Перенос сохранить сумматор [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, чтобы позволить возможному переносу распространиться с одного конца числа к другому. Пока мы этого не сделаем,
- Результат сложения нам неизвестен.
- Мы не знаем, больше или меньше результат сложения заданного числа (например, мы не знаем, положительный он или отрицательный).
Переносов вперед сумматор может уменьшить задержку. В принципе, задержка может быть уменьшена так, чтобы она была пропорциональна log n , но для больших чисел это уже не так, потому что даже при использовании упреждающего переноса расстояния, которые сигналы должны пройти по микросхеме, увеличиваются пропорционально до n , и задержки распространения увеличиваются с той же скоростью. Как только мы перейдем к размерам чисел от 512 до 2048 бит, которые требуются в криптографии с открытым ключом , упреждающий перенос уже не очень помогает.
Основная концепция
Идея отложить разрешение переноса до конца или сохранить перенос переноса принадлежит Джону фон Нейману . [3]
Вот пример двоичной суммы трех длинных двоичных чисел:
10111010101011011111000000001101 (а)+ 11011110101011011011111011101111 (б)+ 00010010101101110101001101010010 (с)
Обычный способ сделать это - сначала вычислить (a + b), а затем вычислить ((a + b) + c). Арифметика с сохранением переноса работает за счет отказа от любого вида распространения переноса. Он вычисляет сумму цифру за цифрой, как:
10111010101011011111000000001101+ 11011110101011011011111011101111+ 00010010101101110101001101010010= 21132130303123132223112112112222
Обозначения нестандартные, но результат однозначный. Если мы предположим, что три числа - это a, b и c. Тогда здесь результат будет описан как сумма 2 двоичных чисел, где первое число 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 ):
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.
Другими словами, мы берем цифру переноса из позиции справа и передаем цифру переноса слева, как при обычном сложении; но цифра переноса, которую мы передаем слева, является результатом предыдущего вычисления, а не текущего. В каждом тактовом цикле переносчики должны двигаться только на один шаг, а не на n шагов, как при обычном сложении.
Поскольку сигналы не должны двигаться так далеко, часы могут идти намного быстрее. ..
По-прежнему существует необходимость в преобразовании результата в двоичный формат в конце вычисления, что фактически означает просто позволить переносчикам пройти весь путь через число, как в обычном сумматоре. Но если мы выполнили 512 сложений в процессе выполнения 512-битного умножения, стоимость этого окончательного преобразования фактически распределяется между этими 512 сложениями, поэтому каждое добавление покрывает 1/512 стоимости этого окончательного «обычного» сложения.
Недостатки
На каждом этапе добавления сохранения при переносе
- Мы сразу знаем результат сложения.
- Мы все еще не знаем , больше или меньше результат сложения заданного числа (например, мы не знаем, положительный он или отрицательный).
Этот последний момент является недостатком при использовании сумматоров с сохранением переноса для реализации модульного умножения (умножение с последующим делением с сохранением только остатка). [4] [5] Если мы не можем знать, больше или меньше промежуточный результат модуля, как мы можем узнать, нужно ли вычесть модуль?
Умножение Монтгомери , которое зависит от самой правой цифры результата, является одним из решений; хотя, скорее, как само сложение с сохранением переноса, оно несет фиксированные накладные расходы, так что последовательность умножений Монтгомери экономит время, а одно - нет. К счастью, возведение в степень, которое, по сути, представляет собой последовательность умножений, является наиболее распространенной операцией в криптографии с открытым ключом.
Тщательный анализ ошибок [6] позволяет сделать выбор в отношении вычитания модуля, даже если мы не знаем наверняка, является ли результат сложения достаточно большим, чтобы оправдать вычитание. Для того, чтобы это работало, необходимо, чтобы схема могла добавлять −2, −1, 0, +1 или +2, умноженные на модуль. Преимущество перед умножением Монтгомери состоит в том, что к каждой последовательности умножений не прилагаются фиксированные накладные расходы.
Технические подробности
Блок сохранения переноса состоит из n полных сумматоров , каждый из которых вычисляет одну сумму и бит переноса, основываясь исключительно на соответствующих битах трех входных чисел. Учитывая три n -битных числа a , b и c , он производит частичную сумму ps и перенос sc :
Затем всю сумму можно рассчитать следующим образом:
- Сдвиг последовательности переноса sc влево на одно место.
- Добавление 0 к началу ( старший бит ) последовательности частичной суммы ps .
- Используя сумматор с переносом пульсации, сложите эти два и получите результирующее ( n + 1) -битное значение.
Смотрите также
Заметки
- ^ Сумматор с сохранением переноса часто обозначается сокращенно как CSA, однако его можно спутать с сумматором с пропуском переноса .
Рекомендации
- ^ Эрл, Джон Г. (1965-07-12), Схема сумматора с фиксированным переносом и сохранением для умножителей , Патент США 3,340,388
- ^ Эрл, Джон Г. (март 1965 г.), «Сумматор с фиксированным переносом и сохранением», Технический бюллетень IBM , 7 (10): 909–910
- ^ фон Нейман, Джон . Собрание сочинений .
- ^ Пархами, Бехруз (2010). Компьютерная арифметика: алгоритмы и аппаратные разработки (2-е изд.). Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-532848-6. OCLC 428033168 .
- ^ Ляхов, П .; Валуева, М .; Валуев, Г .; Нагорнов, Н. (2020). «Высокопроизводительная цифровая фильтрация усеченных многократно-накапливаемых единиц в системе счисления остатков» . Доступ IEEE . 8 : 209181–209190. DOI : 10,1109 / ACCESS.2020.3038496 . ISSN 2169-3536 .
- ^ Кочанский, Мартин (19 августа 2003 г.). "Новый метод последовательного модульного умножения" (PDF) . Архивировано из оригинального (PDF) 16 июля 2018 года . Проверено 16 июля 2018 .
дальнейшее чтение
- Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . квадиблок . Архивировано 3 июля 2018 года . Проверено 16 июля 2018 .