Умножитель по модулю

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

 

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

Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α’β’(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 ≤ t1i < P	0	0
P≤ t1i < 2P	1	0
2P ≤ t1i < (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

ti	ti – P	ti – 2P	ti – 3P	ti – 4P
0 ≤ ti < P	0	0	0	0
P≤ ti < 2P	1	0	0	0
2P ≤ ti < 3P	1	1	0	0
3P ≤ ti < 4P	1	1	1	0
4P ≤ ti ≤ (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) шагов. В результате быстродействие предлагаемого технического решения по сравнению с устройством прототипом будет выше практически в два раза.

Умножитель по модулю, содержащий 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-й ступени преобразования является выходом кода произведения, каждый трехвходовый мультиплексор первой ступени преобразования содержит два инвертора, два двухвходовых элемента И, три ключа, трехвходовый блок элементов ИЛИ, вход первого инвертора является первым управляющим входом трехвходового мультиплексора и соединен с первым входом первого двухвходового элемента И, а выход соединен с первым входом второго двухвходового элемента И, вход второго инвертора является вторым управляющим входом трехвходового мультиплексора и соединен с управляющим входом третьего ключа, а выход соединен со вторыми входами первого и второго двухвходовых элементов И, выходы которых соединены с управляющими входами первого и второго ключа, информационные входы первого, второго и третьего ключей являются соответственно третьим, первым и вторым информационными входами трехвходового мультиплексора, а информационные выходы соединены соответственно с первым, вторым и третьим информационными входами блока элементов ИЛИ, информационный выход которого является информационным выходом трехвходового мультиплексора, пятивходовые мультиплексоры всех ступеней преобразования содержат четыре инвертора, двухвходовый элемент И, трехвходовый элемент И, два четырехвходовых элемента И, пять ключей, пятивходовый блок элементов ИЛИ, вход первого инвертора является первым управляющим входом пятивходового мультиплексора и соединен с четвертым входом первого четырехвходового элемента И, а выход соединен с четвертым входом второго четырехвходового элемента И, вход второго инвертора является вторым управляющим входом пятивходового мультиплексора и соединен с третьим входом трехвходового элемента И, а выход соединен с третьими входами четырехвходовых элементов И, вход третьего инвертора является третьим управляющим входом пятивходового мультиплексора и соединен со вторым входом двухвходового элемента И, а выход соединен со вторым входом трехвходового элемента И и со вторыми входами четырехвходовых элементов И, вход четвертого инвертора является четвертым управляющим входом пятивходового мультиплексора и соединен с управляющим входом четвертого ключа, а выход соединен с первыми входами двухвходового элемента И, трехвходового элемента И и четырехвходовых элементов И, выход двухвходового элемента И соединен с управляющим входом третьего ключа, выход трехвходового элемента И, соединен с управляющим входом второго ключа, выход первого четырехвходового элемента И соединен с управляющим входом первого ключа, выход второго четырехвходового элемента И соединен с управляющим входом пятого ключа, информационные входы ключей являются соответствующими информационными входами пятивходового мультиплексора, а информационные выходы соединены с соответствующими информационными входами блока элементов ИЛИ, информационный выход которого является информационным выходом пятивходового мультиплексора.