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

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

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

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

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

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

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

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

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

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

Сущность изобретения заключается в реализации следующего способа накопительного суммирования чисел по модулю в двухканальном режиме. Суммирование чисел A_1,i первого канала осуществляется по модулю P₁, образуя накопленную сумму S_1,i. Суммирование чисел A_2,i второго канала осуществляется по модулю P₂, образуя накопленную сумму S_2,i. В общем виде накопленные суммы S_k,i по модулям P_k на выходах каналов на i-ых тактах могут быть описаны следующим рекуррентным выражением:

S_{k , i} = (S_k,i−2 + А_k,i−1) mod P_k, i=1, 2, 3, 4, 5,…; k=1, 2; (1)

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

i - номер такта накопительного суммирования;

А_{k , i} - входное число k-го канала на i-м такте, причем 0 ≤ А_k,i < P_k, при этом будем считать, что А_k,0=0;

S_{k , i} - выходная сумма k-го канала на i-м такте, причем 0 ≤ S_k,i < P_k; при этом будем считать, что S_k,-1=0, S_k,0=0 и S_k,1=0;

P_k, - модуль для k-го канала, по которому осуществляется накопительное суммирование.

Частота следования входных чисел А_k,i и выходной суммы S_k,i в каждом из каналов в два раза меньше тактовой частоты накопительного суммирования. В первом канале входные числа А_1,i считываются на нечетных тактах накопительного суммирования А_1,1, А_1,3, А_1,5, …, а выходная сумма S_1,i формируется по модулю P₁ на четных тактах накопительного суммирования S_1,2, S_1,4, S_1,6, …  . Во втором канале входные числа А_2,i считываются на четных тактах накопительного суммирования А_2,2, А_2,4, А_2,6, …, а выходная сумма S_2,i формируется по модулю P₂ на нечетных тактах накопительного суммирования S_2,3, S_2,5, S_2,7, … . Таким образом:

S _{1, i +1} = (S_1,i−1 + А_1,i) mod P₁, i=1, 3, 5, …; (2)

S _{2, i +1} = (S_2,i−1 + А_2,i) mod P₂, i=2, 4, 6,… . (3)

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

Для реализации каждого этапа накапливающий сумматор имеет ячейку памяти и двоичный сумматор. Первая ячейка памяти имеет размерность 2n, где n - разрядность входных чисел, а вторая ячейка памяти имеет размерность (n + 1). Первая ячейка памяти на каждом такте сохраняет входные числа А_k,i разрядностью n, выходные числа S_1,i на четном такте и выходные числа S_2,i на нечетном такте разрядностью n.

Вторая ячейка памяти сохраняет в течение очередного такта сумму (S_1,i + A_1,i) на четном такте и сумму (S_2,i + A_2,i) на нечетном такте. На выходе второй ячейки памяти осуществляется приведение по модулю P_k суммы (S_k,i + A_k,i), где k=1,2. Если указанная сумма больше модуля P_k, соответственно производится вычитание из нее этого модуля, в противном случае сумма без изменения поступает на выход устройства.

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

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

Сущность изобретения поясняется чертежами.

На фиг. 1 представлена схема двухканального накапливающего сумматора по модулю. Двухканальный накапливающий сумматор по модулю содержит 2n-разрядный 3 и (n+1)-разрядный 5 регистры, где n - разрядность обрабатываемых чисел, n-разрядный 4 и (n+1)-разрядный 6 сумматоры, первый мультиплексор 7, второй мультиплексор 1, триггер 2, демультиплексор 8, первые 12, вторые 9 и третьи 10 информационные входы устройства, тактовый вход устройства 11, первые 13 и вторые 14 информационные выходы устройства. Первые информационные входы второго мультиплексора 1 соединены со вторыми информационными входами устройства 9, вторые информационные входы соединены с третьими информационными входами устройства 10, информационные выходы соединены с младшими n разрядами информационных входов 2n-разрядного регистра 3, тактовый вход устройства 11 соединён c тактовыми входами 2n-разрядного регистра 3, (n+1)-разрядного регистра 5 и со входом триггера 2, выход которого соединён с управляющим входом второго мультиплексора 1 и с управляющим входом демультиплексора 8, первые информационные выходы которого соединены с первыми информационными выходами устройства 13, а вторые информационные выходы со вторыми информационными выходами устройства 14, информационные входы соединены с информационными выходами первого мультиплексора 7 и со старшими n разрядами информационных входов 2n-разрядного регистра 3, младшие n разрядов информационных выходов которого соединены с первыми информационными входами n-разрядного сумматора 4, а старшие n разрядов информационных выходов соединены со вторыми информационными входами n-разрядного сумматора 4, информационные выходы которого соединены с n младшими разрядами информационных входов (n+1)-разрядного регистра 5, а выход переноса соединён с (n+1)-м разрядом информационных входов (n+1)-разрядного регистра 5, младшие n разрядов информационных выходов которого соединены с младшими n разрядами вторых информационных входов (n+1)-разрядного сумматора 6 и со вторыми информационными входами первого мультиплексора 7, (n+1)-й разряд информационных выходов соединён с (n+1)-м разрядом вторых информационных входов (n+1)-разрядного сумматора 6. Первые n разрядов первых информационных входов (n+1)-разрядного сумматора 6 соединены с первыми информационными входами устройства 12, на (n+1)-й разряд первых информационных входов и на вход переноса подаётся сигнал логической единицы, первые информационные входы первого мультиплексора 7 соединены с первыми n разрядами информационных выходов (n +1)-разрядного сумматора 6, управляющий вход соединён с выходом переноса (n+1)-разрядного сумматора 6.

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

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

