Метод ускоренного умножения Мак-Сорли

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

Рассмотрим этот метод на примере умножения, начиная со старших разрядов множителя, с обработкой за один цикл двух разрядов множителя. В этом случае разряды множителя анализируются слева направо.

При анализе первой пары разрядов множителя предусматриваются следующие действия. Если анализируемая пара 00 или 10, то есть правый (младший) разряд пары имеет значение 0, то производятся те же действия, что и в предыдущем методе: к сумме частичных произведений или ничего не прибавляется, или прибавляется удвоенное множимое . Если анализируемая пара разрядов множителя 01 или 11, то производится прибавление к сумме частичных произведений множимого, умноженного на число, которое на единицу больше, чем данная пара. Иными словами, к сумме частичных произведений прибавляется либо удвоенное , либо учетверенное множимое.

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

После обработки очередной пары разрядов множителя сумма частичных произведений сдвигается на два разряда влево, то есть увеличивается в четыре раза. Следовательно, в случае обработки пары разрядов множителя 01 и 11 сумма частичных произведений перед обработкой следующей пары будет больше истинной на учетверенное множимое. Поэтому, если правый (младший) разряд предыдущей пары разрядов множителя был равен 1, то для коррекции суммы частичных произведений действие при обработке данной пары должно учитывать необходимость вычитания учетверенного множимого.

При обработке пары 00 из суммы частичных произведений должно быть вычтено учетверенное множимое. При обработке пары 10 из суммы частичных произведений должно быть вычтено удвоенное множимое. При обработке пары 01 также должно быть вычтено удвоенное множимое, а при паре 11 сумма частичных произведений не изменяется.

Правила для обработки по методу Мак-Сорли пар разрядов множителя с учетом младшего разряда предыдущей пары удобно представить в виде табл. 2.2.

 

Таблица 2.2

Пара разрядов множителя Младший разряд предыдущей пары Операция в сумматоре Кратность множимому
0 0 Отсутствие действия
0 1 +
1 0 +
1 1 +
0 0 -
0 1 -
1 0 -
1 1 -

 

Из приведенной таблицы видно, что для выполнения умножения используется удвоенное и учетверенное множимое. Поэтому перед началом умножения в регистр множимого засылается удвоенное, то есть сдвинутое на один разряд влево, множимое. При обработке пар разрядов множителя, требующих прибавления или вычитания учетверенного множимого, логическими схемами вырабатывается сигнал, подключающий к сумматору содержимое регистра множимого, то есть 2Х, сдвинутое еще на один разряд влево.

Логические схемы, формирующие сигнал вычитания (-); формирующие сигнал сложения (+); формирующие сигнал подключения учетверенного множимого, управляются старшими разрядами и дополнительным разрядом регистра множителя. После обработки в очередном цикле каждой пары разрядов регистра множителя его содержимое и содержимое сумматора частичных произведений сдвигается на два разряда влево.

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

 



php"; ?>