разрядных чисел с равной вероятностью появляются значения О и 1, причём разные входы независимы. Докажите, что с вероятностью не менее 1 - 1/га никакой перенос не распространяется далее чем на О (lgra) разрядов.

29.3. Схемы для умножения

Наиболее простой алгоритм умножения «столбиком»состоит в сложении «сдвигов» одного из сомножителей: 2га-битовое произведение двух га-битовых чисел а = (ara-i, ап-2, , ао) и 6 = (bn-i, Ьп 2, , bo) может быть записано как

п-1

р = а Ь = mSl\

8 = 0

где toW = a - bi -2г получается из а сдвигом всех разрядов на г единиц влево (и заполнением освободившихся разрядов нулями), если bi = 1, и равно 0, если Ьг- = 0) (рис. 29.13). Числа тг- называются частичными произведениями; каждое ненулевое частичное произведение соответствет ненулевому разряду в Ь.

Рис. 29.13 29.13 Умножение чисел а = (1110) и Ъ = (1101) столбиком; произведение р = а Ь = (10110110). Каждое частичное произведение тг получается из а сдвигом на г разрядов влево, если b, = 1. В противном случае оно равно нулю.

В этом разделе рассматриваются две схемы для умножения. Матричный умножитель работает за время О(га) и имеет размер в (га2). Дерево Уоллеса (Wallace-tree multiplier) также имеет размер 0(га2), но работает быстрее, за время O(lgra). Обе схемы используют умножение столбиком.

29.3.1. Матричный умножитель

Матричный умножитель работает в три этапа: (1) вычисляет частичные произведения; (2) складывает их, используя сложение с запоминанием переносов, пока не остается два числа; (3) складывает эти два числа (с помощью каскадного сумматора или с предвычисленим переносов).

Матричный умножитель (array multiplier) показан на рис. 29.14; входные биты аг- соответствуют вертикальным проводам, биты Ьг-- горизонтальным. Каждый входной бит поступает на входы га элементов AND, которые вычисляют разряды частичных произведений:

= а? • bi = aj AND bi

Число элементов AND равно га2; все они работают одновременно, вычисляя биты частичных произведений (кроме тех, что заведомо равны 0). Затем сумматоры с запоминанием переносов (составленные из суммирующих элементов FA) складывают частичные произведения. Младшие разряды появляются на выходах в парвом столбце рисунка, старшие получаются на выходе сумматора в низу рисунка.

Рис. 29.14 29.14 Матричный умножитель для п = 4. Элемент AND, обозначенный Ст8, вычисляет j-ik бит частичного произведения т8. Каждый горизонтальный ряд суммипующих элементов FAp) представляет собой сумматор

с запоминанием переносов. Младшие п битов произведения - это бит га0° и u-биты, получаемые в правом столбце в ходе сложения с запоминанием переносов. Старшие п битов получаются на выходе сумматора, складывающего u-биты и-биты, выходящие из суммирующие элементов нижней строки. Показаны значения для множителей рис. 29.13.

Последовательно выполняемые сложения с запоминанием переносов показаны на рис. 29.15. Вначале из чисел 0, то(°) и tow получаются числа и t>W (не более га + 1 битов в каждом; для t>W это так, поскольку га+ 1-ые разряды двух слагаемых из трёх равны 0), при этом то(°) + tow = -wW + t>W Затем из чисел ul\ t>W и то(2) получаются числа и(2) и v2\ имеющие по га + 2 битов каждое (снова в двух слагаемых из трёх старший бит равен 0). Мы продолжаем процесс, складывая и1~1\ г/8-1) и raW для всех i = 2, 3,... , га - 1. В конце концов мы получаем 2 числа ип~1 и vn~l по (2га - 1) битов в каждом, при этом

п-1

+= £ ш(0 =(29.5)

8 = 0

= р.(29.6)

(29.7)

Не все разряды чисел t>W используются: поскольку = 0 при

(г)•...

j = 0,... , г - 1, г + га,... , 2га - 1 и vy- = 0 при j = 0,... , г, г + га, г + га + 1,... , 2га - 1 (см. упражнение 29.3-1), на г-м шаге необходимо работать только с га- 1 разрядами (г, г + 1,... , г + га -2). Вернёмся к

Рис. 29.15 29.15 Суммирование частичных произведений: повторное сложение с запоминанием переносов. Разобран пример рис. 29.13 (а = (1110), Ъ = (1101)). Пустые места перед знаками равенства считаются заполненными нулями. Мы вычисляем т0 + т1 + 0 = и1 + г/1, затем и1 + г/1 + т2 = и2 + г/2, „(2) +г;(2) +т(з) „(з) +v(3) И] наконеЦ] р т(о) т(1) т(2) +т(з) = „(з) j,(3)

При этом ро = пг0° и рг = и-8 для г = 1, 2, . . . , п - 1.

матричному умножителю (рис. 29.14). Элементы AND (обозначен-

ные G) вычисляют частичные произведения. Выходом элемента

G будет бит то есть j-ый бит г-го частичного произведения, так что г-ая строка AND-матрицы даёт га значащих битов частичного произведения га (с индексами га + г - 1, га + г - 2,... , г).

(г)(г)

Каждый ряд сумматоров FA\ ,... , FAi совершает г-й шаг сложения с запоминанием переносов, вычисляя и t>W; элемент FA

,(г) (г-1)(г-1..,-(г)

получает на вход биты т- ,и uj и выдает два бита

и г; 11. Заметьте, что в левой колонке и\ п 1 = т\ п 1, поэтому этот бит не нужно специально вычислять. На входах сумматоров в верхнем ряду фиксировано значение 0, так как одно из слагаемых равно нулю.

Теперь о выходных битах матричного умножителя. Как мы уже отмечали, vn = 0 для j = 0,1,... , га - 1. Поэтому pj = ип

п 11с(!) п(!)(°)

для j = 0,1,... , га - 1. Ьолее того, раз mQ = 0, то и0 = mQ ,

)(0 и Л1-1)

поскольку г младших битов у чисел т(г> и v(t > равны 0, мы имеем = и(г - 1) • для г = 2, 3,... , га - 1 и j = 0,1,... , г - 1. Следовательно, Ро = т0°) и далее рг- = и\ при г = 1, 2,... , га - 1. Так определяются га младших разрядов произведения. Старшие разряды произведения вычисляются с помощью одной из схем предыдущего раздела:

(Р2гг-1,Р2гг-2, , Рп) = ,(""!) >"!)7(п-1)\ , /„("-1) „("-1)v(n-l)\

29.3.2. Характеристики схемы

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

Схема содержит га2 элементов AND, примерно столько же суммирующих элементов и сумматор размера в (га). Поэтому её размер составляет 0(га2).

29.3.3. Умножение с помощью дерева Уоллеса

Дерево Уоллеса (Wallace tree) сводит задачу сложения га чисел размера га к сложению двух чисел размера в (га). Это делается так: используя [п/3\ сумматоров с запоминанием переносов, мы сводим сложение га чисел к сложению [~2га/3] чисел. Эта процедура повторяется до тех пор, пока не останется всего два слагаемых. На каждом