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

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

Шаги

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

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

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

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

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

Ниже показано, как выполняется первый этап сокращения. Обратите внимание, что все «пустые» позиции слагаемых считаются нулевыми (здесь . используется как индикатор «предполагаемых нулевых значений»). В каждой строке три старших бита представляют собой три входа полного сумматора (два члена и перенос). Сумма помещается в верхний бит столбца. Вынос размещается во второй строке столбца слева. Нижний бит — это одиночная подача в сумматор. Сумма этого сумматора помещается в третью строку столбца. Вынос игнорируется, поскольку он всегда будет равен нулю, но по замыслу он будет помещен в четвертую строку столбца слева. Для дизайна важно учесть, что строки 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 — время быстрого сумматора в конце алгоритма).