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

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

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

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

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

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

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

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

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

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

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

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

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

Сущность изобретения заключается в реализации следующего способа суммирования чисел A и B по модулю P. Пусть A и B целые неотрицательные числа, соответственно являются первым и вторым операндами суммирования

; , (1)

; , (2)

где n – разрядность чисел. Пусть P – модуль, по которому проводится суммирование

, P≥2. (3)

Пусть S – сумма чисел A и B по модулю P

(4)

; . (5)

При сложении двух чисел, представленных в виде двоичных кодов A(a_n-1, …, a₀) и B(b_n-1, ..., b₀) образуется сумма С(с_n, ..., с₀), равная . Способ суммирования двух чисел A и B по модулю P заключается в том, что вначале находят значение разности
С(с_n, ..., с₀) – P(p_n-1, …, p₀). Если полученное значение больше или равно нулю, то оно и является искомой суммой

S(s_n-1,…, s₀) = С(с_n, ..., с₀) – P(p_n-1, …, p₀). (6)

Если же полученное значение меньше нуля, то осуществляется повторное суммирование чисел A и B и искомой суммой S является сумма этих чисел

S(s_n-1,…, s₀) = A(a_n-1, ..., a₀) + B(b_n-1, ..., b₀). (7)

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

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

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

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

На первые информационные входы 8 устройства подается инверсный код модуля P. На вторые 9 и третьи 10 информационные входы устройства подаются коды чисел A и B. На управляющий вход 11 устройства в течение выполнения операции суммирования подается сигнал логической единицы. Искомая сумма S чисел A и B снимается с информационных выходов 12 устройства.

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

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

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

С началом работы устройства на первые информационные входы 8 устройства подается в двоичном виде инверсный код модуля P, который поступает на входы переноса полных одноразрядных сумматоров 1.1÷1.n. На вторые 9 и на третьи 10 информационные входы устройства подаются в двоичном виде коды операндов суммирования A и B соответственно, которые соответственно поступают на вторые и первые информационные входы полных одноразрядных сумматоров 1.1÷1.n и на вторые информационные входы второго 3 и первого 2 мультиплексоров. На управляющий вход 11 устройства в течение выполнения операции суммирования подается сигнал логической единицы, который поступает на первый разряд первых информационных входов второго мультиплексора и выполняет функцию дополнения единицы к инверсному коду модуля P, преобразуя его в дополнительный. На выходах каждого из сумматоров n полных одноразрядных сумматоров 1.1÷1.n формируется сигнал частичной суммы S^/ и сигналы сквозного переноса P_o, трех чисел, поступающих на их входы. В результате на информационных выходах полных одноразрядных сумматоров 1.1÷1.n образуются поразрядные сигналы частичной суммы, а на выходах переноса образуются поразрядные сигналы сквозного переноса. Сигналы частичной суммы S^/ с информационных выходов полных одноразрядных сумматоров 1.1÷1.n через первый мультиплексор 2 поступают на (1…n)-й разряды первых информационных входов (n+1)-разрядного сумматора 4. Сигналы с выходов переноса полных одноразрядных сумматоров 1.1÷1.n через второй мультиплексор 3 поступают на вторые информационные входы (n+1)-разрядного сумматора 4. В результате на информационных выходах (n+1)-разрядного сумматора 3 образуется значение S = (A + B) + P_д, где P_д – дополнительный код модуля.

В случае, если , то на (n+1)-м разряде информационных выходов (n+1)-разрядного сумматора 4 образуется сигнал логической единицы, который, поступая через элемент «НЕ» 6 на первый вход элемента «2И-НЕ» 5, будет поддерживать на его выходе сигнал логической единицы, оставляя скоммутированными первые информационные входы первого 2 и второго 3 мультиплексоров с их информационными выходами. При этом на (1…n)-м разрядах информационных выходов (n+1)-разрядного сумматора 4 образуется искомая сумма S чисел A и B по модулю P, , которая поступает на информационные выходы устройства 12.

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

После получения результата суммирования чисел A и B по модулю P на информационных выходах 12 устройства, устройство переводится в нулевое состояние и процесс суммирования может быть возобновлён с другими исходными данными.

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

Анализ работы прототипа и предложенного решения показывает, что в управляющих цепях прототипа сигнал управления дополнительно формируется RS-триггером, который вносит временную задержку в работу прототипа. Исключение RS-триггера из цепи распространения сигнала позволит повысить быстродействие устройства, а также дополнительно уменьшить энергопотребление и повысить надежность работы.

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

1. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. – М.: Радио и связь, 1990. Рисунок 3.45, с.133.

2. Петренко В.И., Степанян Н.Э., Нелидин Ю.Р. Многоразрядный параллельный сумматор по модулю с последовательным переносом // Патент РФ № 2724597. Опубл. 25.06.2020. Бюл. № 18.

3. Петренко В.И., Пуйко Д.Д. Многоразрядный сумматор по модулю // Патент РФ № 2804379. Опубл. 28.09.2023. Бюл. № 28.

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

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