Сумматор с функцией сохранения переноса

Сумматор с сохранением переноса ^{[1] [2] [nb 1]} — это тип цифрового сумматора , используемый для эффективного вычисления суммы трех или более двоичных чисел. Он отличается от других цифровых сумматоров тем, что выводит два (или более) числа, а ответ исходного суммирования может быть получен путем сложения этих выходов. Сумматор с сохранением переноса обычно используется в двоичном умножителе, поскольку двоичный умножитель включает сложение более двух двоичных чисел после умножения. Большой сумматор, реализованный с использованием этой техники, обычно будет намного быстрее, чем обычное сложение этих чисел.

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

 12345678+ 87654322= 100000000

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

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

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

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

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

Сумма двух цифр никогда не может нести больше 1, и сумма двух цифр плюс 1 также никогда не может нести больше 1. Например, в десятичной системе, , которая несет 1; , которая также несет 1. При сложении трех цифр мы можем сложить первые две и получить сумму и переносимые цифры; затем сложить сумму и переносимые цифры с третьей цифрой и получить сумму и переносимые цифры. В двоичной системе единственными цифрами являются ноль и единица, и поэтому , , и с переносимой 1. Добавление бита переноса может дать максимум с переносимой 1, поэтому возможно трехстороннее сложение. Из-за этого также возможно сложить первые три цифры и получить сумму и перенос; для последующих цифр сумма и перенос являются двумя членами, и следующая одиночная цифра добавляется к ним.${\displaystyle 9+9=18}$${\displaystyle 9+9+1=19}$${\displaystyle 0+0=0}$${\displaystyle 0+1=1}$${\displaystyle 1+1=0}$${\displaystyle 1+1+1=1}$

Вот пример двоичной суммы трех длинных двоичных чисел:

 1011 1010 1010 1101 1111 0000 0000 1101 (а)+ 1101 1110 1010 1101 1011 1110 1110 1111 (б)+ 0001 0010 1011 0111 0101 0011 0101 0010 (с)

Самый простой способ сделать это — сначала вычислить (a+b), а затем вычислить ((a+b)+c). Арифметика с сохранением переноса работает, отказываясь от любого вида распространения переноса. Она вычисляет сумму цифра за цифрой, как:

 1011 1010 1010 1101 1111 0000 0000 1101 (а)+ 1101 1110 1010 1101 1011 1110 1110 1111 (б)+ 0001 0010 1011 0111 0101 0011 0101 0010 (с)= 2113 2130 3031 2313 2223 1121 1211 2222

Обозначение нетрадиционное, но результат все равно однозначен: Σ2 ⁱ d _i . Если мы предположим, что три числа — это a, b и c. Тогда здесь результат будет описан как сумма двух двоичных чисел, где первое число, S, — это просто сумма, полученная путем сложения цифр (без какого-либо переноса), т. е. S _i = a _i ⊕ b _i ⊕ c _i , а второе число, C, состоит из переносов из предыдущих отдельных сумм, т. е. C _i+1 = (a _i b _i ) + (b _i c _i ) + (c _i a _i ) :

 0111 0110 1011 0111 0001 1101 1011 0000 и 1 0011 0101 0101 1011 1110 0100 1001 1110

Теперь эти 2 числа можно отправить в сумматор с переносом и распространением, который выведет результат.

Это было очень выгодно с точки зрения задержки (времени вычисления). Если бы вы сложили эти 3 числа, используя обычные методы, вам потребовалось бы 2 задержки сумматора распространения переноса, чтобы получить ответ. Если вы используете технику сохранения переноса, вам потребуется только 1 задержка сумматора распространения переноса и 1 задержка полного сумматора (что намного меньше задержки распространения переноса). Таким образом, CSA обычно очень быстры.

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

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

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

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

Поскольку сигналам не нужно проходить такое большое расстояние, часы могут идти гораздо быстрее.

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

На каждом этапе добавления «перенос-сохранение»,

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

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

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

Тщательный анализ ошибок ^[6] позволяет сделать выбор относительно вычитания модуля, даже если мы не знаем наверняка, достаточно ли велик результат сложения, чтобы оправдать вычитание. Чтобы это работало, необходимо, чтобы схема могла складывать −2, −1, 0, +1 или +2 модуля. Преимущество перед умножением Монтгомери заключается в том, что нет фиксированных накладных расходов, прикрепленных к каждой последовательности умножений.

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

${\displaystyle ps_{i}=a_{i}\oplus b_{i}\oplus c_{i},}$

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

Тогда всю сумму можно вычислить следующим образом:

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

• дерево Уоллеса

• Savard, John JG (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .