Сокращение слагаемых - Reduction of summands

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

Шаги

Производство слагаемых

При двоичном умножении каждая строка слагаемых будет либо нулем, либо одним из чисел, которые нужно умножить. Обратите внимание на следующее:

   1001
  x1010
  -----
   0000
  1001
 0000
1001

Вторая и четвертая строки слагаемых эквивалентны первому члену. Производство слагаемых требует простого логического элемента И для каждого слагаемого. При наличии достаточного количества логических элементов И время создания слагаемых будет составлять один цикл арифметико-логического устройства .

Сокращение слагаемых

Слагаемые сокращаются с помощью обычного 1-битного полного сумматора, который принимает два 1-битных члена и один переносимый бит. Он производит сумму и перенос. Полные сумматоры расположены так, что сумма остается в том же столбце слагаемых, но перенос сдвигается влево. В каждом цикле сокращения три бита в одном столбце используются в качестве двух членов и переноса для полного сумматора, создавая один бит суммы для столбца. Это уменьшает количество битов в столбце в 3 раза. Однако столбец справа будет сдвигать биты переноса, увеличивая количество битов в столбце на треть от числа строк слагаемых. В худшем случае сокращение составит 2/3 числа строк за раунд сокращения.

Ниже показано, как выполняется первый раунд сокращения. Обратите внимание, что все «пустые» позиции слагаемых считаются нулевыми (a. Используется здесь как индикатор «предполагаемых нулевых значений»). В каждой строке три верхних бита - это три входа для полного сумматора (два члена и перенос). Сумма помещается в верхний бит столбца. Вынос размещается во втором ряду столбца слева. Нижний бит - это единичная подача в сумматор. Сумма этого сумматора помещается в третью строку столбца. Перенос игнорируется, так как он всегда будет равен нулю, но по замыслу он будет помещен в четвертую строку столбца слева. Для дизайна важно отметить, что строки 1, 3, 5, ... (считая сверху) заполняются суммами из самого столбца. Строки 2, 4, 6, ... заполнены значениями переноса из столбца справа.

   1011
  x0110
  -----
...0000
..1011.
.1011..
0000...
-------
0111010
000100.
00000..

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

0111010
000100.
00000..
-------
0110010
001000.

Когда значимых строк слагаемых всего две, редукционные циклы заканчиваются. Для базового полного сумматора обычно требуется три цикла арифметико-логического устройства . Поэтому каждый цикл восстановления обычно длится 3 цикла.

Суммирование

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

Время расчета

Время вычисления для алгоритма сокращения слагаемых: T = 1Δt + r3Δt + FA (где r - количество циклов сокращения, а FA - время для быстрого сумматора в конце алгоритма).