WikiDer > Сумматор Carry-save - Википедия

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

Мотивация

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

   12345678+  87654322= 100000000

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

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

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

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

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

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

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

  10111010101011011111000000001101 (а) + 11011110101011011011111011101111 (б) + 10010010101101110101001101010010 (в)

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

  10111010101011011111000000001101+ 11011110101011011011111011101111+ 00010010101101110101001101010010= 21132130303123132223112112112222

Обозначения нестандартные, но результат однозначный. Здесь результат будет описан как сумма двух двоичных чисел:

  01110110101101110001110110110000 и 100110101010110111110010010011110

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

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

Аккумуляторы Carry-save

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

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

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

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

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

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

Недостатки

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

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

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

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

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

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

Устройство защиты от переноски состоит из п полные сумматоры, каждый из которых вычисляет один бит суммы и переноса исключительно на основе соответствующих битов трех входных чисел. Учитывая три п-битовые числа а, б, и c, он дает частичную сумму пс и сменный перенос 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 впереди (старший бит) последовательности частичных сумм пс.
3. Используя гадюка чтобы сложить эти два вместе и получить результат (п + 1) -битное значение.

Смотрите также

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

Примечания

Рекомендации

дальнейшее чтение

• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.