Сумматор переноса-сохранения [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]
Сумма двух цифр никогда не может содержать больше 1, а сумма двух цифр плюс 1 также никогда не может содержать больше 1. Например, в десятичной системе счисления , которая содержит 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 i 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 ) + (ci a i ) :
0111 0110 1011 0111 0001 1101 1011 0000 и 1 0011 0101 0101 1011 1110 0100 1001 1110
Теперь эти два числа можно отправить в сумматор переноса и распространения, который выведет результат.
Это было очень выгодно с точки зрения задержки (времени вычислений). Если бы вы сложили эти три числа обычными методами, вам потребовались бы две задержки сумматора переноса-распространения, чтобы получить ответ. Если вы используете метод переноса-сохранения, вам потребуется только 1 задержка суммирования переноса и 1 полная сумматорная задержка (что намного меньше, чем задержка распространения переноса). Таким образом, CSA обычно работают очень быстро.
Предположим, что у нас есть два бита памяти на цифру, мы можем использовать избыточное двоичное представление , сохраняя значения 0, 1, 2 или 3 в каждой позиции цифры. Поэтому очевидно, что к нашему результату переноса-сохранения можно добавить еще одно двоичное число, не переполняя емкость нашей памяти: но что тогда?
Залог успеха в том, что в момент каждого частичного сложения мы добавляем три бита:
Другими словами, мы берем цифру переноса из позиции справа и передаем цифру переноса влево, как при обычном сложении; но цифра переноса, которую мы передаем влево, является результатом предыдущего вычисления, а не текущего. За каждый такт переносам нужно пройти только один шаг, а не n шагов, как при обычном сложении.
Поскольку сигналам не нужно перемещаться так далеко, часы могут идти намного быстрее. ..
По-прежнему необходимо преобразовать результат в двоичный формат в конце вычислений, что фактически означает, что переносы перемещаются по всему числу, как в обычном сумматоре. Но если мы сделали 512 сложений в процессе выполнения 512-битного умножения, стоимость этого окончательного преобразования фактически распределяется между этими 512 сложениями, поэтому каждое сложение несет 1/512 стоимости этого окончательного «обычного» сложения.
На каждом этапе сложения переноса-сохранения
Этот последний момент является недостатком при использовании сумматоров с переносом-сохранением для реализации модульного умножения (умножение с последующим делением, сохраняя только остаток). [4] [5] Если мы не можем знать, больше или меньше промежуточный результат модуля, как мы можем узнать, следует ли вычитать модуль?
Умножение Монтгомери , которое зависит от крайней правой цифры результата, является одним из решений; хотя, как и само сложение переноса-сохранения, оно несет фиксированные накладные расходы, так что последовательность умножений Монтгомери экономит время, а одно - нет. К счастью, возведение в степень, которое фактически представляет собой последовательность умножений, является наиболее распространенной операцией в криптографии с открытым ключом.
Тщательный анализ ошибок [6] позволяет сделать выбор в пользу вычитания модуля, даже если мы не знаем наверняка, достаточно ли велик результат сложения, чтобы оправдать вычитание. Чтобы это работало, необходимо, чтобы в схемотехнике была возможность прибавлять модуль в -2, -1, 0, +1 или +2 раза. Преимущество по сравнению с умножением Монтгомери состоит в том, что к каждой последовательности умножений не применяются фиксированные накладные расходы.
Блок переноса-сохранения состоит из n полных сумматоров , каждый из которых вычисляет одну сумму и бит переноса исключительно на основе соответствующих битов трех входных чисел. Учитывая три n -битных числа a , b и c , он создает частичную сумму ps и сдвиг-перенос sc :
Всю сумму затем можно вычислить по формуле: