НАКАПЛИВАЮЩИЙ СУММАТОР ПО МОДУЛЮ

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в криптографических приложениях.

Известен накапливающий сумматор (Тарабрин Б.В. Справочник по интегральным микросхемам / Б.В. Тарабрин, С.В. Якубовский, Н.А. Барканов и др. Под ред. Б.В. Тарабрина. - 2-е изд., перераб. и доп. - М.: Энергия, 1981., рис.5-250, стр.741), содержащий 3 сумматора и 3 регистра.

Недостатком данного сумматора является ограниченные функциональные возможности, а именно отсутствие операции суммирования по модулю.

Наиболее близким по технической сущности к заявляемому изобретению является накопительный сумматор, содержащий регистр и сумматор (Наумкина Л.Г. Цифровая схемотехника. Конспект лекций по дисциплине «Схемотехника» - М.: «Горная книга». Издательство Московского государственного горного университета, 2008, рис.6.9, стр.228).

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

Цель изобретения - расширение функциональных возможностей устройства за счет введения операции суммирования по модулю.

Для достижения поставленной цели в накапливающий сумматор по модулю, содержащий n-разрядный сумматор и n-разрядный регистр, причем вторые информационные входы сумматора являются информационными входами устройства, а информационные выходы регистра являются информационными выходами устройства и соединены с первыми информационными входами n-разрядного сумматора, тактовый вход регистра является тактовым входом устройства, вход обнуления регистра является входом обнуления устройства, а вход переноса n-разрядного сумматора является входом переноса устройства, введены (n+1)-разрядный сумматор и n-разрядный мультиплексор, причем 1…n информационные выходы n-разрядного сумматора соединены с первыми 1…n информационными входами (n+1)-разрядного сумматора и вторыми 1…n информационными входами мультиплексора, выход переноса n-разрядного сумматора соединен с первым (n+1) информационным входом (n+1)-разрядного сумматора, вторые 1…n+1 информационные входы которого являются входами кода модуля в инверсном виде, на вход переноса (n+1)-разрядного сумматора подается логическая единица, выход переноса (n+1)-разрядного сумматора соединен с управляющим входом мультиплексора, а 1…n информационные выходы соединены с первыми 1…n информационными входами мультиплексора, информационные выходы которого соединены со входами записи регистра.

Сущность изобретения заключается в реализации следующего способа накопительного суммирования чисел А_i по модулю Р. Поступающие на вход накапливающего сумматора целые числа A_i (i=1,2,3,…), 0≤А_i<Р, потактово суммируются с числами, записанными в его памяти на предыдущем такте. До первого такта память устройства обнулена. Результат суммирования A_i+A_i-1 приводится по модулю Р следующим образом. Если (S=A_i+A_i-1)<P, то выполняется обычное суммирование S=A_i+A_i-1 и эта сумма S является результатом. Если же (S=A_i+A_i-1)≥P, а по исходному условию сумма S не может превышать 2Р-2, то из суммы S вычитается значение Р и результат является суммой (A_i+A_i-1) mod P. Полученный результат записывается в память устройства и на следующем такте используется в качестве значения числа A_i-1.

На фиг.1 представлена схема накапливающего сумматора по модулю.

Накапливающий сумматор по модулю содержит 2 сумматора 1 и 2, причем сумматор 1 является n-разрядным, а сумматор 2 является (n+1)-разрядным, мультиплексор 3 и регистр 4. На вход 5 последовательно, синхронно с тактовыми импульсами, подаваемыми на вход 9, подается последовательность чисел А_i, на вход 6 подается нулевой сигнал, на вход 7 подается код модуля в инверсном виде, на вход 8 подается логическая единица, вход 10 служит для обнуления накапливающего сумматора перед началом работы. Выход 11 является выходом устройства. Выходы регистра 4 соединены с выходом 11 устройства и с первыми входами сумматора 1, выходы сумматора 1 соединены с первыми входами сумматора 2 и вторыми входами мультиплексора 3. Информационные выходы сумматора 2 соединены с первыми входами мультиплексора 3, а выход переноса сумматора 2 - с управляющим входом мультиплексора 3. Выходы мультиплексора 3 соединены со входами записи регистра 4. Входы 5 подачи кода числа устройства соединены со вторыми информационными входами сумматора 1.

Накапливающий сумматор по модулю работает следующим образом.

Перед началом работы на вход 10 устройства подается импульс, который обнуляет содержимое регистра 4. На вход 9 устройства поступают тактовые импульсы, которые синхронизируют работу устройства. С каждым тактовым импульсом на вход 5 поступают коды чисел А_i, поступающие на входы (В₁…В_n) сумматора 1. Разрядность входного числа равна n. На первые входы сумматора 1 поступает код числа с выхода элемента памяти устройства - регистра 4. На первом такте таким числом является «0». С выхода сумматора 1 код суммы поступает на первые входы сумматора 2 и на вторые входы (Y₁…Y_n) мультиплексора 3. На вторые входы сумматора 2 (B₁…B_n+1) поступает инверсный код модуля, а на вход переноса 8 - логическая единица. Сумматор 2 выполняет операцию вычитания из кода числа, поступающего с выхода сумматора 1, кода модуля Р, поступающего со входа 7 устройства. В случае, если уменьшаемое число больше или равно Р, на выходах сумматора 2 (S₁…S_n) появится разность чисел, а на выходе переноса Р_О сумматора 2 появится логическая единица, которая поступает на управляющий вход мультиплексора 3, под воздействием которой на выход мультиплексора будут скоммутированы вторые входы (Y₁…Y_n). Если же уменьшаемое число меньше Р, то на выходе переноса Р_О образуется нулевой сигнал, и на выходы мультиплексора будут скоммутированы его первые входы (Х₁…X_n). Под воздействием тактового импульса число с выхода мультиплексора записывается в регистр 4. Данное число на следующем такте работы выступает в качестве первого слагаемого А, в сумматоре 1 и результата вычисления S на данном такте, поступающего на выход 11 устройства. Таким образом, на каждом такте работы в регистре формируется сумма всех поступивших на предыдущих тактах чисел А_i по модулю Р.