Логические методы ускорения умножения
1. умножение на два разряда множителя за один такт:
bn bn+1 микрооперация
0 0 нет
0 1 +А
1 0 +2А
1 1 -А
| Bn | bn+1 | P | мко | P' |
| - | ||||
| +A | ||||
| +A | ||||
| +2A | ||||
| +2A | ||||
| -A | ||||
| -A | ||||
| - |
В базовом алгоритме Тумн= n(Тсдв+0,5Тсум).
В этом алгоритме Тумн=n/2(Тсдв+3/4Тсум).
Микропрограмма умножения на два разряда множителя.
При прибавлении к сумме частных произведений n+1 разрядного частного произведения 2А,. Результат может получиться n+2 разрядным. С учетом разряда переноса и знакового разряда сумматор должен быть n+3 разрядным, предполагается, что n – четное.
В качестве аппаратной поддержки необходим формирователь дополнительного кода, чтобы вычесть А.
2. умножение с последовательным преобразованием цифр множителя.
В …01111110…
+А -А
…1 0 1 0 1 0 1 0 1… (*)
-А+А-А+А-А+А-А+А-А
Для приодаления ситуации (*) договорились игнорировать серии длиной в 1 бит. Для реализации микропрограммы умножения вводится триггер j, который задает режим сдвига, и тогда возможны 4 ситуации:
j=0 – сдвиг по 0ж
j=1 – сдвиг по единицам.
1) начало серии единиц
j=0
bn+1=1
bn=1
-A j:=1
2) начало серии нулей
j=1
bn+1=0
bn=0
+A j:=0
3) единица среди нулей
j=0
bn+1=1
bn==0
+A j=0(без изм.)
4) ноль среди единиц
…111101111…В
j=1
bn+1=0
bn=1
-A j=1(без изм.).
В начале алгоритма j:=0. сдвиг осуществляется на первый разряд. Цикл проверки bn, bn+1, p повторяются n раз. Если при выходе из цикла j=1, то делается дополнительное суммирование С:=С+1.
| № | bn | bn+1 | j | M\o | j’ |
| - | |||||
| +A | |||||
| +A | |||||
| - | |||||
| - | |||||
| -A | |||||
| -A | |||||
| - |
Пример:
В = 0 1 1 0 1 1 1 0 1 0 1 1 1
+А - - -А - - - -А - -А - - -
Тумн.=n*(Тсдв+1/3Тсум.);
Для ускорения алгоритма можно ввести цепи сдвига на 2 разряда. При встречи комбинации, описанной в 4 и 5 строках, выполнить микрооперацию сдвига на 1 разряд, для остальных – на 2 разряда.