УМНОЖИТЕЛЬ ПО МОДУЛЮ Российский патент 2021 года по МПК G06F7/72 G06F7/523 

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

Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α’β’(mod p/2)+p/2, пять элементов ИЛИ, два элемента И и шифратор (см. АС СССР №1187161, кл. G 06 F 7/49, опубл. 23.10.1985).

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

Известен умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G 06 F 7/49, опубл. 30.06.1994).

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

Наиболее близким по технической сущности к заявляемому изобретению является устройство для умножения чисел по произвольному модулю, содержащее сумматоры, мультиплексоры, ключи, блоки сдвига, инвертор и сумматор по модулю (см. патент РФ № 2316042, МПК G06F 7/523 (2006.01), G06F 7/72 (2006.01), опубл. 27.01.2008. Бюл. № 3). Недостатком данного устройства является низкое быстродействие.

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

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

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

(A·B) ≡ R (mod P), (1)

где A – целое положительное число, являющееся множимым;

B – целое положительное число, являющееся множителем, причем B<P;

P – целое положительное число, называемое модулем;

R – целое положительное число, являющееся остатком от произведения чисел A и B по модулю P.

При этом пусть

A = a_n-1·2^n-1+a_n-2·2^n-2+ a_n-3·2^n-3+a_n-4·2^n-4+ . . . +a₃·2³+a₂·2²+a₁·2+a₀, (2)

B = b_m-1·2^m-1+ . . . + b₁·2+b₀, (3)

P = p_m-1·2^m-1+ . . . +p₁·2¹+p₀, (4)

R = r_m-1·2^m-1+ . . . +r₁·2¹+r₀, (5)

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

n – количество разрядов в представлении множимого, n – четное;

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

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

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

m – количество разрядов в представлении множителя B, модуля P и остатка R.

Представим произведение чисел A и B следующим образом:

A·B = (a_n-1·2^n-1+a_n-2·2^n-2+ a_n-3·2^n-3+a_n-4·2^n-4+ . . . +a₃·2³+a₂·2²+a₁·2+a₀)·B. (6)

Перепишем выражение (6) следующим образом:

A·B = (a_n-1·2^n-1·B +a_n-2·2^n-2·B + a_n-3·2^n-3·B +a_n-4·2^n-4·B + ...

... +a₃·2³·B +a₂·2²·B +a₁·2·B +a₀·B), (7)

Преобразуем выражение (7) в следующий вид, объединив по два соседних слагаемых:

A·B = (a_n-1·2^n-1·B +a_n-2·2^n-2·B)+ (a_n-3·2^n-3·B +a_n-4·2^n-4·B)+ . . .

. . . +(a₃·2³·B +a₂·2²·B)+(a₁·2·B +a₀·B), (8)

Из каждой суммы в скобках в выражении (8) вынесем 2ⁱ за скобки, где , принимает только четные значения:

A·B = 2^n-2(a_n-1·2·B +a_n-2·B)+2^n-4(a_n-3·2·B +a_n-4·B)+ . . .

. . . +2²(a₃·2·B +a₂·B)+(a₁·2·B +a₀·B), (9)

В выражении (9) перед каждой из n/2 образовавшихся сумм вида
(a_i+1·2·B+a_i·B), получаем множитель 2ⁱ, где , принимает только четные значения.

Далее вынесем в (9) наименьшую ненулевую степень 2 за скобки:

A·B = 2²(2^n-4(a_n-1·2·B +a_n-2·B)+ 2^n-6 (a_n-3·2·B +a_n-4·B)+ . . .

. . . + (a₃·2·B +a₂·B))+(a₁·2·B +a₀·B), (10)

Выполняя последовательно преобразование (10) (n/2)-2 раз получим:

A·B = 2²(2²…(2²(a_n-1·2·B +a_n-2·B)+(a_n-3·2·B +a_n-4·B))+ . . .

. . . + (a₃·2·B +a₂·B))+(a₁·2·B +a₀·B), (11)

где 2² встречается (n/2)-1 раз.

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

