Сумматор с сохранением переноса

Сумматор с сохранением переноса^[1]^[2] (англ. carry-save adder) — является видом цифровых сумматоров, используемых в компьютерной микроархитектуре для вычисления суммы трёх или более n-битных чисел в двоичной системе счисления. Он отличается от других цифровых сумматоров тем, что его выходные два числа той же размерности, что и входные, одно из которых является частной суммой битов, а другое является последовательностью битов переноса.

Мотивация

Рассмотрим сумму:

  12345678
+ 87654322
=100000000

Используя арифметику, справа налево: «8+2=0, перенос 1», «7+2+1=0, перенос 1», «6+3+1=0, перенос 1» и так далее до конца суммы. Однако, мы знаем, что пока не получена последняя цифра результата, мы не знаем первой цифры слева, пока мы не пройдём через каждую цифру в вычислениях, перенося перенос от каждой цифры к другой слева от неё. Таким образом, сложение двух n-битных чисел займёт время пропорциональное n, даже если машина, которую мы используем, способна выполнять множество вычислений одновременно.

В терминах электроники, используя биты (двоичные цифры), это означает, что даже если мы имеем в нашем распоряжении n однобитных сумматоров, мы по прежнему должны тратить время пропорциональное n, чтобы позволить переносу распространиться от одного конца числа до другого. Пока мы делаем это,

1. Мы не знаем результат сложения.

2. Мы не знаем будет ли результат сложения меньше или больше, чем данное число (например, мы не знаем будет ли он положительным или отрицательным).

Сумматор с ускоренным переносом может уменьшить задержку. В принципе, задержка может быть уменьшена так, что она будет пропорциональна logn, но для больших чисел это уже не тот случай, потому что даже когда применяется ускоренный перенос, расстояние, которое сигнал проходит по чипу увеличивается пропорционально n и задержка распространения возрастает в этом же отношении. Как только мы получим числа с размерами от 512-битов до 2048-битов, которые требуются в криптосистемах с открытым ключом, ускоренный перенос более не помогает.

Основная концепция

Мысль задержки разрешения переноса до конца, или сохранения переносов, принадлежит Джону фон Нейману.^[3]

Здесь приведён пример двоичного сложения:

  10111010101011011111000000001101
+ 11011110101011011011111011101111.

Арифметика с сохранением переноса работает покидая двоичную запись, всё ещё оставаясь работать по основанию 2. Она вычисляет сумму цифра за цифрой, как

  10111010101011011111000000001101
+ 11011110101011011011111011101111
= 21122120202022022122111011102212.

Запись является нетрадиционной, но результат остаётся однозначным. Более того, данными n сумматорами (здесь, n = 32 полных сумматора), результат может быть вычислен после прохождения входов через один сумматор (за один такт генератора), так как каждая цифра результата не зависит от какой-либо другой.

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

Накопители с сохранением переноса

Предположим, что мы имеем два бита памяти на каждую цифру результата, тогда мы можем использовать избыточное двоичное представление, запоминая величины 0, 1, 2 или 3 в каждой цифровой позиции. Это происходит потому, что к нашему результату с сохранением переноса может быть добавлено более одного двоичного числа без переполнения ёмкости нашей памяти: но потом что?

Ключом к пониманию является то, что за время каждого частичного сложения мы складываем три бита:

0 или 1, из чисел, которые мы складываем.
0 если цифра в нашей памяти является 0 или 2, или 1 если она является 1 или 3.
0 если цифра справа является 0 или 1, или 1 если она является 2 или 3.

Другими словами, мы берём цифру переноса из позиции справа, и переносим цифру переноса налево, также как и в традиционном сложении; но цифра переноса, которую мы передаём налево является результатом предыдущего вычисления, а не текущего. За каждый такт генератора, переносы сдвигаются только на один шаг вперёд, а не на n шагов, как в традиционном сложении.

Так как сигналы перемещаются не так далеко, генератор может тикать более быстро.

В конце вычисления остаётся необходимость преобразовать результат в двоичный, которое фактически просто означает разрешение переносам проходить весь путь через число также как и в традиционном сумматоре. Но если мы сделали 512 сложений в процессе выполнения 512-битного умножения, большая цена этого конечного преобразования фактически делится на все 512 сложений, таким образом каждое сложение несёт только 1/512 большой цены конечного «обычного» сложения.

Недостатки

На каждой стадии сложения с сохранением переноса,

Мы знаем результат сложения сразу.
Мы всё ещё не знаем является ли результат сложения больше или меньше чем данное число (например, мы не знаем является ли оно положительным или отрицательным).

Этот последний пункт является недостатком, когда используются сумматоры с сохранением переноса для выполнения модульного умножения (умножения следующего за делением, сохраняя только остаток). Если мы не можем знать является ли промежуточный результат больше или меньше чем модули, как мы можем знать вычитать модули или нет?

Умножение Монтгомери, которое зависит от самой правой цифры результата, является одним из решений; которое более похоже на само сложение с сохранением переноса, оно несёт постоянные накладные расходы, так что последовательность умножений Монтгомери экономит время но одиночное нет. К счастью, возведение в степень, которое фактически является последовательностью умножений, является наиболее частой операцией в криптографии с открытым ключом.

Технические детали

Устройство с сохранением переноса состоит из n полных сумматоров, каждый из которых вычисляет одноразрядную сумму и бит переноса основанные полностью на соответствующих битах трёх входных чисел. Из данных трёх n-битных чисел a, b и c, он производит частную сумму ps и сдвинутый перенос sc:

ps_{i}=a_{i}\oplus b_{i}\oplus c_{i}

sc_{i}=(a_{i}\wedge b_{i})\vee (a_{i}\wedge c_{i})\vee (b_{i}\wedge c_{i})

Полная сумма может затем быть вычислена:

Сдвигом последовательности переноса sc влево на одно место.
Добавляя 0 слева от (наиболее значимого бита) последовательности частной суммы ps.
Используя сумматор с последовательным переносом для сложения этих двух вместе и производства результирующей n + 1-битной величины.

Когда складываются вместе три или более числа, использование сумматора с сохранением переноса с последующим последовательным сумматором является более быстрым, чем использование двух сумматоров с последовательным переносом. Это происходит потому, что последовательный сумматор не может вычислить сумму битов без ожидания вычисления предыдущего бита переноса, и таким образом имеет задержку равную что и в n полных сумматорах. Сумматор с сохранением переноса вычисляет все свои выходные величины параллельно, и таким образом имеет ту же задержку что и один полный сумматор. Таким образом общее время вычисления (в единицах времени задержки полного сложения) для сумматора с сохранением переноса плюс сумматор с последовательным переносом равно n + 1, в то время как для двух последовательных сумматоров оно должно быть 2n.

См. также

Сумматор

Примечания

↑ Earle, J. G. et al U.S. Patent 3 340 388 «Latched Carry Save Adder Circuit for Multipliers» filed July 12, 1965
↑ Earle, J. (March, 1965), "Latched Carry-Save Adder", IBM Technical Disclosure Bulletin, 7 (10): 909—910 {{citation}}: Проверьте значение даты: |date= (справка)
↑ John von Neumannn, Collected Works.

[1] Earle, J. G. et al U.S. Patent 3 340 388 «Latched Carry Save Adder Circuit for Multipliers» filed July 12, 1965

[2] Earle, J. (March, 1965), "Latched Carry-Save Adder", IBM Technical Disclosure Bulletin, 7 (10): 909—910 {{citation}}: Проверьте значение даты: |date= (справка)

[3] John von Neumannn, Collected Works.

[1]

[2]

[3]