Сокращение слагаемых
 |
Сокращение слагаемых — это алгоритм быстрого двоичного умножения беззнаковых двоичных целых чисел. Он выполняется в три этапа: получение слагаемых, сокращение слагаемых и суммирование.
Шаги
[ редактировать ]Производство слагаемых
[ редактировать ]При двоичном умножении каждая строка слагаемых будет либо нулем, либо одним из чисел, подлежащих умножению. Учтите следующее:
1001 х1010 ----- 0000 1001 00001001
Вторая и четвертая строки слагаемых эквивалентны первому слагаемому. Для формирования слагаемых требуется простой логический элемент И для каждого слагаемого. При достаточном количестве логических элементов И время создания слагаемых составит один цикл арифметико-логического устройства .
Сокращение слагаемых
[ редактировать ]Слагаемые сокращаются с использованием обычного 1-битного полного сумматора , который принимает два 1-битных члена и бит переноса. Он производит сумму и перенос. Полные сумматоры устроены так, что сумма остается в том же столбце слагаемых, но перенос смещается влево. В каждом раунде сокращения три бита в одном столбце используются в качестве двух членов и переноса для полного сумматора, образуя один бит суммы для столбца. Это уменьшает количество битов в столбце в 3 раза. Однако столбец вправо сместится на биты переноса, увеличивая биты в столбце на треть от количества строк слагаемых. В худшем случае сокращение составит 2/3 количества строк за раунд сокращения.
Ниже показано, как выполняется первый этап сокращения. Обратите внимание, что все «пустые» позиции слагаемых считаются нулевыми (здесь . используется как индикатор «предполагаемых нулевых значений»). В каждой строке три старших бита представляют собой три входа полного сумматора (два члена и перенос). Сумма помещается в верхний бит столбца. Вынос размещается во второй строке столбца слева. Нижний бит — это одиночная подача в сумматор. Сумма этого сумматора помещается в третью строку столбца. Вынос игнорируется, поскольку он всегда будет равен нулю, но по замыслу он будет помещен в четвертую строку столбца слева. Для дизайна важно учесть, что строки 1, 3, 5,... (считая сверху) заполняются суммами из самого столбца. Строки 2, 4, 6, ... заполняются значениями выноса из столбца справа.
1011 х0110 -----...0000..1011..1011..0000...-------0111010000100.00000..
Сокращение выполняется еще раз точно таким же образом. На этот раз интерес представляют только три верхние строки слагаемых, поскольку все остальные слагаемые должны быть равны нулю.
0111010000100.00000..-------0110010001000.
Когда имеется только две значащие строки слагаемых, циклы приведения заканчиваются. Базовый полный сумматор обычно требует трех циклов арифметико-логического устройства . Таким образом, каждый цикл сокращения обычно длится 3 цикла.
Суммирование
[ редактировать ]Когда остается только две строки слагаемых, они складываются с помощью быстрого сумматора. Существует множество конструкций быстрых сумматоров, любую из которых можно использовать для завершения этого алгоритма.
Время расчета
[ редактировать ]Время расчета для алгоритма приведения слагаемых составляет: T = 1Δt + r3Δt + FA (где r — количество циклов приведения, а FA — время работы быстрого сумматора в конце алгоритма).