Многоразрядный сумматор по модулю Российский патент 2024 года по МПК G06F7/72 

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

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

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

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

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

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

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

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

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

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

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

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

Сущность изобретения заключается в реализации следующего способа суммирования чисел 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, n полных одноразрядных сумматоров 2.1÷2.n, (n+1)-разрядный сумматор 3, где n-разрядность устройства, элемент «2И-НЕ» 4, n-входовый элемент «ИЛИ» 5, первые 6, вторые 7 и третьи 8 информационные входы устройства, информационные выходы 9 устройства.

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

На первые информационные входы 6 устройства подается дополнительный код модуля P. Одновременно с этим на вторые 7 и третьи 8 информационные входы устройства подаются коды чисел A и B. Искомая сумма S чисел A и B снимается с информационных выходов 9 устройства.

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

Многоразрядный сумматор по модулю работает следующим образом (см. Фиг. 1).

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

С началом работы устройства на первые информационные входы 6 устройства подается в двоичном виде дополнительный код модуля
P_д, который через открытый n-разрядный ключ 1 поступает на входы переноса полных одноразрядных сумматоров 2.1÷2.n. На вторые 7 и на третьи 8 информационные входы устройства подаются в двоичном виде коды операндов суммирования A и B соответственно, которые соответственно поступают на вторые и первые информационные входы полных одноразрядных сумматоров 2.1÷2.n. На выходах каждого из сумматоров n полных одноразрядных сумматоров 2.1÷2.n формируется сигнал частичной суммы S^/ и сигналы сквозного переноса, трех чисел, поступающих на их входы. В результате на информационных выходах полных одноразрядных сумматоров 2.1÷2.n образуются поразрядные сигналы частичной суммы, а на выходах переноса образуются поразрядные сигналы сквозного переноса. Сигналы частичной суммы S^/ с информационных выходов полных одноразрядных сумматоров 2.1÷2.n поступают на (1…n)-й разряды первых информационных входов (n+1)-разрядного сумматора 3, на (n+1)-й разряд которого поступает сигнал логической единицы с выхода элемента «2И-НЕ» 4. Сигналы с выходов переноса полных одноразрядных сумматоров 2.1÷2.n поступают на (2…(n+1))-й разряды вторых информационных входов (n+1)-разрядного сумматора 3. В результате на выходах (n+1)-разрядного сумматора 3 образуется значение S = (A + B) + P_д, где P_д – дополнительный код модуля.

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

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

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

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

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

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

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

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

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

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

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