A·B ≡ (2²(2²…(2²(a_n-1·2·B +a_n-2·B)+(a_n-3·2·B +a_n-4·B))+ . . .

. . . + (a₃·2·B +a₂·B))+(a₁·2·B +a₀·B)) mod P. (12)

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

Исходя из вышесказанного, выражение (12) может быть вычислено следующим образом.

Вначале на первой ступени преобразования одновременно в (n/2) узлах вычисляют величины t_1i, :

t ₁₁=(a_n-1·2·B +a_n-2·B) mod P,

t₁₂=(a_n-3·2·B +a_n-4·B) mod P, (13)

… ,

t_1(n/2)=(a₁·2·B +a₀·B) mod P.

На второй ступени преобразования вычисляют величину

t ₂=(2²t₁₁+t₁₂) mod P. (14)

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

На последней (n/2)-й ступени преобразования вычисляют величину

t_{n /2}=(2²t_n/2-1+t_1(n/2)) mod P, (15)

которая и является искомым произведением чисел A и B по модулю P.

Операция приведения по модулю P на первой ступени преобразования во всех узлах выполняется исходя из следующих соображений.

По определению величина множителя B лежит в диапазоне 0≤ B ≤P-1. Поэтому значение любой величины t_1i в (13) до приведения ее по модулю находится в диапазоне от 0 до 3P-3.

Приведение по модулю величины t_1i, осуществляется по следующим правилам:

t _{1 i} (mod P)= t_1i, если 0 ≤ t_1i < P, (16)

t _{1 i} (mod P)= t_1i - P, если P≤ t_1i < 2P,

t_1i (mod P)= t_1i - 2P, если 2P ≤ t_1i ≤ (3P- 3),

Условия попадания значения t_1i в один из указанных в (16) интервалов определяются значениями сигналов переноса на выходах переноса сумматоров, осуществляющих операцию вычитания (t_1i – kP), где k=1, 2 в соответствии с таблицей 1.

Таблица 1

t _{1 i} t _{1 i} – P t _{1 i} – 2P 0 ≤ t_1i < P 0 0 P≤ t_1i < 2P 1 0 2P ≤ t_1i < (3P- 3) 1 1

Таким образом, если значение сигналов переноса равно «1» на выходах переноса двух сумматоров, то t_1i (mod P)=t_1i – 2P, если значение сигнала переноса равно «1» на выходах переноса одного сумматора, то
t_1i (mod P)= t_1i – P. Если значение сигналов переноса равно «0» на выходах переноса двух сумматоров, то тогда t_i (mod P)=t_i, т.е. операция вычитания не выполняется.

Операция приведения по модулю P на второй и последующих ступенях преобразования выполняется следующим образом. Значение величин t_i, в (14)-(15) до приведения по модулю находится в диапазоне от 0 до 5P-5.

Приведение по модулю P величины t_i, осуществляется по следующим правилам

t_i (mod P)=t_i, если 0 ≤ t_i < P, (17)

t_i (mod P)=t_i - P, если P≤ t_i < 2P,

t_i (mod P)=t_i - 2P, если 2P ≤ t_i < 3P,

t_i (mod P)=t_i - 3P, если 3P ≤ t_i < 4P,

t_i (mod P)=t_i - 4P, если 4P ≤ t_i ≤ (5P-5).

Условия попадания значения t_i в один из указанных в (17) интервалов определяются значениями сигналов переноса на выходах переноса сумматоров, осуществляющих операцию вычитания (t_i – kP), где k=1, 2, 3, 4 в соответствии с таблицей 2.

Таблица 2

t_i t_i – P t_i – 2P t_i – 3P t_i – 4P 0 ≤ t_i < P 0 0 0 0 P≤ t_i < 2P 1 0 0 0 2P ≤ t_i < 3P 1 1 0 0 3P ≤ t_i < 4P 1 1 1 0 4P ≤ t_i ≤ (5P-5) 1 1 1 1

