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

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

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

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

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

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

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

Недостатком данного устройства является низкое быстродействие, вызванное использованием последовательного переноса и выполнением операции суммирования чисел A и B по произвольному модулю P для случаев, когда (A + B) < P двойным проходом.

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

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

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

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

Для достижения технического результата в сумматор групповой структуры по произвольному модулю с последовательным переносом, содержащий первые информационные входы устройства, вторые информационные входы устройства, третьи информационные входы устройства, выход переноса устройства, вход переноса устройства, вход переноса модуля устройства, информационные выходы устройства, введены k n-разрядных сумматоров по модулю, где n - разрядность i-го n-разрядного сумматора по модулю, i = 1, …, k, m = k·n - разрядность устройства, при этом первые информационные входы устройства соединены соответствующими группами по n-разрядов с первыми информационными входами k n-разрядных сумматоров по модулю, вторые информационные входы устройства соединены соответствующими группами по n-разрядов со вторыми информационными входами k n-разрядных сумматоров по модулю, третьи информационные входы устройства соединены соответствующими группами по n-разрядов с третьими информационными входами k n-разрядных сумматоров по модулю, информационные выходы k n-разрядных сумматоров по модулю соединены с соответствующими группами по n-разрядов информационных выходов устройства, вход переноса устройства соединен со входом переноса первого n-разрядного сумматора по модулю, вход переноса модуля устройства соединен со входом переноса модуля первого n-разрядного сумматора по модулю, выход переноса k-го n-разрядного сумматора по модулю соединен с выходом переноса устройства, выход переноса модуля k-го n-разрядного сумматора по модулю соединен с управляющими входами k n-разрядных сумматоров по модулю, выходы переноса (1, …, k-1)-го n-разрядных сумматоров по модулю соединены со входами переноса (2, …, k)-го n-разрядных сумматоров по модулю, выходы переноса модуля (1, …, k-1)-го n-разрядных сумматоров по модулю соединены со входами переноса модуля (2, …, k)-го n-разрядных сумматоров по модулю, причем n-разрядный сумматор по модулю содержит n - полных одноразрядных сумматоров, (n+1)-разрядный сумматор, n-разрядный сумматор и мультиплексор, информационные выходы которого соединены с информационными выходами n-разрядного сумматора по модулю, вход переноса n-разрядного сумматора соединен со входом переноса n-разрядного сумматора по модулю, а выход переноса соединен с выходом переноса n-разрядного сумматора по модулю, вход переноса (n+1)-разрядного сумматора соединен со входом переноса модуля n-разрядного сумматора по модулю, (n+1)-й разряд информационных выходов (n+1)-разрядного сумматора соединен с выходом переноса модуля n-разрядного сумматора по модулю, а (1, …, n)-й разряды информационных выходов соединены с первыми информационными входами мультиплексора, со вторыми информационными входами которого соединены информационные выходы n-разрядного сумматора, а управляющий вход соединен с управляющим входом n-разрядного сумматора по модулю, первые информационные входы которого соединены с первыми информационными входами n-разрядного сумматора и поразрядно с первыми информационными входами n полных одноразрядных сумматоров, вторые информационные входы соединены со вторыми информационными входами n-разрядного сумматора и поразрядно со вторыми информационными входами n полных одноразрядных сумматоров, а третьи информационные входы соединены поразрядно со входами переноса n полных одноразрядных сумматоров, информационные выходы которых соединены с (1, …, n)-м разрядами первых информационных входов (n+1)-разрядного сумматора, а выходы переноса соединены со (2, …, n+1)-м разрядами вторых информационных входов (n+1)-разрядного сумматора, на первый разряд которых подается сигнал логической единицы.

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

где A и B - неотрицательные целые числа, называемые соответственно первым и вторым слагаемым, причем,

P - неотрицательное целое число, называемое модулем, P ≥ 2;

S - неотрицательное целое число, являющееся суммой чисел A и B, приведенной по модулю P, при этом 0≤ S <P.

Все числа представлены в позиционной двоичной системе счисления.

