14-10-2023
Это заготовка статьи. Вы можете помочь проекту, исправив и дополнив её. Это примечание по возможности следует заменить более точным. |
Сумматор с сохранением переноса[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, чтобы позволить переносу распространиться от одного конца числа до другого. Пока мы делаем это,
Сумматор с ускоренным переносом может уменьшить задержку. В принципе, задержка может быть уменьшена так, что она будет пропорциональна logn, но для больших чисел это уже не тот случай, потому что даже когда применяется ускоренный перенос, расстояние, которое сигнал проходит по чипу увеличивается пропорционально n и задержка распространения возрастает в этом же отношении. Как только мы получим числа с размерами от 512-битов до 2048-битов, которые требуются в криптосистемах с открытым ключом, ускоренный перенос более не помогает.
Мысль задержки разрешения переноса до конца, или сохранения переносов, принадлежит Джону фон Нейману. [3]
Здесь приведён пример двоичного сложения:
10111010101011011111000000001101
.
+ 11011110101011011011111011101111
Арифметика с сохранением переноса работает покидая двоичную запись, всё ещё оставаясь работать по основанию 2. Она вычисляет сумму цифра за цифрой, как
10111010101011011111000000001101
.
+ 11011110101011011011111011101111
= 21122120202022022122111011102212
Запись является нетрадиционной, но результат остаётся однозначным. Более того, данными n сумматорами (здесь, n = 32 полных сумматора), результат может быть вычислен за один такт генератора, так как каждая цифра результата не зависит от какой либо другой.
Если сумматор требуется для того, чтобы сложить два числа и вычислить результат, сложение с сохранением переноса является непригодным, так как результат остаётся конвертируемым назад в двоичный и это означает что переносы распространились справа налево. Но в арифметике больших целых, сложение является очень редкой операцией, и сумматоры с сохранением переноса обычно используются, для накопления частных сумм в умножителе.
Предположим, что мы имеем два бита памяти на каждую цифру результата, тогда мы можем использовать избыточное двоичное представление, запоминая величины 0, 1, 2 или 3 в каждой цифровой позиции. Это происходит потому, что к нашему результату с сохранением переноса может быть добавлено более одного двоичного числа без переполнения ёмкости нашей памяти: но потом что?
Ключом к пониманию является то, что за время каждого частичного сложения мы складываем три бита:
Другими словами, мы берём цифру переноса из позиции справа, и переносим цифру переноса налево, также как и в традиционном сложении; но цифра переноса, которую мы передаём налево является результатом предыдущего вычисления, а не текущего. За каждый такт генератора, переносы сдвигаются только на один шаг вперёд, а не на n шагов, как в традиционном сложении.
Так как сигналы перемещаются не так далеко, генератор может тикать более быстро.
Остаётся необходимость преобразовать результат в двоичный в конце вычисления, которое фактически просто означает разрешение переносам проходить весь путь через число также как и в традиционном сумматоре. Но если мы сделали 512 сложений в процессе выполнения 512-битного умножения, цена этого конечного преобразования фактически делится на все 512 сложений, таким образом каждое сложение несёт 1/512 цены конечного "обычного" сложения.
На каждой стадии сложения с сохранением переноса,
Этот последний пункт является недостатком, когда используются сумматоры с сохранением переноса для выполнения модульного умножения (умножения следующего за делением, сохраняя только остаток). Если мы не можем знать является ли промежуточный результат больше или меньше чем модули, как мы можем знать вычитать модули или нет?
Умножение Монтгомери, которое зависит от самой правой цифры результата, является одним из решений; которое более похоже на само сложение с сохранением переноса, оно несёт постоянные накладные расходы, так что последовательность умножений Монтгомери экономит время но одиночное нет. К счастью, возведение в степень, которое фактически является последовательностью умножений, является наиболее частой операцией в криптографии с открытым ключом.
Устройство с сохранением переноса состоит из n полных сумматоров, каждый из которых вычисляет одноразрядную сумму и бит переноса основанные полностью на соответствующих битах трёх входных чисел. Из данных трёх n-битных чисел a, b и c, он производит частную сумму ps и сдвинутый перенос sc:
Полная сумма может затем быть вычислена:
Когда складываются вместе три или более числа, использование сумматора с сохранением переноса с последующим последовательным сумматором является более быстрым, чем использование двух сумматоров с последовательным переносом. Это происходит потому, что последовательный сумматор не может вычислить сумму битов без ожидания вычисления предыдущего бита переноса, и таким образом имеет задержку равную что и в n полных сумматорах. Сумматор с сохранением переноса вычисляет все свои выходные величины параллельно, и таким образом имеет ту же задержку что и один полный сумматор. Таким образом общее время вычисления (в единицах времени задержки полного сложения) для сумматора с сохранением переноса плюс сумматор с последовательным переносом равно n + 1, в то время как для двух последовательных сумматоров оно должно быть 2n.
Сумматор с сохранением переноса.