В исходном состоянии 2n-разрядный и (n+1)-разрядный регистры 3 и 5 обнулены. На тактовый вход устройства 11 поступают тактовые импульсы i=1, 2, 3, …. На первые информационные входы устройства 12 на чётных тактах подаётся инверсный код модуля P₁, а на нечётных тактах (начиная с 3) подаётся инверсный код модуля P₂. На вторые информационные входы устройства 9 подаются числа первого канала A_1,i, а на третьи информационные входы устройства 10 подаются числа второго канала A_2,i. Сумма S_1,i+1 по модулю P₁ для чисел A_i (i=1, 3, 5,…) снимается с первых информационных выходов устройства 13, а сумма S_2,i+1 по модулю P₂ для чисел A_i (i=2, 4, 6, …) снимается со вторых информационных выходов устройства 14. Причем, 0≤ A_1,i < P₁ и 0≤A_2,i < P₂.

На первом такте работы устройства первое n-разрядное число A_1,1 со вторых информационных входов 9 устройства поступает на первые информационные входы второго мультиплексора 1, которые под воздействием нулевого сигнала с выхода триггера 2 оказываются скоммутированными с его информационными выходами. Под воздействием первого тактового импульса число A_1,1 запишется в младшие n разрядов 2n-разрядного регистра 3, при этом в старшие n разрядов этого регистра запишется нулевое значение с информационных выходов первого мультиплексора 7. В (n+1)-разрядный регистр 5 под воздействием этого же тактового импульса запишется с выхода n-разрядного сумматора 4 ноль. В результате на первом такте в 2n-разрядном регистре 3 будет записано значение числа A_1,1, а в (n+1)-разрядном регистре 5 будет записано нулевое значение, которое поступит на вторые информационные входы (n+1)-разрядного сумматора 6 и на вторые информационные входы первого мультиплексора 7. Так как на выходе переноса (n+1)-разрядного сумматора 6 сигнал переноса будет отсутствовать, то с информационными выходами первого мультиплексора 7 будут скоммутированы его вторые информационные входы. В результате на этих информационных выходах будет нулевой сигнал, который к началу следующего такта будет воздействовать на старшие n-разрядов информационных входов 2n-разрядного регистра 3. При этом по окончании действия первого тактового импульса триггер 2 будет переведен в единичное состояние и информационные входы демультиплексора 8 под воздействием единичного сигнала с выхода триггера 2 окажутся скоммутированы с его вторыми информационными выходами, которые соединены со вторыми информационными выходами 14 устройства. С информационными выходами второго мультиплексора 1 окажутся скоммутированы его вторые информационные входы, которые соединены с третьими информационными входами 10 устройства.

На втором такте работы устройства второе n-разрядное число A_2,2 с третьих информационных входов 10 устройства поступает на вторые информационные входы второго мультиплексора 1. Под воздействием второго тактового импульса число A_2,2 запишется в младшие n разрядов 2n-разрядного регистра 3, при этом в старшие n разрядов этого регистра запишется нулевое значение с информационных выходов первого мультиплексора 7. В (n+1)-разрядный регистр 5 под воздействием второго тактового импульса запишется с выхода n-разрядного сумматора 4 значение A_1,1+0. В результате на втором такте в 2n-разрядном регистре 3 будет записано значение числа A_2,2, а в (n+1)-разрядном регистре 5 будет записано значение A_1,1, которое поступит на вторые информационные входы (n+1)-разрядного сумматора 6 и на вторые информационные входы первого мультиплексора 7. На первые информационные входы (n+1)-разрядного сумматора 6 с первых информационных входов 12 устройства в этот момент будет поступать инверсный код модуля P₁. Так как по определению A_1,1<P₁, то на выходе переноса (n+1)-разрядного сумматора 6 будет нулевой сигнал, по воздействием которого на выходы первого мультиплексора 7 будут скоммутированы его вторые информационные входы. В результате на выходах мультиплексора 7 окажется значение A_1,1. По окончании действия второго тактового импульса триггер 2 будет переведен в нулевое состояние. При этом информационные входы демультиплексора 8 под воздействием нулевого сигнала с выхода триггера 2 окажутся скоммутированы с его первыми информационными выходами, которые соединены со первыми информационными выходами 13 устройства. В результате, в соответствии с (2) на первых информационных выходах 13 устройства образуется первое значение накаливающей суммы первого канала:

