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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов, в криптографических приложениях и в системах управления. Устройство содержит n-разрядный сумматор, n одноразрядных сумматоров, (n+1)-разрядный сумматор, мультиплексор и параллельный регистр. Техническим результатом является повышение быстродействия устройства. Технический результат предлагаемого изобретения достигается за счет того, что вычисление (A_i+Q_i-1) и (A_i+Q_i-1)-P осуществляется параллельно, в отличие от устройства-прототипа, где эти операции выполняются последовательно. 1 ил.

 

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

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

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

Наиболее близким по технической сущности к заявляемому изобретению является накапливающий сумматор по модулю, содержащий n-разрядный и (n+1)-разрядный сумматоры, мультиплексор и регистр (Патент RU 2500017 С1. Накапливающий сумматор по модулю. Опубликован 27.11.2013. Бюл. № 33).

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

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

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

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

На первые информационные входы 6 устройства последовательно, синхронно с тактовыми импульсами, подаваемыми на тактовый вход 8, подаются коды последовательности чисел А_i (i=1, 2, 3,…), . Эти входы соединены со вторым входом (В₁…B_n) n-разрядного сумматора 1 и вторыми входами n одноразрядных сумматоров 2.1 — 2.n. На вход переноса P_i сумматора 1 подается нулевой сигнал. На вторые информационные входы 7 устройства подается код модуля Р в инверсном виде, который соединён со входами переносов P_i n одноразрядных сумматоров 2. Вход 9 устройства служит для обнуления устройства перед началом работы. Выход 10 является выходом Q устройства. Выходы регистра 5 (Q₁…Q_n) соединены с выходом 10 устройства, с первыми входами (A₁…A_n) n-разрядного сумматора 1 и первыми входами n одноразрядных сумматоров 2.1 — 2.n. Выходы сумматора 1 (S₁…S_n) соединены с первыми входами (X₁…X_n) мультиплексора 4. Информационные выходы n одноразрядных сумматоров 2.1 — 2.n соединены с первым информационным входом (A₁…A_n) (n+1)-разрядного сумматора 3. Выходы переноса n одноразрядных сумматоров 2.1 — 2.n соединены со вторым информационным входом (В₂…B_n+1) (n+1)-разрядного сумматора 3 со сдвигом на один разряд в сторону старшего, на самый младший разряд вторых информационных входов (n+1)-разрядного сумматора 3 В₁ и на его самый старший разряд первых информационных входов A_n+1 подается сигнал логического нуля. На вход переноса P_i (n+1)-разрядного сумматора 3 подаётся логическая единица. Младшие n информационных выходов (n+1)-разрядного сумматора 3 (S₁…S_n) соединены со вторыми входами (Y₁…Y_n) мультиплексора 4, а выход переноса P_o – с управляющим входом V мультиплексора 4. Выходы мультиплексора 4 (Q₁…Q_n) соединены со входами записи (D₁…D_n) регистра 5.

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

Перед началом работы на вход сброса 9 устройства подается импульс, который обнуляет содержимое параллельного регистра 5. На тактовый вход 8 устройства поступают тактовые импульсы, которые синхронизируют работу устройства. С каждым тактовым импульсом на первые информационные входы 6 поступают коды чисел А_i (i=1, 2, 3,…), , поступающие далее на вторые информационные входы (В₁…B_n) сумматора 1 и вторые информационные входы B n одноразрядных сумматоров 2.1 — 2.n. На вход переноса P_i n-разрядного сумматора 1 подается нулевой сигнал. Разрядность входных чисел A_i равна n. На первые входы сумматора 1 (A₁…A_n) и n одноразрядных сумматоров 2.1 — 2.n поступает код числа с выхода (Q₁…Q_n) параллельного регистра 5. На первом такте таким числом является «0». С информационного выхода (S₁…S_n) n-разрядного сумматора 1 код суммы поступает на первые входы (X₁…X_n) мультиплексора 4. На входы переноса P_i n одноразрядных сумматоров 2.1 — 2.n поступает инверсный код модуля P. Цепь из n одноразрядных сумматоров 2.1 — 2.n и (n+1)-разрядного сумматора 3 выполняет операцию вычитания из кода числа, являющегося суммой чисел, поступающих с первых информационных входов 6 устройства и информационного выхода (Q₁…Q_n) параллельного регистра 5, кода модуля Р, поступающего со входа 7 устройства. В случае, если уменьшаемое число больше или равно Р, на выходах (n+1)-разрядного сумматора 3 (S₁…S_n) появится разность чисел, а на выходе переноса P_o (n+1)-разрядного сумматора 3 появится логическая единица, которая поступает на управляющий вход V мультиплексора 4, под воздействием которой на выход мультиплексора 4 будут скоммутированы его вторые информационные входы (Y₁…Y_n). Если же уменьшаемое число меньше Р, то на выходе переноса P_o образуется нулевой сигнал и на выходы мультиплексора 4 (Q₁…Q_n) будут скоммутированы его первые информационные входы (Х₁…Х_n). Под воздействием тактового импульса код числа с выхода мультиплексора 4 (Q₁…Q_n) записывается в регистр 5. Данное число на следующем такте работы выступает в качестве первого слагаемого A_i в n-разрядном сумматоре 1 и цепи, состоящей из n одноразрядных сумматоров 2.1 — 2.n и (n+1)-разрядного сумматора 3 и результата вычисления Q на данном такте, поступающего на выход 10 устройства. Таким образом, на каждом такте работы в регистре 5 формируется сумма всех поступивших на предыдущих тактах чисел A_i по модулю Р.

Повышение быстродействия предлагаемого устройства достигается за счет того, что вычисление (A_i+Q_i-1) и (A_i+Q_i-1)-P осуществляется параллельно, в отличие от устройства-прототипа, где эти операции выполняются последовательно.

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