Алгоритмы умножения двоичных чисел

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

- анализ цифры очередного разряда множителя;

- суммирование множимого с накапливаемой суммой частичных произведений, если цифра множителя =1;

- сдвиги в каждом такте цикла умножения.

Умножение можно выполнять как с младших, так и со старших разрядов множителя, и сдвигать можно как сумму частичных произведений, так и множимое. Это и формирует четыре способа умножения чисел, схемы которых приведены на рис.1.

Следует обратить внимание на то, что множитель сдвигается во всех способах умножения, так как в каждом такте анализируется очередной разряд: при умножении с младших разрядов сдвиг выполняется вправо - в сторону младших разрядов, при умножении со старших разрядов множитель сдвигается влево. И еще одна особенность, позволяющая легко запомнить способы умножения: сумма частичных произведений всегда сдвигается в ту же сторону, что и множитель, а множимое сдвигается навстречу множителю, то есть в противоположную сторону.

	Сдвиг суммы частичных произведений	Сдвиг множимого
Сдвиг множителя вправо	I способ	II способ
Сдвиг множителя влево	III способ	IV способ
Рис.1. Схемы четырех способов умножения чисел

I способ – умножение с младших разрядов множителя со сдвигом суммы частичных произведений вправо

Устройства для хранения операндов - регистры, имеют следующую разрядность: регистры множителя и множимого - n-разрядные; регистр суммы частичных произведений - 2n-разрядный.

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

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

Поиск по сайту: