НАКАПЛИВАЮЩИЙ СУММАТОР ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ Российский патент 2025 года по МПК G06F7/501 G06F7/72 

Область техники, к которой относится изобретение

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

Уровень техники

Известен накапливающий сумматор, содержащий 3 сумматора и 3 регистра с соответствующими связями, позволяющий выполнять накапливающее суммирование чисел, поступающих на его вход по модулю 2ⁿ [1].

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

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

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

Техническим результатом изобретения является уменьшение объема оборудования.

Раскрытие сущности изобретения

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

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

Краткое описание чертежей

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

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

Первые информационные входы 9 устройства соединены со входами переноса n полных одноразрядных сумматоров 1.1÷1.n, вторые информационные входы устройства соединены со вторыми информационными входами n полных одноразрядных сумматоров 1.1÷1.n и с (1…n)-ми разрядами вторых информационных входов (n+1)-разрядного мультиплексора 3, информационные выходы n-разрядного регистра 8 соединены с информационными выходами 11 устройства, с первыми информационными входами n полных одноразрядных сумматоров 1.1÷1.n и со вторыми информационными входами n-разрядного мультиплексора 2, c первыми информационными входами которого соединены информационные выходы n полных одноразрядных сумматоров 1.1÷1.n, выходы переноса которых соединены со (2…(n+1))-м разрядом первых информационных входов (n+1)-разрядного мультиплексора 3 соответственно, информационные выходы n-разрядного мультиплексора 2 соединены (1…n)-м разрядом первых информационных входов (n+1)-разрядного сумматора 4, информационные выходы (n+1)-разрядного мультиплексора 3 соединены со вторыми информационными входами (n+1)-разрядного сумматора 4, (1…n)-е разряды информационных выходов которого соединены с информационными входами n-разрядного регистра 8 и со входами n-входового элемента «ИЛИ» 7, а (n+1)-й разряд соединен со входом элемента «НЕ» 6, выход которого соединен с первым входом элемента «2И-НЕ» 5, второй вход которого соединен с выходом n-входового элемента «ИЛИ» 7, а выход соединен с управляющим входом n-разрядного мультиплексора 2 и с управляющим входом (n+1)-разрядного мультиплексора 3.

На первые информационные входы 9 устройства подается дополнительный код модуля Р_д. На вторые информационные входы 10 устройства подаются коды чисел A_i. Искомая сумма S_i снимается с информационных выходов 11 устройства.

Осуществление изобретения

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

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

С началом работы устройства на первые информационные входы 9 устройства подается в двоичном виде дополнительный код модуля Р_д, который поступает на входы переноса полных одноразрядных сумматоров 1.1÷1.n. На тактовый вход 12 устройства поступают тактовые импульсы. С каждым тактовым импульсом i = 1, 2, 3,…, на вторые 10 информационные входы устройства подаются в двоичном виде коды чисел A_i, 0 ≤ А_i < Р, значения соответствующих разрядов которых поступают на вторые информационные входы полных одноразрядных сумматоров 1.1÷1.n и на вторые информационные входы (n+1)-разрядного мультиплексора 3. На первые информационные входы полных одноразрядных сумматоров 1.1÷1.n поступают с информационных выходов n-разрядного регистра 8, являющихся информационными выходами 11 устройства, значения соответствующих разрядов суммы S_i−1. На первом такте S₀ = 0. На выходах каждого из сумматоров n полных одноразрядных сумматоров 1.1÷1.n формируется сигнал частичной суммы S^/_i и сигналы сквозного переноса, трех чисел, поступающих на их входы. В результате на информационных выходах полных одноразрядных сумматоров 1.1÷1.n образуются поразрядные сигналы частичной суммы S^/_i, а на выходах переноса образуются поразрядные сигналы сквозного переноса. Сигналы частичной суммы с информационных выходов полных одноразрядных сумматоров 1.1÷1.n через скоммутированные первые информационные входы n-разрядного мультиплексора 2 поступают на (1…n)-е разряды первых информационных входов (n+1)-разрядного сумматора 4. Сигналы с выходов переноса полных одноразрядных сумматоров 1.1÷1.n через скоммутированные первые информационные входы (n+1)-разрядного мультиплексора 3 поступают на вторые информационные входы (n+1)-разрядного сумматора 4. В результате на выходах (n+1)-разрядного сумматора 4 образуется значение (A_i + S_i−1) + Р_д.

В случае, если (A_i + S_i−1) + Р_д ≥ Р, то на (n+1)-м разряде (n+1)-разрядного сумматора 4 образуется сигнал логической единицы, который, проходя через элемент «НЕ» 6, будет поддерживать на выходе элемента «2И-НЕ» 5 сигнал логической единицы. При этом на (1…n)-м разрядах информационных выходов (n+1)-разрядного сумматора 4 образуется сумма S^/_i, которая и является искомой суммой S_i чисел (A_i + S_i−1) по модулю P. Под воздействием тактового импульса сумма S_i запишется в n-разрядный регистр 8 и поступит на информационные выходы 11 устройства.