Таким образом, если значение сигналов переноса равно «1» на выходах переноса всех четырех сумматоров, то t_i (mod P)=t_i – 4P, если значение сигналов переноса равно «1» на выходах переноса трех сумматоров, то
t_i (mod P)=t_i – 3P, если значение сигналов переноса равно «1» на выходах переноса двух сумматоров, то t_i (mod P)=t_i – 2P, если значение сигнала переноса равно «1» на выходах переноса одного сумматора, то
t_i (mod P)=t_i – P. Если значение сигналов переноса равно «0» на выходах переноса всех четырех сумматоров, то тогда t_i (mod P)=t_i, т.е. операция вычитания не выполняется.

На фиг.1 представлена схема умножителя по модулю.

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

На фиг. 2 представлена схема трехвходовых мультиплексоров 3 первой ступени преобразования.

Каждый трехвходовый мультиплексор 3 первой ступени преобразования содержит два инвертора 9, два двухвходовых элемента И 10, три ключа 11, трехвходовый блок элементов ИЛИ 12. Вход первого инвертора 9 является первым управляющим входом трехвходового мультиплексора 3 и соединен с первым входом первого двухвходового элемента И 10, а выход соединен с первым входом второго двухвходового элемента И 10. Вход второго инвертора 9 является вторым управляющим входом трехвходового мультиплексора 3 и соединен с управляющим входом третьего ключа 11, а выход соединен со вторыми входами первого и второго двухвходовых элементов И 10, выходы которых соединены с управляющими входами первого и второго ключа 11. Информационные входы первого, второго и третьего ключей 11 являются соответственно третьим, первым и вторым информационными входами трехвходового мультиплексора 3, а информационные выходы соединены соответственно с первым, вторым и третьим информационными входами блока элементов ИЛИ 12, информационный выход которого является информационным выходом трехвходового мультиплексора 3.

На фиг. 3 представлена схема пятивходовых мультиплексоров 4.

Пятивходовые мультиплексоры 4 всех ступеней преобразования содержат четыре инвертора 9, двухвходовый элемент И 10, трехвходовый элемент И 13, два четырехвходовых элемента И 14, пять ключей 11, пятивходовый блок элементов ИЛИ 8. Вход первого инвертора 9 является первым управляющим входом пятивходового мультиплексора 4 и соединен с четвертым входом первого четырехвходового элемента И 14, а выход соединен с четвертым входом второго четырехвходового элемента И 14. Вход второго инвертора 9 является вторым управляющим входом пятивходового мультиплексора 4 и соединен с третьим входом трехвходового элемента И 13, а выход соединен с третьими входами четырехвходовых элементов И 14. Вход третьего инвертора 9 является третьим управляющим входом пятивходового мультиплексора 4 и соединен со вторым входом двухвходового элемента И 10, а выход соединен со вторым входом трехвходового элемента И 13 и со вторыми входами четырехвходовых элементов И 14. Вход четвертого инвертора 9 является четвертым управляющим входом пятивходового мультиплексора 4 и соединен с управляющим входом четвертого ключа 11, а выход соединен с первыми входами двухвходового элемента И 10, трехвходового элемента И 13 и четырехвходовых элементов И 14. Выход двухвходового элемента И 10 соединен с управляющим входом третьего ключа 11. Выход трехвходового элемента И 13, соединен с управляющим входом второго ключа 11. Выход первого четырехвходового элемента И 14 соединен с управляющим входом первого ключа 11, выход второго четырехвходового элемента И 14 соединен с управляющим входом пятого ключа 11. Информационные входы ключей 11 являются соответствующими информационными входами пятивходового мультиплексора 4, а информационные выходы соединены с соответствующими информационными входами блока элементов ИЛИ 8, информационный выход которого является информационным выходом пятивходового мультиплексора 4.

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

На вход 6 устройства подается n – разрядный двоичный код множимого A. На вход 5 устройства подается m – разрядный код множителя B. На первые входы первых сумматоров 2 первой ступени преобразования подается инверсный код модуля P, а на их входы переноса подается логическая единица. На первые входы вторых сумматоров 2 первой ступени преобразования подается инверсный код удвоенного модуля P, а на их входы переноса подается логическая единица. На первые входы первых, вторых, третьих и четвертых сумматоров 2 второй и последующих ступеней преобразования подается соответственно инверсный код модуля, удвоенный инверсный код модуля, утроенный инверсный код модуля и учетверенный инверсный код модуля.