где a_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа A;

b_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа B;

p_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля P;

s_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения суммы S;

m - количество разрядов в представлении чисел.

Разобьем число A в (3) на k групп по n разрядов:

Перепишем (7) в виде

Аналогичным образом представим числа B, P и S:

Введем следующие обозначения:

Тогда выражение (1) может быть переписано в следующем виде:

Операция вычитания в (13) может быть заменена операцией суммирования, если вместо прямого двоичного кода числа P использовать дополнительный двоичный код P_д:

При этом разряд переноса, формируемый при выполнении (15), дополнительно может использоваться для определения условия в (14): если (A + B) < P, то сигнал на выходе переноса будет отсутствовать, появление сигнала на выходе переноса означает, что (A + B) ≥ P.

По аналогии с (8) представим числа S_AB и S_ABP:

При этом с учетом (8) и (9) значения S_AB i в выражении (16) можно записать как:

где C_{i  i−1} - сигнал переноса из (i-1)-й группы.

Сигнал переноса, формируемый в i-й группе, обозначим через C_{out i}.

С учетом (8), (9) и (10) значения S_{ABP i} в выражении (17) можно записать как:

где CM_{in i−1} - сигнал переноса модуля из (i-1)-й группы, P_{д i} - представление модуля в дополнительном коде аналогично (10).

Сигнал переноса модуля, формируемый в i-й группе, обозначим через CM_{out i}.

Таким образом в каждой в i-й группе на основе A_i, B_i и P_{д i} с учетом C_{in i-1} и CM_{in i-1} вычисляются значения S_{AB i} и S_{ABP i}, а также формируются сигналы переноса C_{out i} и сигналы переноса модуля CM_{out i}.

Соединяя группы последовательно, таким образом, что C_{in i} = C_{ou  i−1} и CM_{in i} = CM_{ou  i-1}, а также используя сигнал переноса модуля CM_{ou  k} в k-й группе для управления выбором S_AB или S_ABP в соответствии с (14) получим структуру группового суммирования по модулю с последовательным переносом. Внутри группы суммирование может выполняться по любой схеме, например, с параллельным переносом или префиксное суммирование, что позволит увеличить быстродействие устройства в целом по сравнению с прототипом. Все внутригрупповые сумматоры могут иметь одинаковую структуру, что делает предложенное решение универсальным и масштабируемым.

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

На фиг. 1 представлена схема сумматора групповой структуры по произвольному модулю с последовательным переносом, содержащего k n-разрядных сумматоров по модулю 1.1÷1.k, где n - разрядность i-го n-разрядного сумматора по модулю 1.1÷1.k, i = 1, …, k, m = k·n - разрядность устройства, первые информационные входы 2 устройства, вторые информационные входы 3 устройства, третьи информационные входы 4 устройства, выход переноса 5 устройства, вход переноса 6 устройства, вход переноса модуля 7 устройства, информационные выходы 8 устройства.

Первые информационные входы 2 устройства соединены соответствующими группами по n-разрядов с первыми информационными входами k n-разрядных сумматоров по модулю 1.1÷1.k, вторые информационные входы 3 устройства соединены соответствующими группами по n-разрядов со вторыми информационными входами k n-разрядных сумматоров по модулю 1.1÷1.k, третьи информационные входы 4 устройства соединены соответствующими группами по n-разрядов с третьими информационными входами k n-разрядных сумматоров по модулю 1.1÷1.k, информационные выходы k n-разрядных сумматоров по модулю 1.1÷1.k соединены с соответствующими группами по n-разрядов информационных выходов 8 устройства, вход переноса 6 устройства соединен со входом переноса первого n-разрядного сумматора по модулю 1.1, вход переноса модуля 7 устройства соединен со входом переноса модуля первого n-разрядного сумматора по модулю 1.1, выход переноса k-го n-разрядного сумматора по модулю 1.k соединен с выходом переноса 5 устройства, выход переноса модуля k-го n-разрядного сумматора по модулю 1.k соединен с управляющими входами k n-разрядных сумматоров по модулю 1.1÷1.k, выходы переноса (1, …, k-1)-го n-разрядных сумматоров по модулю 1.1÷1.k-1 соединены со входами переноса (2, …, k)-го n-разрядных сумматоров по модулю 1.2÷1.k, выходы переноса модуля (1, …, k-1)-го n-разрядных сумматоров по модулю 1.1÷1.k-1 соединены со входами переноса модуля (2, …, k)-го n-разрядных сумматоров по модулю 1.2÷1.k.

