Выходные значения этой схемы поступают на входы регистров, но не воспринимаются ими до следующего тактового импульса.

Схема, изображённая на рис. 29.17, называется устройством побитового сложения (bit-serial adder). Чтобы схема работала правильно, период между импульсами должен быть не меньше задержки сумматора (иначе к следующему тику не будет готов выходной бит переноса). Значения на входы подаются с интервалом в один период. В момент первого тактового импульса на входы сумматора подаются значения ао, &о и 0 (рис. 29.17 (а); мы предполагаем, в начальном состоянии на выходе регистра имеется значение 0). На выходе через некоторое время появляются бит суммы so (который выдаётся наружу) и бит переноса с\. Бит переноса поступает (по проводу) на вход регистра, но лишь после второго импульса появляется на выходе регистра. Вместе со значениями а\ и Ь\ он даёт на выходе s\ и с2 (рис. 29.17(b)) и т. д. Так продолжается, пока не будут обработаны все разряды слагаемых, после чего на входы подаются нули (ап = 0, Ьп = 0), и на выход подаётся старший разряд суммы (совпадающий с последним битом переноса; sn = сп) см. рис. 29.17(e).

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

Как мы говорили, тактовая частота зависит от задержки в схеме из функциональных элементов (в данном случае - задержки в элементе суммирования FA), поскольку все вычисления должны закончиться до начала следующего тактового импульса. В данном случае сумматор имеет глубину 0(1), а для получения всех выходов необходимо га+1 периодов, так что общее время работы составляет (п + 1)0(1) = 0(га). Размер схемы равен 0(1).

29.4.3.Каскадное сложение и побитовое сложение

Каскадный сумматор можно рассматривать как развёрнутую схему устройства побитового сложения: теперь за каждый период между импульсами отвечает свой сумматор.

Такое развёртывание, заменяющее время пространством, можно сделать для любой тактированной схемы, соединяя несколько экзмепляров схемы (столько, сколько тактов требует её работа).

Конечно, при этом увеличивается число элементов - зато не нужны синхронизирующие импульсы от тактового генератора. Такая схема на практике работает несколько быстрее, поскольку в тактированной схеме на каждом такте нужно оставлять некоторый запас времени (чтобы вычисления успели произойти), а после развёртывания выходы каскада сразу же попадают на входы следующего, ничего не ожидая.

29.4.4.Одномерный умножитель

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

Оба этих умножителя используют алгоритм, который в Америке называют русским народным алгоритмом умножения (Russian peasants algorithm). Он показан на рис. 29.18 (а). Сомножители а и Ь записываются рядом, и под каждым из них пишется колонка чисел. В левой колонке число на каждом шаге делится на 2 (остаток отбрасывается); в правой - умножается на 2. Так продолжается до тех пор, пока в левой колонке не будет 1. После этого складываются числа из правой колонки, стоящие напротив нечётных чисел в левой.

На первый взгляд этот алгоритм кажется удивительным, но он становится понятным, если записать все числа в двоичной системе: при этом становится ясным, что он представляет собой вариант умножения в столбик. Строки, в которых слева появляется нечётное число, соответствуют единичным разрядам в а, их вклад в сумму есть умноженное на соответствующую степень двойки число Ь (см. рис. 29.18 (Ь)).

Рис. 29.18 29.18 Умножение 19 на 29 с помощью русского народного алгоритма. В колонке а каждое следующее число получается из предыдущего делением на 2 (остаток отбрасывается), а в колонке Ъ -умножением на 2. Складываются числа из правой колонки, напротив которых стоят нечётные числа в левой (выделены серым цветом), (а) Сложение в десятичной системе. (Ь) То же в двоичной системе.

29.4.5.Простая реализация

Простой вариант реализации русского народного алгоритма в виде тактированной схемы умножения га-битовых чисел показан на рис. 29.19 (а). В нём используется 2га групп по 3 регистра. Верхние регистры хранят биты сомножителя а, средние отвечают за сомножитель Ь, а в нижных постепенно формируется произведение р. Содержимое г-го а-регистра перед j-м шагом обозначается а\ , аналогично для Ь и р. Вместе все биты в а-регистрах образуют двоичную запись числа, которогое обозначется (по состоянию

&(°) = Ъ и = 0. Поддерживается инвариант

aU) . ьО) + ptt) = а-Ь(29.6)

(см. упражнение 29.4-2). На j-m шаге производятся следующие действия:

1.Если а0 = 1 (т. е. а) нечётно), то p+1) = + &(•?), иначе р(з+1) - р(])

2.Число а сдвигается вправо на одну позицию (делится на 2 с остатком):

(j+i) { а\1 если 0 г 2га - 2 [ 0 если г = 2га - 1

3.Число Ь сдвигается влево на одну позицию (умножается на 2):

(j+i) \ а\-\ если 1 i 2га - 1 [ 0 если i = О

После га шагов получаем ап) = 0, поэтому инвариант гарантирует, что р(п) = а Ь.

Наш алгоритм требует га шагов. Если на каждом шаге использовать для сложения каскадный сумматор, то каждый шаг занимает время О(га), поэтому общее время работы составляет 0(га2). Схема состоит из Зга регистров, каскадного сумматора размера О(га) и О (га) элементов, формирующих частичные произведения (операция

AND над а0 и 6-битами). Общий размер схемы равен О (га).

Рис. 29.19 29.19 Два одномерных умножителя. Показано умножение 5-битовых чисел а = 19 = (10011) на Ъ = 29 = (11101) и содержимое регистров перед каждым шагом; значащие биты выделены серым цветом, (а) Простой умножитель (время работы 0(п2)). На каждом шаге используется каскадный сумматор, поэтому интервал между тактами должен быть не меньше Q(n). (Ь) Быстрый умножитель, использующий сложение с запоминанием переносов. Каждый шаг требует времени 0(1). Всего требуется 2п - 1 = 9 шагов, показаны первые 5. (После этого остаются сложить и и v, для чего достаточно продолжить тот же процесс сложения с запоминанием переносов.)

29.4.6. Быстрая реализация

Уменьшения времени работы можно добиться, используя вместо каскадного сложения сложение с запоминанием переносов (см. рис. 29.19 (Ь)). Теперь вместо трёх регистров на каждый разряд будут четыре; в двух из них по-прежнему хранятся цифры чисел а и Ь, а вместо числа р будт храниться два числа и и v, причём поддерживается инвариант

а(з) . ь0) + и(Л + VU) = а 6едгао(29.7)

так что роль р играет сумма и + v (см. упражнение 29.4-2). Вначале = г>(°) = 0. (Это соответствует использованию алгоритма