Вначале на первой ступени преобразования одновременно в (n/2) узлах вычисляют величины t_1i, :

t ₁₁=(a_n-1·2·B +a_n-2·B) mod P,

t₁₂=(a_n-3·2·B +a_n-4·B) mod P,

… ,

t_1(n/2)=(a₁·2·B +a₀·B) mod P.

Умножение разрядов множимого a_i на множитель B осуществляется с помощью ключей 1. Умножение на 2 осуществляется путем сдвига разрядов на один в сторону старших сигнала с информационных выходов первых ключей 1 каждого узла при подключении к первому информационному выходу третьего сумматора 2 соответствующего узла. Третий сумматор 2 каждого узла первой ступени преобразования осуществляет суммирование значений a_i·2·B и a_i-1·B. Приведение получившейся суммы по модулю осуществляется с помощью первого и второго сумматоров 2 путем одновременного вычитания из нее значений P и 2P и трехвходового мультиплексора 3 соответствующего узла, осуществляющего коммутацию на выход, поступивших на его информационные входы значений сигналов переноса, в соответствии с таблицей 1.

В результате на выходах всех узлов первой ступени преобразования образуются значения t_1i, в соответствии с выражением (13).

На второй ступени преобразования осуществляется вычисление значения t₂=(2²t₁₁+t₁₂) mod P, где t₁₁ и t₁₂ значения на выходах первого и второго узла первой ступени преобразования. Умножение значения t₁₁ на 2² осуществляется сдвигом разрядов на два в сторону старшего. Приведение по модулю P осуществляется аналогичным образом путем одновременного вычитания из суммы значений модуля, удвоенного модуля, утроенного модуля и учетверенного модуля и выбором окончательного значения с помощью пятивходового мультиплексора 4 в зависимости от управляющих сигналов, подаваемых на его вход в соответствии с таблицей 2.

Аналогичные вычисления производятся и на последующих ступенях преобразования. В результате этих вычислений на выходе последней (n/2)-й ступени преобразования образуется значение произведения чисел A и B по модулю P.

Трехвходовый мультиплексор 3 (см. Фиг. 2) в зависимости от комбинаций сигналов на его управляющих входах, коммутирует на свой выход сигнал с одного из своих трех информационных входов.

Если управляющий сигнал появляется на двух управляющих входах трехвходового мультиплексора 3, что по таблице 1 соответствует диапазону 2P ≤ t_1i < (3P- 3), то окажется открытым третий ключ 11. Первый и второй ключи 11 будут закрыты нулевым сигналом, поступающим на вторые входы элементов И 10 с выхода второго инвертора 9. В результате на выходе трехвходового мультиплексора 3 окажется величина t_1i – 2P.

Если управляющий сигнал появляется на одном управляющем входе трехвходового мультиплексора 3, что по таблице 1 соответствует диапазону
P ≤ t_1i < 2P, то окажется открытым второй ключ 11. Третий ключ 11 будет закрыт нулевым сигналом со второго управляющего входа трехвходового мультиплексора 3, а первый ключ 11 будет закрыт нулевым сигналом, поступающим на первый вход второго элемента И 10 с выхода первого инвертора 9. В результате на выходе трехвходового мультиплексора 3 окажется величина t_1i – P.

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

Пятивходовый мультиплексор 4 (см. Фиг. 3) в зависимости от комбинаций сигналов на его управляющих входах, коммутирует на свой выход один из своих пяти информационных входов в соответствии с таблицей 2. Логика работы пятивходового мультиплексора 4 аналогична логике работы трехвходового мультиплексора 3.

Так как на каждой ступени преобразования осуществляется обработка одновременно двух разрядов множимого, то через (n/2) преобразований на выходе 7 устройства сформируется двоичный код произведения чисел A и B по модулю P.

Рассмотрим работу умножителя по модулю на примере.

Пусть множимое A=248₁₀=11111000₂, множитель B=23₁₀=00010111₂ модуль P=37₁₀=00100101₂, разрядность n=8, разрядность m=8.

