сложение с предвычислением переносов (carry-lookahead addition), причем соответствующая схема также имеет размер в (га). Наконец, сложение с запоминанием переносов (carry-save addition) за время 0(1) сводит сложение трёх га-разрядных чисел к сложению га-разрядного и (га + 1)-разрядного чисел. Схема также имеет размер 0(га).

29.2.1. Каскадное сложение

Неотрицательное целое число а записывается в двоичной системе как последовательностью га битов (ага-ъ an-2j • • • , ao)j причем га [lg(«+l)l и

п-1

а = Е «г2*-

г=0

При сложении по двум га-значным числам а = (ara-i, ап-2, ,ао) и Ь = (bn i, bn 2, , bo) строится (га + 1)-значное число s = (sn, sra 2,... , So), равное их сумме (пример на рис. 29.3).

Рис. 29.3 29.3 При сложении 8-значных чисел а = (01011110) и Ь = (11010101) получается 9-значное число s = (100110011). В г-м столбце указаны г-е разряды чисел а, Ъ и s, а также бит переноса с,. Входной бит переноса со всегда равен 0.

При сложении столбиком (справа налево) мы складываем в г-м разряде bi и входной бит переноса (carry-in bit) сг-. Младший разряд суммы записывается в г-ый разряд ответа (s8), а старший становится выходным битом переноса (carry-out bit) c8 i и используется при сложении в следующем разряде. В младший разряд ничего не переносится, поэтому со = 0. Последний перенос сп становится старшим разрядом суммы sn. Поскольку s4- = parity(сц, bi, сг), а сг 1 = majority(аг, 6г, сг), для каждого шага можно годится описанный выше сумматор.

Таким образом, га-разрядный каскадный сумматор состоит из последовательно соединённых простых сумматоров FAq,FA\, ... ,FAn-\, так что выход c8 i сумматора FAi является входом для FAi+i. На входе со фиксировано значение 0, не зависящее от входов (см. рис. 29.4).

Рис. 29.4 Каскадный сумматор для п = 8. Ромбик справа означает, что значение на входе фиксировано.

Поскольку бит переноса проходит через все сумматоры, глубина каскадного сумматора равна га (а глубина элемента FAi равна г+1). Поэтому время работы составляет в (га). Размер схемы равен в (га).

29.2.2. Сложение с предвычислением переносов

В каскадном сумматоре бит переноса сг- вычисляется в момент времени г. Значения аг- и Ьг-, однако, известны с самого начала. В некоторых случаях они определяют бит переноса сг-:

•если аг- = Ь{ = 0, то сг- = 0 (перенос «поглощается»(kill))

•если аг- = Ьг- = 1, то сг- = 1 (перенос «порождается»(generate))

Однако если один из битов аг- и Ьг- равен 1, а другой 0, но c8 i существен; именно,

•если аг- ф bi, то сг- = сг 1 (перенос распространяется (propagate))

Каждому разряду, следовательно, соответствует один из трёх типов переноса (carry statuses): k, (kill), g (generate) или p (propagate) (см. рис. 29.5). Этот тип известен заранее, что позволяет уменьшить время работы схемы сложения.

Рис. 29.5 Выходной бит переноса и тип переноса сумматора FA,-i в зависимости от а, и 6,.

Зная типы переноса для соседних сумматоров ((г - 1)-го и г-го), можно определить тип переноса для их соединения, считая c8 i входным битом, a c8 i - выходным: зная, что случается с битом переноса на каждом шаге, можно рассчитать, что произойдёт за два шага, то есть как зависит c8 i от c8 i. Если г-й разряд имеет тип к или g, то соединение имеет тот же тип переноса. Если же г-й разряд имеет тип переноса р, то тип переноса для соединения совпадает с типом (г - 1)-го разряда (см. рис. 29.6).

Рис. 29.6 Тип переноса соединения двух сумматоров (таблица операции Сх)).

Таблицу на рис. 29.6 можно рассматривать как определение операции (композиции типов переноса) на множестве {k, g, р} ; она будет обозначаться символом <g>. Эта операция ассоциативна (см. упражнение 29.2-2).

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

[ k,ifa8 i = 6г 1 = 0; g,ifa8 i = 6г 1 = 1;(29.3)

p,ifa; i ф 6г 1.

Тогда зависимость, скажем, бита с7 от с4 определяется композицией ж5 (g) Xq (g) ж7.

Поскольку в нулевой разряд переноса от младших разрядов не поступает, условно положим жо = к. Тогда перенос на выходе г -го

разряда определяется композицией xq <g> х\ <g> ... <g> xf. С{ = О, если композиция равна к, и с,- = 1, если композиция равна g. (Значение р для композиции невозможно, поскольку для этого все члены должны быть равна р, а это не так для жо-)

Более формально это записывается так. Положим уо = к и определим У1,у2,---уп так:

Другими словами, уо,...уп называются префиксами (prefixes) выражения жо®Ж1®.. .®хп. (Общая задача о параллельном вычислении префиксов рассмотрена в гл. 30). На рис. 29.7 показаны значения Xi и yi для примера рис. 29.3.

Рис. 29.7 29.7. Значения х, и у, для примера рис. 29.3.

Теперь сказанное выше запишется так: Лемма 29.1. При всех г = 0,1, 2,... , га:

1.Если yi = к, то Ci = 0.

2.Если yi = g, то Ci = 1

3.Случай yi = р невозможен.

Доказательство. Индукция по г. При г = 0 по определению уо = жо = к и со = 0. Пусть утверждение леммы выполнено для г - 1. Возможны три случая.

1.Если yi = к, то либо Xi = к (и тогда сг- = 0), либо жг- = р и жг 1 = к. Тогда по предположению индукции c8 i = 0, а сг- = сг 1 (бит переноса сохраняется), поэтому и в этом случае сг- = 0.

2.Случай yi = g аналогичен.

3.Если yi = р, то обязательно жг- = р и = р, но последнее равенство невозможно по предположению индукции.

Лемма доказана.

Таким образом, вычисление битов переноса сг- сводится к вычислению префиксов yi. Оставшиеся действия выполняются за время 0(1) -достаточно подать биты переноса на входы сумматоров.

29.2.3. Вычисление типов переноса с помощью параллельной префиксной схемы

Здесь мы рассмотрим схему, использующую возможность параллельных вычислений и позволяющую за время О (lgra) вычислить все типы переноса уг-. Она имеет размер О (га).

Введём некоторые обозначения. При 0 г j га положим

Уг = Xi <g) уг 1 = Ж0 <g> Xi <g) . . . ® Xi

(29.3)

В частности, [г, г]

[г, j] = Xi 0 жг+1 <g) ... <g) Xi. Если 0 г < j /г га, то [i,fc] = [i,i-l]®[i,A;]

(29.4)