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

Abstract

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

Description

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

Известен накапливающий сумматор (Тарабрин Б.В. Справочник по интегральным микросхемам/Б.В. Тарабрин, С.В. Якубовский, Н.А. Барканов и др.; под ред. Б.В. Тарабрина – 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 осуществляется параллельно, в отличие от устройства-прототипа, где эти операции выполняются последовательно.

Claims (1)

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

Images