Для заданных исходных данных умножитель по модулю будет содержать четыре ступени преобразования и четыре узла в первой ступени преобразования. Двоичные прямые и инверсные коды значений модуля P, 2P, 3P, 4P представлены в табл. 3.

Таблица 3

Двоичный прямой код Двоичный инверсный код Модуль P =37 00100101 11011010 Значение 2P = 74 01001010 10110101 Значение 3P = 111 01101111 10010000 Значение 4P = 148 10010100 01101011

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

Значения сигналов на входах и выходах ключей 1, которых всего 8, представлены в табл. 4.

Таблица 4

Ключ 1 Ключ 2 Ключ 3 Ключ 4 Ключ 5 Ключ 6 Ключ 7 Ключ 8 Инф. вх 00010111 00010111 00010111 00010111 00010111 00010111 00010111 00010111 Упр. вх 1 1 1 1 1 0 0 0 Выход 00010111 00010111 00010111 00010111 00010111 00000000 00000000 00000000

На информационные входы (строка «Инф. вх») ключей 1 подается двоичный код множителя B, а на управляющие входы (строка «Упр. вх») подаются соответствующие двоичные разряды множимого A, которые при нулевом значении закрывают соответствующий ключ 1 (строка «Выход»), а при единичном – открывают.

Значения сигналов на входах и выходах третьих сумматоров 2 первой ступени преобразования, которых всего 4, представлены в табл. 5.

Таблица 5

Сумматор 1 Сумматор 2 Сумматор 3 Сумматор 4 Вход 1 Вход 2 Вход 1 Вход 2 Вход 1 Вход 2 Вход 1 Вход 2 Входы 00101110 00010111 00101110 00010111 00101110 00000000 00000000 00000000 Выход 01000101 01000101 00101110 00000000

Значения сигналов на входах и выходах первых и вторых сумматоров 2 первой ступени преобразования, которых всего 8, представлены в табл. 6.

Таблица 6

Сумматор 1 Сумматор 2 Сумматор 3 Сумматор 4 Сумматор 5 Сумматор 6 Сумматор 7 Сумматор 8 Вход 1 11011010 10110101 11011010 10110101 11011010 10110101 11011010 10110101 Вход 2 01000101 01000101 01000101 01000101 00101110 00101110 00000000 00000000 Вход переноса 1 1 1 1 1 1 1 1 Выход 1 00100000 11111011 00100000 11111011 00001001 11100100 11011011 10110110 Выход переноса 1 0 1 0 1 0 0 0

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

Таблица 7

мультиплексор 1 мультиплексор 2 мультиплексор 3 мультиплексор 4 Информационный вход 1 00100000 00100000 00001001 11011011 Информационный вход 2 11111011 11111011 11100100 10110110 Информационный вход 3 01000101 01000101 00101110 00000000 Управляющий вход 1 1 1 1 0 Управляющий вход 2 0 0 0 0 Выход 00100000 00100000 00001001 00000000

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

Значения сигналов на информационных входах (строки «Вход 1» и «Вход 2») и на выходах (строка «Выход») пятого сумматора 2 (Столбец «Сумматор»), на информационных входах (строки «Вход 1» и «Вход 2»), на входах переноса (строка «Вход переноса»), на выходах (строка «Выход») и на выходах переноса (строка «Выход переноса») первого, второго, третьего и четвертого сумматоров 2 (столбцы «Сумматор 1», «Сумматор 2», «Сумматор 3» и «Сумматор 4»), на информационных входах (строки «Вход 1», «Вход 2», «Вход 3», «Вход 4» и «Вход 5»), на управляющих входах (строки «Упр. вход 1», «Упр. вход 2», «Упр. вход 3» и «Упр. вход 4»), на выходе (строка «Выход») мультиплексора 4 (столбец «Мультиплексор») второй ступени преобразования представлены в табл. 8.

Таблица 8