В случае, если (A_i + S_i−1) + Р_д < Р, то на (n+1)-м разряде (n+1)-разрядного сумматора 4 остается нулевой сигнал, который, проходя через элемент «НЕ» 6, поступает в виде единичного сигнала на первый вход элемента «2И-НЕ» 5. На второй вход элемента «2И-НЕ» 5 с выхода n-входового элемента «ИЛИ» 7 также поступает сигнал логической единицы, в результате чего на выходе элемента «2И-НЕ» 5 образуется нулевой сигнал, который поступит на управляющие входы n-разрядного мультиплексора 2 и (n+1)-разрядного мультиплексора 3. В результате n-разрядный мультиплексор 2 и (n+1)-разрядный мультиплексор 3 скоммутируют со своими выходами свои вторые информационные входы. При этом на первых информационных входах (n+1)-разрядного сумматора 4 окажется значение S_i−1, а на его вторых информационных входах окажется значение A_i. При этом на выходах (n+1)-разрядного сумматора 4 образуется сумма, которая и является искомой суммой S_i чисел (A_i + S_i−1) по модулю P. Под воздействием тактового импульса сумма S_i запишется в n-разрядный регистр 8 и поступит на информационные выходы 11 устройства.

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

Объем оборудования прототипа V_пр составляет

V _пр = V_SMn + V_SMn1 + V_Mn + V_RGn, (1)

где - объем оборудования n-разрядного сумматора;

– объем оборудования (n+1)-разрядного сумматора;

– объем оборудования n-разрядного мультиплексора;

– объем оборудования n-разрядного регистра;

n - разрядность устройства.

При префиксном варианте исполнения сумматоров объем оборудования относительно элементарных логических элементов будет пропорционален величинам

Объем оборудования мультиплексора V_Mn и регистра V_RGn будет пропорционален величинам

Подставляя (2), (3), (4) и (5) в (1), получим

Объем оборудования предложенного решения V_из составляет

где V_SM1 - объем оборудования полного одноразрядного сумматора;

- объем оборудования n-разрядного мультиплексора;

- объем оборудования (n+1)-разрядного мультиплексора;

- объем оборудования (n+1)-разрядного сумматора;

- объем оборудования n-разрядного регистра.

Объем оборудования полного одноразрядного сумматора V_SM1 будет пропорционален величине

V _SM1=5n. (8)

Объем оборудования (n+1)-разрядного мультиплексора V_Mn1 будет пропорционален величине

Подставляя (3), (4), (5), (8) и (9) в (7), получим

V _из=2 (n +1) log (n+1) + 14n+5. (10)

Тогда выигрыш B в объеме оборудования при использовании предложенного решения по отношению к прототипу составит

B=(2(n log n + (n +1) log (n+1)) + 7n) / (2(n +1) log (n+1) + 14n+5). (11)

Выигрыш B в объеме оборудования при увеличении разрядности будет увеличиваться, так, например, при разрядности устройства n=16 выигрыш B в объеме оборудования составит 3%, при разрядности устройства n=32, B=12%, а при n=64, B=19%.

Источники информации

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

2. Петренко В.И., Кузьминов Ю.В. Накапливающий сумматор по модулю // Патент РФ №2500017. Опубл. 27.11.2013. Бюл. № 33.

Изобретение относится к вычислительной технике. Технический результат заключается в уменьшении объема используемого оборудования. Накапливающий сумматор по произвольному модулю содержит n-разрядный мультиплексор, (n+1)-разрядный сумматор, n-разрядный регистр, первые и вторые информационные входы устройства, информационные выходы устройства, тактовый вход устройства, вход синхронизации n-разрядного регистра, вход установки устройства в начальное состояние, вход сброса n-разрядного регистра, n полных одноразрядных сумматоров, (n+1)-разрядный мультиплексор, элемент «2И-НЕ», элемент «НЕ», n-входовый элемент «ИЛИ». 1 ил.

Накапливающий сумматор по произвольному модулю, содержащий n-разрядный мультиплексор, (n+1)-разрядный сумматор, n-разрядный регистр, где n - разрядность устройства, первые и вторые информационные входы устройства, информационные выходы устройства, тактовый вход устройства, соединенный со входом синхронизации n-разрядного регистра, вход установки устройства в начальное состояние, соединенный со входом сброса n-разрядного регистра, информационные выходы которого соединены с информационными выходами устройства, отличающийся тем, что в него введены n полных одноразрядных сумматоров, (n+1)-разрядный мультиплексор, элемент «2И-НЕ», элемент «НЕ», n-входовый элемент «ИЛИ», причем первые информационные входы устройства соединены со входами переноса n полных одноразрядных сумматоров, вторые информационные входы устройства соединены со вторыми информационными входами n полных одноразрядных сумматоров и с (1…n)-ми разрядами вторых информационных входов (n+1)-разрядного мультиплексора, информационные выходы n-разрядного регистра соединены с первыми информационными входами n полных одноразрядных сумматоров и со вторыми информационными входами n-разрядного мультиплексора, c первыми информационными входами которого соединены информационные выходы n полных одноразрядных сумматоров, выходы переноса которых соединены со (2…(n+1))-м разрядом первых информационных входов (n+1)-разрядного мультиплексора соответственно, информационные выходы n-разрядного мультиплексора соединены (1…n)-м разрядом первых информационных входов (n+1)-разрядного сумматора, информационные выходы (n+1)-разрядного мультиплексора соединены со вторыми информационными входами (n+1)-разрядного сумматора, (1…n)-е разряды информационных выходов которых соединены с информационными входами n-разрядного регистра и со входами n-входового элемента «ИЛИ», а (n+1)-й разряд соединен со входом элемента «НЕ», выход которого соединен с первым входом элемента «2И-НЕ», второй вход которого соединен с выходом n-входового элемента «ИЛИ», а выход соединен с управляющим входом n-разрядного мультиплексора и с управляющим входом (n+1)-разрядного мультиплексора.