На фиг. 2 представлена схема одного из n-разрядных сумматоров по модулю 1.1÷1.k, обозначенная как 1.i, и содержит n - полных одноразрядных сумматоров 9.1÷9.n, (n+1)-разрядный сумматор 10, n-разрядный сумматор 11 и мультиплексор 12.

Информационные выходы мультиплексора 12 соединены с информационными выходами n-разрядного сумматора по модулю 1.i, вход переноса n-разрядного сумматора 11 соединен со входом переноса n-разрядного сумматора по модулю 1.i, а выход переноса соединен с выходом переноса n-разрядного сумматора по модулю 1.i, вход переноса (n+1)-разрядного сумматора 10 соединен со входом переноса модуля n-разрядного сумматора по модулю 1.i, (n+1)-й разряд информационных выходов (n+1)-разрядного сумматора 10 соединен с выходом переноса модуля n-разрядного сумматора по модулю 1.i, а (1, …, n)-й разряды информационных выходов соединены с первыми информационными входами мультиплексора 12, со вторыми информационными входами которого соединены информационные выходы n-разрядного сумматора 11, а управляющий вход соединен с управляющим входом n-разрядного сумматора по модулю 1.i, первые информационные входы которого соединены с первыми информационными входами n-разрядного сумматора 11 и поразрядно с первыми информационными входами n полных одноразрядных сумматоров 9.1÷9.n, вторые информационные входы соединены со вторыми информационными входами n-разрядного сумматора 11 и поразрядно со вторыми информационными входами n полных одноразрядных сумматоров 9.1÷9.n, а третьи информационные входы соединены поразрядно со входами переноса n полных одноразрядных сумматоров 9.1÷9.n, информационные выходы которых соединены с (1, …, n)-м разрядами первых информационных входов (n+1)-разрядного сумматора 10, а выходы переноса соединены со (2, …, n+1)-м разрядами вторых информационных входов (n+1)-разрядного сумматора 10, на первый разряд которых подается сигнал логической единицы.

На первые информационные входы 2 устройства подается первое m-разрядное слагаемое A, на вторые информационные входы 3 устройства подается второе m-разрядное слагаемое B, на третьи информационные входы 4 устройства подается m-разрядный инверсный код модуля P. Искомая сумма S двух чисел A и B по модулю P снимается с информационных выходов 8 устройства. Выход переноса 5 устройства, вход переноса 6 устройства, вход переноса модуля 7 устройства служат для наращивания групп устройства.

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

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