Сумматор Сумматор 1 Сумматор 2 Сумматор 3 Сумматор 4 Мультиплексор Вход 1 0010000000 11011010 10110101 10010000 01101011 01111011 Вход 2 0000100000 10100000 10100000 10100000 10100000 01010110 Вход 3 - - - - - 00110001 Вход 4 - - - - - 00001100 Вход 5 - - - - - 10100000 Вход переноса - 1 1 1 1 - Упр. вход 1 - - - - - 1 Упр. вход 2 - - - - - 1 Упр. вход 3 - - - - - 1 Упр. вход 4 - - - - - 1 Выход 0010100000 01111011 01010110 00110001 00001100 00001100 Выход переноса - 1 1 1 1 -

Значения сигналов на информационных входах (строки «Вход 1» и «Вход 2») и на выходах (строка «Выход») пятого сумматора 2 (Столбец «Сумматор»), на информационных входах (строки «Вход 1» и «Вход 2»), на входах переноса (строка «Вход переноса»), на выходах (строка «Выход») и на выходах переноса (строка «Выход переноса») первого, второго, третьего и четвертого сумматоров 2 (столбцы «Сумматор 1», «Сумматор 2», «Сумматор 3» и «Сумматор 4»), на информационных входах (строки «Вход 1», «Вход 2», «Вход 3», «Вход 4» и «Вход 5»), на управляющих входах (строки «Упр. вход 1», «Упр. вход 2», «Упр. вход 3» и «Упр. вход 4»), на выходе (строка «Выход») мультиплексора 4 (столбец «Мультиплексор») третьей ступени преобразования представлены в табл. 9.

Таблица 9

Сумматор Сумматор 1 Сумматор 2 Сумматор 3 Сумматор 4 Мультиплексор Вход 1 0000110000 11011010 10110101 10010000 01101011 00010100 Вход 2 0000001001 00111001 00111001 00111001 00111001 11101111 Вход 3 - - - - - 11001010 Вход 4 - - - - - 10100101 Вход 5 00111001 Вход переноса - 1 1 1 1 - Упр. вход 1 - - - - - 1 Упр. вход 2 - - - - - 0 Упр. вход 3 - - - - - 0 Упр. вход 4 - - - - - 0 Выход 0000111001 00010100 11101111 11001010 10100101 00010100 Выход переноса - 1 0 0 0 -

Значения сигналов на информационных входах (строки «Вход 1» и «Вход 2») и на выходах (строка «Выход») пятого сумматора 2 (Столбец «Сумматор»), на информационных входах (строки «Вход 1» и «Вход 2»), на входах переноса (строка «Вход переноса»), на выходах (строка «Выход») и на выходах переноса (строка «Выход переноса») первого, второго, третьего и четвертого сумматоров 2 (столбцы «Сумматор 1», «Сумматор 2», «Сумматор 3» и «Сумматор 4»), на информационных входах (строки «Вход 1», «Вход 2», «Вход 3», «Вход 4» и «Вход 5»), на управляющих входах (строки «Упр. вход 1», «Упр. вход 2», «Упр. вход 3» и «Упр. вход 4»), на выходе (строка «Выход») мультиплексора 4 (столбец «Мультиплексор») четвертой ступени преобразования представлены в табл. 10.

Таблица 10

Сумматор Сумматор 1 Сумматор 2 Сумматор 3 Сумматор 4 Мультиплексор Вход 1 0001010000 11011010 10110101 10010000 01101011 00101011 Вход 2 0000000000 01010000 01010000 01010000 01010000 00000110 Вход 3 - - - - - 11100001 Вход 4 - - - - - 10111100 Вход 5 01010000 Вход переноса - 1 1 1 1 - Упр. вход 1 - - - - - 1 Упр. вход 2 - - - - - 1 Упр. вход 3 - - - - - 0 Упр. вход 4 - - - - - 0 Выход 0001010000 00101011 00000110 11100001 10111100 00000110 Выход переноса - 1 1 0 0 -

В результате на выходе пятивходового мультиплексора 4 четвертой ступени преобразования получаем значение R=00000110₂=6₁₀. Непосредственной проверкой убеждаемся в правильности полученного результата: 248*23=5704≡6 mod 37.

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

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

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