ЛЕКЦИЯ 11

Каждый элемент этой матрицы равен 0 или 1. Произведение дзух чисел можно получить, если суммировать элементы матрицы р следующем порядке:

Так как при суммировании по столбцам складываются только -0 или 1, то операцию сложения можно выполнить с помощью счет­ чиков. Однако при значительном числе разрядов сомножителей потребуются счетчики с большим количеством входов и выходов, что существенно увеличивает время суммирования. Но этот принцип умножения можно реализовать таким образом, что количество вхо­дов счетчиков на каждом этапе не будет больше трех. Значит, для этих целей можно использовать одноразрядные двоичные полусум­маторы и сумматоры.

Наиболее известны среди матричных алгоритмов умножения алгоритмы Дадда, Уоллеса, матричный и алгоритм с сохранением переносов. На рис. 5.4 представлена структурная схема множительного устройства для реализации матричного алгоритма, а на рис схема, с помощью которой может быть реализован алгоритм Дадда. Как видно из рисунков, алгоритмы отличаются друг от друга не только группировкой частных произведений, но и количеством ступеней преобразования: для матричного алгоритма количество ступеней преобразования равно четырем, т. е. на единицу меньше числа разрядов сомножителей, а для алгоритма Дадда - трем. Но с другой стороны, группировка разрядов по методу Дадда требует более сложного устройства управления операцией умножения. Реализация матричных методов выполнения операции умноже­ ния требует большего количества оборудования, чем методов последовательного анализа разрядов или групп разрядов множителя и дает больший выигрыш во времени. Однако в связи с широким раз­витием микроэлектронных и особенно больших интегральных схем (БИС) ограничения по количеству оборудования становятся все ме­нее строгими, поэтому рассмотренные выше методы применяют на практике.

Деление двоичных чисел во многом аналогично делению деся­ тичных чисел. Процесс деления состоит в том, что последовательно разряд за разрядом отыскиваются цифры частного путем подбора с последующим умножением этой цифры на делитель и вычитанием этого произведения из делимого.Из множества разных методов выполнения операции деления рассмотрим наиболее распространенные. Прежде всего это «школьный» алгоритм деления, заключав­ шийся в том, что делитель на каждом шаге вычитается столько раз из делимого (начиная со старших разрядов), сколько это воз-» можно для получения наименьшего положительного остатка. Тогда в очередной разряд частного записывается цифра, равная числу делителей, содержащихся в делимом на данном шаге. Таким обра­зом, весь процесс деления сводится к операциям вычитания и сдвига. Другой метод выполнения операции деления заключается в ; умножении делимого на обратную величину делителя. 6. Деление чисел на двоичных сумматорах 6.1. Методы деления двоичных чисел

Здесь возникает новая операция - вычисление обратной величины, осуществ­ляемая по известным приближенным формулам (например, разложением в биномиальный ряд Ньютона и т. п.). В этом случае в сос­тав команд машины должна входить специальная операция нахож­дения обратной величины. К наиболее распространенным методам выполнения операции деления относится также метод, заключающийся в использовании приближенной формулы для нахождения частного от деления двух величин. От метода умножения делимого на обратную величину он отличается только тем, что частное определяется по некоторой формуле, которая сводится к выполнению операций сложения, вычита­ния и умножения. Фактически два последних метода пригодны для использования в специализированных машинах, в которых операции деления встречается не часто и ее целесообразно реализовать программным путем. В универсальных вычислительных машинах, как правило, реализуется разновидность «школьного» алгоритма деления.

В общем случае «школьный> алгоритм деления на примере двоичных чисел выглядит следующим образом:

Здесь цифры частного получаются последовательно начиная со старшего разряда путем вычитания делителя из полученного остатка. Если получен положительный остаток, то цифра частного равна единице; если остаток отрицательный, то цифра частного равна нулю, при этом восстанавливается предыдущий положительный остаток. В случае положительного остатка для получения следующей цифры частного последний остаток сдвигается влево на один разряд (либо делитель вправо на один разряд) и из него вычитается делитель и т. д. В случае отрицательного остатка восстанавливается предыдущий положительный остаток прибавлением к отрицательному остатку делителя и восстановленные остаток сдвигается на один разряд влево (либо сдвигается делитель вправо на один разряд) и из него вычитается делитель. Такой алгоритм деления получил название алгоритма деления с восстановлением остатка.