С началом работы устройства на первые информационные входы 2 устройства подается первое m-разрядное слагаемое A, на вторые информационные входы 3 устройства подается второе m-разрядное слагаемое B, на третьи информационные входы 4 устройства подается m-разрядный инверсный код модуля P. С первых информационных входов 2 устройства m-разрядное число A подается группами по n разрядов, начиная с младших, на первые информационные входы n-разрядных сумматоров по модулю 1.1÷1.k. Аналогичным образом второе число B и модуль P подаются соответственно на вторые и третьи информационные входы n-разрядных сумматоров по модулю 1.1÷1.k. На первые информационные входы полных одноразрядных сумматоров 9.1÷9.n (см. Фиг. 2) n-разрядных сумматоров по модулю 1.1÷1.k поступают соответствующие разряды кода числа A, на вторые информационные входы поступают соответствующие разряды кода числа B, а на входы переноса поступают соответствующие разряды инверсного кода модуля P. На выходах каждого из сумматоров n полных одноразрядных сумматоров 9.1÷9.n формируется сигнал частичной суммы и сигналы сквозного переноса трех чисел, поступающих на их входы. В результате на информационных выходах полных одноразрядных сумматоров 9.1÷9.n образуются поразрядные сигналы частичной суммы, а на выходах переноса образуются поразрядные сигналы сквозного переноса. Сигналы частичной суммы с информационных выходов полных одноразрядных сумматоров 9.1÷9.n поступают на (1, …, n)-й разряды первых информационных входов (n+1)-разрядного сумматора 10, на (n+1)-й разряд которого подается сигнал логического нуля. Сигналы с выходов переноса полных одноразрядных сумматоров 9.1÷9.n поступают на (2, …, (n+1))-й разряды вторых информационных входов (n+1)-разрядного сумматора 10, на первый разряд которого поступает сигнал логической единицы, преобразуя инверсный код модуля в дополнительный. На вход переноса (n+1)-разрядного сумматора 10 из предыдущей группы поступает сигнал переноса модуля со входа переноса модуля n-разрядного сумматора по модулю 1.i. В результате на информационных выходах (n+1)-разрядного сумматора 10 образуется значение суммы в соответствии с (19), причем значение формируемое на (n+1)-м разряде информационных выходах (n+1)-разрядного сумматора 10 является сигналом переноса модуля и подается на выход переноса модуля соответствующего n-разрядного сумматора по модулю 1,i, поступая далее в следующую группу суммирования в качестве входного сигнала переноса модуля. На первые информационные входы мультиплексора 12 поступают значения с первых n разрядов информационных входов (n+1)-разрядного сумматора 10. На первые информационные входы n-разрядного сумматора 11 поступают соответствующие разряды числа A, на вторые информационные входы поступают соответствующие разряды числа B, а на вход переноса из предыдущей группы поступает сигнал переноса со входа переноса модуля n-разрядного сумматора по модулю 1.i. На информационных выходах n-разрядного сумматора 11 образуется значение суммы в соответствии с (18), а на выходе переноса образуется сигнал переноса, который подается на выход переноса соответствующего n-разрядного сумматора по модулю 1.i, поступая далее в следующую группу суммирования в качестве входного сигнала переноса. Значение суммы с информационных выходов n-разрядного сумматора 11 поступает на вторые информационные входы мультиплексора 12. Таким образом k n-разрядных сумматоров по модулю 1.1÷1.k в каждой группе одновременно вычисляют значения слагаемых в (16) и в (17) с последовательным переносом сигналов переноса для (16) и сигналов переноса модуля для (17). В случае, если (A + B) ≥ P, то на выходе переноса модуля k-го n-разрядного сумматора по модулю 1.k образуется сигнал логической единицы, который поступая на управляющие входы n-разрядных сумматоров по модулю 1.1÷1.k и далее на управляющие входы мультиплексоров 12, скоммутирует с информационными выходами мультиплексоров 12 их первые информационные входы, в результате на информационные выходы 8 устройства поступит значение суммы в соответствии с (13), которая и будет являться искомой суммой. Если же (A + B) < P, то на выходе переноса модуля k-го n-разрядного сумматора по модулю 1.k образуется сигнал логического нуля, под воздействием которого с информационными выходами мультиплексоров 12 окажутся скоммутированы их вторые информационные входы, в результате на информационные выходы 8 устройства поступит значение суммы в соответствии с (12), которая и будет являться искомой суммой в этом случае.

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

Время задержки суммирования прототипом T_пр составляет

где t₁ - время задержки суммирования полным одноразрядным сумматором;

t _лэ - время задержки суммирования базовым логическим элементом,

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

С учетом того, что

выражение (20) примет вид

Время задержки суммирования предлагаемым устройством T_из составит

где k - количество групп сумматоров в устройстве; T_мод - время задержки суммирования n-разрядного сумматора по модулю 1.i, определяемое как

где t₁ - время задержки суммирования полным одноразрядным сумматором;

t_{n +1} - время задержки суммирования (n+1)-разрядным сумматором 10;

t _лэ - время задержки суммирования базовым логическим элементом.

