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

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

Мотивация

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

   12345678
+  87654322
= 100000000

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

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

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

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

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

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

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

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

  1011 1010 1010 1101 1111 0000 0000 1101 (a)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)

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

  1011 1010 1010 1101 1111 0000 0000 1101 (a)
+ 1101 1110 1010 1101 1011 1110 1110 1111 (b)
+ 0001 0010 1011 0111 0101 0011 0101 0010 (c)
= 2113 2130 3031 2313 2223 1121 1211 2222

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

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

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

Это было очень выгодно с точки зрения задержки (времени вычислений). Если бы вы сложили эти три числа обычными методами, вам потребовались бы две задержки сумматора переноса-распространения, чтобы получить ответ. Если вы используете метод переноса-сохранения, вам потребуется только 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 стоимости этого окончательного «обычного» сложения.

Недостатки

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

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

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

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

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

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

Блок переноса-сохранения состоит из 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)-битного значения.

См. также

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

Примечания

^ Сумматор с переносом-сохранением часто обозначается сокращенно CSA, однако его можно спутать с сумматором с пропуском переноса .

Ссылки

^ Эрл, Джон Г. (12 июля 1965 г.), Сумматорная схема с сохранением переноса и сохранением данных для умножителей , патент США 3,340,388
^ Эрл, Джон Г. (март 1965 г.), «Сумматор с фиксацией переноса и сохранения», Бюллетень технической информации IBM , 7 (10): 909–910
^ фон Нейман, Джон . Собрание сочинений .
^ Пархами, Бехруз (2010). Компьютерная арифметика: алгоритмы и аппаратные средства (2-е изд.). Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-532848-6 . OCLC 428033168 .
^ Ляхов П.; Валуева, М.; Валуев Г.; Нагорнов, Н. (2020). «Высокопроизводительная цифровая фильтрация по усеченным множественно-накопляющим единицам в системе счисления остатков» . Доступ IEEE . 8 : 209181–209190. дои : 10.1109/ACCESS.2020.3038496 . ISSN 2169-3536 .
^ Кочански, Мартин (19 августа 2003 г.). «Новый метод последовательного модульного умножения» (PDF) . Архивировано из оригинала (PDF) 16 июля 2018 г. Проверено 16 июля 2018 г.

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

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

[NB_CSA-3] Сумматор с переносом-сохранением часто обозначается сокращенно CSA, однако его можно спутать с сумматором с пропуском переноса .

[Earle_1965_1-1] Эрл, Джон Г. (12 июля 1965 г.), Сумматорная схема с сохранением переноса и сохранением данных для умножителей , патент США 3,340,388

[Earle_1965_2-2] Эрл, Джон Г. (март 1965 г.), «Сумматор с фиксацией переноса и сохранения», Бюллетень технической информации IBM , 7 (10): 909–910

[Neumann-4] фон Нейман, Джон . Собрание сочинений .

[5] Пархами, Бехруз (2010). Компьютерная арифметика: алгоритмы и аппаратные средства (2-е изд.). Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-532848-6 . OCLC 428033168 .

[6] Ляхов П.; Валуева, М.; Валуев Г.; Нагорнов, Н. (2020). «Высокопроизводительная цифровая фильтрация по усеченным множественно-накопляющим единицам в системе счисления остатков» . Доступ IEEE . 8 : 209181–209190. дои : 10.1109/ACCESS.2020.3038496 . ISSN 2169-3536 .

[encrypt-7] Кочански, Мартин (19 августа 2003 г.). «Новый метод последовательного модульного умножения» (PDF) . Архивировано из оригинала (PDF) 16 июля 2018 г. Проверено 16 июля 2018 г.

[1]

[2]

[номер 1]

[3]

[4]

[5]

[6]