S _1,2 = (0 + А_1,1) mod P₁. (4)

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

На третьем такте работы устройства следующее n-разрядное число A_1,3 со вторых информационных входов 9 устройства поступает через первые информационные входы второго мультиплексора 1, на младшие n-разрядов информационных входов 2n-разрядного регистра 3. На старшие n-разрядов информационных входов 2n-разрядного регистра 3 поступает в соответствии с (4) значение S_1,2. На информационные входы (n+1)-разрядного регистра 5 с выходов n-разрядного сумматора 4 воздействует значение A_2,2, которое под воздействием третьего тактового импульса запишется в (n+1)-разрядный регистр 5, в 2n-разрядный регистр 3 в младшие n-разрядов запишется n-разрядное число A_1,3, а в старшие n-разрядов запишется значение S_1,2. На первые информационные входы (n+1)-разрядного сумматора 6 с первых информационных входов 12 устройства в этот момент будет поступать инверсный код модуля P₂. (n+1)-разрядный сумматор 6 выполняет фактически операцию вычитания значения числа, подаваемого на его первые информационные входы из значения числа, подаваемого на его вторые входы. Для выполнения операции вычитания необходимо представить вычитаемое в дополнительном коде , что и осуществляется в предлагаемом устройства. Код модуля подается на первые информационные входы (n+1)-разрядного сумматора 6 в инверсном виде, а на его вход переноса подается сигнал логической единицы, что позволяет представить значение модуля в дополнительном коде. При этом, если вычитаемое по своему значению больше уменьшаемого, то на выходе переноса (n+1)-разрядного сумматора 6 образуется сигнал логического нуля, в противном случае на выходе переноса образуется сигнал логической единицы. Так как по определению A_2,2<P₂, то на выходе переноса (n+1)-разрядного сумматора 6 будет нулевой сигнал, под воздействием которого на выходы первого мультиплексора 7 будут скоммутированы его вторые информационные входы. В результате на выходах мультиплексора 7 окажется значение A_2,2. По окончании действия третьего тактового импульса триггер 2 будет переведен в единичное состояние. При этом информационные входы демультиплексора 8 под воздействием единичного сигнала с выхода триггера 2 окажутся скоммутированы с его вторыми информационными выходами, которые соединены со вторыми информационными выходами 14 устройства. В результате, в соответствии с (3) на вторых информационных выходах 14 устройства образуется первое значение накаливающей суммы второго канала:

S _2,3 = (0 + А_2,2) mod P₂. (5)

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

На четвертом такте работы устройства следующее n-разрядное число A_2,4 с третьих информационных входов 10 устройства поступает через вторые информационные входы второго мультиплексора 1 на младшие n-разрядов информационных входов 2n-разрядного регистра 3. На старшие n-разрядов информационных входов 2n-разрядного регистра 3 в соответствии с (5) поступает значение S_2,3. На информационные входы (n+1)-разрядного регистра 5 с выходов n-разрядного сумматора 4 воздействует значение (A_1,3+S_1,2), которое под воздействием третьего тактового импульса запишется в (n+1)-разрядный регистр 5, в 2n-разрядный регистр 3 в младшие n-разрядов запишется n-разрядное число A_2,4, а в старшие n-разрядов запишется значение S_2,3.

На первые информационные входы (n+1)-разрядного сумматора 6 с первых информационных входов 12 устройства в этот момент будет поступать инверсный код модуля P₁, а на вторые информационные входы с информационных выходов (n+1)-разрядного регистра 5 значение (S_1,2+A_1,3). На информационных выходах (n+1)-разрядного сумматора 6 вычисляется значение (S_1,2+A_1,3)−P₁. Если (S_1,2+A_1,3)≥P₁, то на выходе переноса (n+1)-разрядного сумматора 6 появится единичный сигнал, под воздействием которого с информационными выходами первого мультиплексора 7 окажутся скоммутированы его первые информационные входы, а если (S_1,2+A_1,3)<P₁, то на выходе переноса (n+1)-разрядного сумматора 6 появится нулевой сигнал и информационными выходами первого мультиплексора 7 окажутся скоммутированы его вторые информационные входы, на которые поступает значение (S_1,2+A_1,3). В результате на информационных выходах первого мультиплексора 7 появится значение:

S _1,4 =(S_1,2+A_1,3) mod P₁. (6)

По окончании действия четвертого тактового импульса триггер 2 будет переведен в нулевое состояние. При этом информационные входы демультиплексора 8 под воздействием нулевого сигнала с выхода триггера 2 окажутся скоммутированы с его первыми информационными выходами, которые соединены со первыми информационными выходами 13 устройства. В результате, в соответствии с (6) на первых информационных выходах 13 устройства образуется второе значение накаливающей суммы первого канала S_1,4.

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

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

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

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

2. Патент на изобретение RU 2500017 C1. МПК G06F 7/72 (2006.01), G06F 7/50 (2006.01). Накапливающий сумматор по модулю. Опубликован 27.11.2013 Бюл. № 33.

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

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