Реализация (n+1)-разрядного сумматора 10 и n-разрядного сумматора 11 в префиксном варианте позволит получить

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

С учетом (21), (24) и (25), выражение (23) примет вид

Тогда выигрыш в быстродействии с учетом того, что m = k·n, составит

Объединяя группы, например, по n=8 разрядов, получим выигрыш в быстродействии B=4,17.

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

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

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

3. Копытов В.В., Петренко В.И., Сидорчук А.В. Многоразрядный параллельный сумматор по модулю с последовательным переносом // Патент РФ № 2439661. Опубл. 10.08.2011. Бюл. № 22.

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

Сумматор групповой структуры по произвольному модулю с последовательным переносом, содержащий первые информационные входы устройства, вторые информационные входы устройства, третьи информационные входы устройства, выход переноса устройства, вход переноса устройства, вход переноса модуля устройства, информационные выходы устройства, отличающийся тем, что в него введены k n-разрядных сумматоров по модулю, где n – разрядность i-го n-разрядного сумматора по модулю, i=1, …, k, m=k·n – разрядность устройства, при этом первые информационные входы устройства соединены соответствующими группами по n разрядов с первыми информационными входами k n-разрядных сумматоров по модулю, вторые информационные входы устройства соединены соответствующими группами по n разрядов со вторыми информационными входами k n-разрядных сумматоров по модулю, третьи информационные входы устройства соединены соответствующими группами по n разрядов с третьими информационными входами k n-разрядных сумматоров по модулю, информационные выходы k n-разрядных сумматоров по модулю соединены с соответствующими группами по n разрядов информационных выходов устройства, вход переноса устройства соединен со входом переноса первого n-разрядного сумматора по модулю, вход переноса модуля устройства соединен со входом переноса модуля первого n-разрядного сумматора по модулю, выход переноса k-го n-разрядного сумматора по модулю соединен с выходом переноса устройства, выход переноса модуля k-го n-разрядного сумматора по модулю соединен с управляющими входами k n-разрядных сумматоров по модулю, выходы переноса (1, …, k−1)-го n-разрядных сумматоров по модулю соединены со входами переноса (2, …, k)-го n-разрядных сумматоров по модулю, выходы переноса модуля (1, …, k−1)-го n-разрядных сумматоров по модулю соединены со входами переноса модуля (2, …, k)-го n-разрядных сумматоров по модулю, причем n-разрядный сумматор по модулю содержит n полных одноразрядных сумматоров, (n+1)-разрядный сумматор, n-разрядный сумматор и мультиплексор, информационные выходы которого соединены с информационными выходами n-разрядного сумматора по модулю, вход переноса n-разрядного сумматора соединен со входом переноса n-разрядного сумматора по модулю, а выход переноса соединен с выходом переноса n-разрядного сумматора по модулю, вход переноса (n+1)-разрядного сумматора соединен со входом переноса модуля n-разрядного сумматора по модулю, (n+1)-й разряд информационных выходов (n+1)-разрядного сумматора соединен с выходом переноса модуля n-разрядного сумматора по модулю, а (1, …, n)-й разряды информационных выходов соединены с первыми информационными входами мультиплексора, со вторыми информационными входами которого соединены информационные выходы n-разрядного сумматора, а управляющий вход соединен с управляющим входом n-разрядного сумматора по модулю, первые информационные входы которого соединены с первыми информационными входами n-разрядного сумматора и поразрядно с первыми информационными входами n полных одноразрядных сумматоров, вторые информационные входы соединены со вторыми информационными входами n-разрядного сумматора и поразрядно со вторыми информационными входами n полных одноразрядных сумматоров, а третьи информационные входы соединены поразрядно со входами переноса n полных одноразрядных сумматоров, информационные выходы которых соединены с (1, …, n)-м разрядами первых информационных входов (n+1)-разрядного сумматора, а выходы переноса соединены со (2, …, n+1)-м разрядами вторых информационных входов (n+1)-разрядного сумматора, на первый разряд которых подается сигнал логической единицы.