Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

Рассмотрим первую группу логических методов уско­ рения умножения. Сократить количество суммирований при наличии в множителе групп из нескольких единиц (комбинаций вида 0111... ПО..) можно, использовав сле­ дующее свойство двоичного числа:

торой во всех разрядах единицы. Например, двоичное число 011110 —25—21. Таким образом, если при выпол­ нении умножения в множителе встречается группа еди­ ниц, то вместо сложений, число которых равно количест­ ву единиц в группе, можно выполнить одно сложение и одно вычитание.

Умножение с младших разрядов множителя в этом случае может выполняться следующим образом. Множи­ тель сдвигается до появления первой единицы, затем производятся вычитание множимого и сдвиг множителя до появления первого нуля. После этого производится прибавление множимого и вновь сдвиг множителя до появления первой единицы.

Однако такой способ умножения может привести не к уменьшению, а к увеличению количества сложений при обработке комбинаций вида ...01010101.., поскольку в этом случае на каждые два разряда множителя вместо одного сложения при обычном способе умножения необ­ ходимо выполнить одно сложение и одно вычитание. Это обстоятельство делает применение такого способа умно­ жения невыгодным.

Можно улучшить этот способ умножения, использо­

Если две группы нулей разделены единицей, стоящей в k-й позиции, то вместо вычитания в k-й позиции и сло­ жения в k-\- 1-й позиции достаточно выполнить только сложение в k-ü позиции. Если две группы единиц разде­ лены нулем, стоящим в k-ü позиции, то вместо сложения в k-ü позиции и вычитания в ß + 1 -й позиции достаточно выполнить только вычитание в k-ü позиции.

335

Алгоритм действия на данном шаге умножения мо­ жет быть записан с помощью следующих выражений ал­ гебры логики:

di — ibi 0 ^ - 1 )

где i — номер разряда множителя; 6,— цифра разряда множителя;

dt— двоичная переменная, единичное значение ко­ торой для соответствующего разряда множите­ ля указывает на необходимость выполнения арифметического действия;

Si— знак арифметического действия.

При d i= 1, Si==bi+X. Если Sj=0, то производится до­ бавление множимого к частичному произведению. При

336

Si= 1 производится вычитание множимого из частичного произведения.

Данный алгоритм умножения впервые был предло­ жен Леманом [Л. 105]. Схема выполнения умножения начиная с младших разрядов множителя, реализующая алгоритм Лемана, показана на рис. 5-14. Для запомина­

Он устанавливается в состояние 1 при выполнении вы­ читания и в состояние 0 при выполнении сложения. Схе­ мы, вырабатывающие командные сигналы сложения и вычитания, управляются триггером Т3ап и двумя млад­ шими разрядами регистра множителя.

стоит 0, то схема И\ возбуждает сигнал сложения. При наличии в следующем разряде единицы схема И3 воз­ буждает сигнал вычитания и Гзап устанавливается в состояние 1.

Если Т3ап находится в состоянии 1, то сдвиг множите­ ля и сумматора частичных произведений производится до появления 0 в младшем разряде регистра множителя. При наличии в следующем разряде единицы схема Я 4 возбуждает сигнал вычитания, а при наличии нуля схе­ ма И2 возбуждает сигнал сложения, который устанавли­ вает Тзап в состояние 0.

При таком способе умножения даже при наиболее неблагоприятном сочетании цифр множителя количество суммирований равно «/2, где п — число разрядов множи­ теля. В среднем же количество суммирований для «-раз­ рядного множителя равно п/3 [Л. 105].

Следует отметить, что при использовании некоторых аппаратных методов ускорения умножения сокращение количества суммирований может не привести к уменьше­ нию времени умножения. Например, если в АЛУ реализо­ ван сумматор с запоминанием переносов и сложение в сумматоре совмещено по времени со сдвигом, то время умножения определяется числом сдвигов (количеством разрядов множителя) и уменьшение суммирований не приводит к сокращению времени умножения.

В этом случае оказываются эффективными логиче­ ские методы ускорения с обработкой за шаг умножения нескольких разрядов множителя.

22—333 337

ilüit

Наиболее распространенными среди синхронных спо­ собов ускорения являются способы умножения с обра­ боткой за шаг двух разрядов множителя.

Рассмотрим один из способов умножения на два раз­ ряда множителя начиная с младших его разрядов. В за­ висимости от результата исследования пары разрядов множителя предусматриваются следующие действия.

В случае пары 00 производится простой сдвиг на два разряда вправо частичного произведения. В случае пары 01 к сумме частичных произведений прибавляется оди­ нарное множимое и сумма частичных произведений сдвигается на два разряда вправо. В случае пары 10 прибавляется удвоенное множимое и сумма частичных произведений сдвигается на два разряда вправо. В слу­ чае пары 11 из суммы частичных произведений вычита­ ется одинарное множимое и сумма частичных произведе­ ний сдвигается на два разряда вправо. Тогда в первых трех случаях результат получается правильный, а в по­ следнем неправильный, он должен быть скорректирован на следующем шаге.

Поскольку в случае пары 11 из суммы частичных произведений вычитается одинарное множимое вместо прибавления утроенного множимого, для корректировки результата к сумме частичных произведений перед вы­ полнением сдвига надо было бы прибавить учетверенное множимое. Но после сдвига на два разряда вправо сум­ ма частичных произведений уменьшается в 4 раза, так что для корректировки его на следующем шаге должно быть прибавлено одинарное множимое.

Это учитывается при обработке следующей пары раз­ рядов. Если следующая пара 00, то она обрабатывается как 01. Если следующая пара 01, то она обрабатывается как 10. Если следующая пара 10, то она обрабатывается как 11. Если следующая пара 11, то она обрабатывается как 00 и учитывается дополнительная единица для сле­ дующей пары. Удвоенное множимое может быть получе­ но сдвигом его в регистре множимого или переключением его разрядов на входе сумматора. Дополнительная еди­ ница может запоминаться в отдельном триггере.

Правила для обработки пар разрядов множителя с учетом дополнительной единицы от предыдущей пары сведены в табл. 5-2.

Схема умножения, реализующая данный алгоритм, показана на рис. 5-15. Для корректировки результата

338

Т а б л и ц а 5-2

Рис. 5-15. Схема умножения на 2 разряда мно­ жителя.