УМНОЖИТЕЛЬ ПО МОДУЛЮ
MODULO MULTIPLIER

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, в криптографических приложениях, а также в устройствах цифровой обработки сигналов и в системах управления.
p
p
Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α’β’(mod /2)+/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
n
i
i
n
j
j
n
j
j
j
j
n
j
n
Для достижения технического результата в умножитель по модулю, содержащий  сумматоров, где - разрядность кода множимого,  ключей, вход кодов множимого, вход кодов множителя, выход кода произведения, вход инверсного кода модуля, причем на первые входы первых сумматоров подается инверсный код модуля, а на вход переноса подается сигнал логической единицы, а управляющие входы ключей соединены с соответствующими разрядами кода множимого, дополнительно введены /2 ступеней преобразования, причем первая ступень преобразования содержит /2 узлов, каждый из которых содержит первый и второй ключи, второй и третий сумматоры и трехвходовый мультиплексор, -я ступень преобразования, где =2,.., /2, содержит пять сумматоров и пятивходовый мультиплексор, причем информационные входы всех ключей первой ступени преобразования соединены со входом кода множителя, информационный выход первого ключа каждого узла первой ступени преобразования соединен со сдвигом на один разряд в сторону старших с первым информационным входом третьего сумматора, информационный выход второго ключа каждого узла первой ступени преобразования соединен со вторым информационным входом соответствующего третьего сумматора, информационный выход третьего сумматора каждого узла первой ступени преобразования соединен с третьим информационным входом трехвходового мультиплексора и вторыми информационными входами первого и второго сумматора соответствующего узла, на входы переноса вторых сумматоров первой ступени преобразования подается логическая единица, а на первые информационные входы подается инверсный код удвоенного модуля, информационные выходы первого и второго сумматора каждого узла первой ступени преобразования соединены соответственно с первыми и вторыми информационными входами трехвходового мультиплексора, а выходы переноса соединены соответственно с первым и вторым управляющими входами трехвходового мультиплексора, информационный выход трехвходового мультиплексора первого узла первой ступени преобразования соединен со сдвигом на два разряда в сторону старших с первым информационным входом пятого сумматора второй ступени преобразования, информационный выход трехвходового мультиплексора -го узла первой ступени преобразования, где =2,.., /2, соединен со вторым информационным входом пятого сумматора -й ступени преобразования, информационный выход пятого сумматора -й ступени преобразования, соединен с пятым информационным входом пятивходового мультиплексора и со вторым информационным входом первого, второго, третьего и четвертого сумматоров этой же ступени преобразования, информационные выходы которых соединены соответственно с первым, вторым, третьим и четвертым информационными входами пятивходового мультиплексора, а выходы переноса соединены соответственно с первым, вторым, третьим и четвертым управляющими входами пятивходового мультиплексора, на входы переноса подается логическая единица, а на первые входы подается соответственно инверсный код модуля, удвоенного модуля, утроенного модуля и учетверенного модуля, информационный выход пятивходового мультиплексора -й ступени преобразования, где =2,.., /2-1, соединен со сдвигом на два разряда в сторону старших с первым информационным входом пятого сумматора (+1)-й ступени преобразования, а /2-й ступени преобразования является выходом кода произведения, каждый трехвходовый мультиплексор первой ступени преобразования содержит два инвертора, два двухвходовых элемента И, три ключа, трехвходовый блок элементов ИЛИ, вход первого инвертора является первым управляющим входом трехвходового мультиплексора и соединен с первым входом первого двухвходового элемента И, а выход соединен с первым входом второго двухвходового элемента И, вход второго инвертора является вторым управляющим входом трехвходового мультиплексора и соединен с управляющим входом третьего ключа, а выход соединен со вторыми входами первого и второго двухвходовых элементов И, выходы которых соединены с управляющими входами первого и второго ключа, информационные входы первого, второго и третьего ключей являются соответственно третьим, первым и вторым информационными входами трехвходового мультиплексора, а информационные выходы соединены соответственно с первым, вторым и третьим информационными входами блока элементов ИЛИ, информационный выход которого является информационным выходом трехвходового мультиплексора, пятивходовые мультиплексоры всех ступеней преобразования содержат четыре инвертора, двухвходовый элемент И, трехвходовый элемент И, два четырехвходовых элемента И, пять ключей, пятивходовый блок элементов ИЛИ, вход первого инвертора является первым управляющим входом пятивходового мультиплексора и соединен с четвертым входом первого четырехвходового элемента И, а выход соединен с четвертым входом второго четырехвходового элемента И, вход второго инвертора является вторым управляющим входом пятивходового мультиплексора и соединен с третьим входом трехвходового элемента И, а выход соединен с третьими входами четырехвходовых элементов И, вход третьего инвертора является третьим управляющим входом пятивходового мультиплексора и соединен со вторым входом двухвходового элемента И, а выход соединен со вторым входом трехвходового элемента И и со вторыми входами четырехвходовых элементов И, вход четвертого инвертора является четвертым управляющим входом пятивходового мультиплексора и соединен с управляющим входом четвертого ключа, а выход соединен с первыми входами двухвходового элемента И, трехвходового элемента И и четырехвходовых элементов И, выход двухвходового элемента И соединен с управляющим входом третьего ключа, выход трехвходового элемента И, соединен с управляющим входом второго ключа, выход первого четырехвходового элемента И соединен с управляющим входом первого ключа, выход второго четырехвходового элемента И соединен с управляющим входом пятого ключа, информационные входы ключей явялются соответствующими информационными входами пятивходового мультиплексора, а информационные выходы соединены с соответствующими информационными входами блока элементов ИЛИ, информационный выход которого является информационным выходом пятивходового мультиплексора.
A
B
P
Сущность изобретения заключается в реализации следующего способа вычисления произведения чисел  и  по модулю . Пусть
A
B
R
P
(·) ≡  (mod ),  (1)
A
где  – целое положительное число, являющееся множимым;
B
B<P
– целое положительное число, являющееся множителем, причем ;
P
– целое положительное число, называемое модулем;
R
A
B
P
– целое положительное число, являющееся остатком от произведения чисел  и  по модулю .
При этом пусть
A
a
·
a
·
a
·
a
·
a
·
a
·
a
·
a
n
-1
n
-2
n
-3
n
-4
3
2
1
0
n
-1
n
-2
n
-3
n
-4
3
2
= 2+2+2+2+  . . . +2+2+2+,  (2)
B
b
·
b
·
b
m
-1
1
0
m
-1
= 2+  . . . +2+,  (3)
P
p
·
p
·
p
m
-1
1
0
m
-1
1
= 2+ . . . +2+,  (4)
R
r
·
r
·
r
m
-1
1
0
m
-1
1
= 2+ . . . +2+,  (5)
a
A
i
где ,  – коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа ;
n
n
– количество разрядов в представлении множимого,  – четное;
b
B
i
,  – коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа ;
p
P
i
,  – коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля ;
r
R
i
,  – коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка ;
m
B
P
R
– количество разрядов в представлении множителя, модуля  и остатка.
A
B
Представим произведение чисел  и  следующим образом:
A
B
a
·
a
·
a
·
a
·
a
·
a
·
a
·
a
B.
n
-1
n
-2
n
-3
n
-4
3
2
1
0
n
-1
n
-2
n
-3
n
-4
3
2
· = (2+2+2+2+  . . . +2+2+2+)·  (6)
Перепишем выражение (6) следующим образом:
A
B
a
·
B
a
·
B
a
·
B
a
·
B
n
-1
n
-2
n
-3
n
-4
n
-1
n
-2
n
-3
n
-4
· = (2· +2· +2· +2· +  ...
a
·
B
a
·
B
a
·
B
a
B
3
2
1
0
3
2
... +2· +2· +2· +·),  (7)
Преобразуем выражение (7) в следующий вид, объединив по два соседних слагаемых:
A
B
a
·
B
a
·
B
a
·
B
a
·
B
n
-1
n
-2
n
-3
n
-4
n
-1
n
-2
n
-3
n
-4
· = (2· +2·)+(2· +2·)+ . . .
a
·
B
a
·
B
a
·
B
a
B
3
2
1
0
3
2
. . . +(2· +2·)+(2· +·),  (8)
i
Из каждой суммы в скобках в выражении (8) вынесем 2 за скобки, где , принимает только четные значения:
A
B
a
·
B
a
B
a
·
B
a
B
n
-2
n
-4
n
-1
n
-2
n
-3
n
-4
· = 2(2· +·)+2(2· +·)+  . . .
2
a
·
B
a
B
a
·
B
a
B
3
2
1
0
. . . +2(2· +·)+(2· +·),  (9)
n
a
·
B
a
B
i
+1
i
i
В выражении (9) перед каждой из /2 образовавшихся сумм вида(2·+·), получаем множитель 2, где , принимает только четные значения.
Далее вынесем в (9) наименьшую ненулевую степень 2 за скобки:
A
B
a
·
B
a
B
a
·
B
a
B
2
n
-4
n
-6
n
-1
n
-2
n
-3
n
-4
· = 2(2(2· +·)+2 (2· +·)+  . . .
a
·
B
a
B
a
·
B
a
B
3
2
1
0
. . . + (2· +·))+(2· +·),  (10)
n
Выполняя последовательно преобразование (10) (/2)-2 раз получим:
A
B
a
·
B
a
B
a
·
B
a
B
2
2
2
n
-1
n
-2
n
-3
n
-4
· = 2(2…(2(2· +·)+(2· +·))+  . . .
a
·
B
a
B
a
·
B
a
B
3
2
1
0
. . . + (2· +·))+(2· +·),  (11)
2
n
где 2 встречается (/2)-1 раз.
Тогда выражение (1) может быть представлено в следующем виде:
A
B
a
·
B
a
B
a
·
B
a
B
2
2
2
n
-1
n
-2
n
-3
n
-4
· ≡ (2(2…(2(2· +·)+(2· +·))+  . . .
a
·
B
a
B
a
·
B
a
B
P
3
2
1
0
. . . + (2· +·))+(2· +·)) mod. (12)
Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т. е. величина остатка не зависит от того, вычислен ли он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.
Исходя из вышесказанного, выражение (12) может быть вычислено следующим образом.
n
t
1
i
Вначале на первой ступени преобразования одновременно в (/2) узлах вычисляют величины , :
t
a
·
B
a
B
P
11
n
-1
n
-2
=(2· +·) mod,
t
a
·
B
a
B
P
12
n
-3
n
-4
=(2· +·) mod, (13)
…  ,
t
a
·
B
a
B
P
1(
n
/2)
1
0
=(2· +·) mod.
На второй ступени преобразования вычисляют величину
t
t
t
P
2
11
12
2
=(2+) mod. (14)
Аналогичным образом производят вычисления на последующих ступенях преобразования.
n
На последней (/2)-й ступени преобразования вычисляют величину
t
t
t
P
n
/2
n
/2-1
1(
n
/2)
2
=(2+) mod, (15)
A
B
P
которая и является искомым произведением чисел  и  по модулю .
P
Операция приведения по модулю  на первой ступени преобразования во всех узлах выполняется исходя из следующих соображений.
B
B
P
t
P
1
i
По определению величина множителя  лежит в диапазоне 0≤ ≤-1. Поэтому значение любой величины  в (13) до приведения ее по модулю находится в диапазоне от 0 до 3-3.
t
1
i
Приведение по модулю величины ,  осуществляется по следующим правилам:
t
P
t
t
P
1
i
1
i
1
i
(mod )=,  если 0 ≤ < , (16)
t
P
t
P
P
t
P
1
i
1
i
1
i
(mod )=- ,  если ≤ < 2,
t
P
t
P
P
t
P
1
i
1
i
1
i
(mod )=- 2,  если 2≤  ≤ (3- 3),
t
t
kP
k
1
i
1
i
Условия попадания значения  в один из указанных в (16) интервалов определяются значениями сигналов переноса на выходах переноса сумматоров, осуществляющих операцию вычитания ( – ), где =1, 2 в соответствии с таблицей 1.
Таблица 1
<i>t</i><sub>1</sub><i></i><sub><i>i</i></sub><i></i>
<i>t</i><sub>1</sub><i></i><sub><i>i</i></sub><i></i> – <i>P</i>
<i>t</i><sub>1</sub><i></i><sub><i>i</i></sub><i></i> – 2<i>P</i>
0 ≤ <i>t</i><sub>1</sub><sub><i>i</i></sub><sub><i></i></sub>< <i>P</i>
0
0
<i>P</i>≤ <i>t</i><sub>1</sub><sub><i>i</i></sub> < 2<i>P</i>
1
0
2<i>P </i>≤ <i>t</i><sub>1</sub><sub><i>i</i></sub> < (3<i>P</i>- 3)
1
1
t
P
t
P
t
P
t
P
t
P
t
1
i
1
i
1
i
1
i
i
i
Таким образом, если значение сигналов переноса равно «1» на выходах переноса двух сумматоров, то  (mod )=– 2, если значение сигнала переноса равно «1» на выходах переноса одного сумматора, то (mod )=– . Если значение сигналов переноса равно «0» на выходах переноса двух сумматоров, то тогда  (mod )=, т.е. операция вычитания не выполняется.
P
t
P
i
Операция приведения по модулю  на второй и последующих ступенях преобразования выполняется следующим образом. Значение величин , в (14)-(15) до приведения по модулю находится в диапазоне от 0 до 5-5.
P
t
i
Приведение по модулю  величины , осуществляется по следующим правилам
t
P
t
t
P
i
i
i
(mod )=,  если 0 ≤ < , (17)
t
P
t
P
P
t
P
i
i
i
(mod )=- ,  если ≤ < 2,
t
P
t
P
P
t
P
i
i
i
(mod )=- 2,  если 2≤  < 3,
t
P
t
P
P
t
P
i
i
i
(mod )=- 3,  если 3≤ < 4,
t
P
t
P
P
t
P
i
i
i
(mod )=- 4,  если 4≤ ≤ (5-5).
t
t
kP
k
i
i
Условия попадания значения  в один из указанных в (17) интервалов определяются значениями сигналов переноса на выходах переноса сумматоров, осуществляющих операцию вычитания  ( – ), где =1, 2, 3, 4 в соответствии с таблицей 2.
Таблица 2
<i>t</i><sub><i>i</i></sub>
<i>t</i><sub><i>i</i></sub> – <i>P</i>
<i>t</i><sub><i>i</i></sub> – 2<i>P</i>
<i>t</i><sub><i>i</i></sub> – 3<i>P</i>
<i>t</i><sub><i>i</i></sub> – 4<i>P</i>
0 ≤ <i>t</i><sub><i>i</i></sub><i></i>< <i>P</i>
0
0
0
0
<i>P</i>≤ <i>t</i><sub><i>i</i></sub><i></i>< 2<i>P</i>
1
0
0
0
2<i>P </i>≤ <i>t</i><sub><i>i</i></sub> < 3<i>P</i>
1
1
0
0
3<i>P </i>≤ <i>t</i><sub><i>i</i></sub><i></i>< 4<i>P</i>
1
1
1
0
<i>4P </i>≤ <i>t</i><sub><i>i</i></sub><i></i>≤ (5<i>P</i>-5)
1
1
1
1
t
P
t
P
t
P
t
P
t
P
t
P
t
P
t
P
t
P
t
i
i
i
i
i
i
i
i
i
i
Таким образом, если значение сигналов переноса равно «1» на выходах переноса всех четырех сумматоров, то  (mod )=– 4, если значение сигналов переноса равно «1» на выходах переноса трех сумматоров, то
(mod )=– 3, если значение сигналов переноса равно «1» на выходах переноса двух сумматоров, то  (mod )=– 2, если значение сигнала переноса равно «1» на выходах переноса одного сумматора, то
(mod )=– . Если значение сигналов переноса равно «0» на выходах переноса всех четырех сумматоров, то тогда  (mod )=, т.е. операция вычитания не выполняется.
На фиг.1 представлена схема умножителя по модулю.
n
n
n
n
n
n
A
B
A
B
P
A
B
j
j
n
j
j
j
j
n
j
j
n
j
n
A
B
P
Умножитель по модулю содержит /2 ступеней преобразования, где - разрядность кода множимого. Первая ступень преобразования содержит /2 узлов включающих  ключей 1, 3/2 сумматоров 2 и /2 трехвходовых мультиплексоров 3. Вторая и последующая ступени преобразования содержат каждая пять сумматоров 2 и пятивходовый мультиплексор 4. Вход 6 устройства является входом кодов множимого , вход 5 устройства является входом кодов множителя, выход 7 является выходом кода произведения чисел  и  по модулю . Управляющие входы ключей 1 соединены с соответствующими разрядами кода множимого, а информационные входы соединены со входом кода множителя. Информационный выход первого ключа 1 каждого узла первой ступени преобразования соединен со сдвигом на один разряд в сторону старших с первым информационным входом третьего сумматора 2 этого же узла. Информационный выход второго ключа 1 каждого узла первой ступени преобразования соединен со вторым информационным входом соответствующего третьего сумматора 2. Информационный выход третьего сумматора 2 каждого узла первой ступени преобразования соединен с третьим информационным входом трехвходового мультиплексора 3 и вторыми информационными входами первого и второго сумматоров 2 соответствующего узла. На входы переноса первых и вторых сумматоров 2 первой ступени преобразования подается логическая единица, на первые информационные входы первых сумматоров 2 подается инверсный код модуля, а на первые информационные входы вторых сумматоров 2 подается инверсный код удвоенного модуля. Информационные выходы первого и второго сумматора 2 каждого узла первой ступени преобразования соединены соответственно с первыми и вторыми информационными входами трехвходового мультиплексора 3, а выходы переноса соединены соответственно с первым и вторым управляющими входами трехвходового мультиплексора 3. Информационный выход трехвходового мультиплексора 3 первого узла первой ступени преобразования соединен со сдвигом на два разряда в сторону старших с первым информационным входом пятого сумматора 2 второй ступени преобразования. Информационный выход трехвходового мультиплексора 3 -го узла первой ступени преобразования, где =2,.., /2, соединен со вторым информационным входом пятого сумматора 2 -й ступени преобразования. Информационный выход пятого сумматора 2 -й ступени преобразования, соединен с пятым информационным входом пятивходового мультиплексора 4 и со вторым информационным входом первого, второго, третьего и четвертого сумматоров 2 этой же ступени преобразования, информационные выходы которых соединены соответственно с первым, вторым, третьим и четвертым информационными входами пятивходового мультиплексора 4, а выходы переноса соединены соответственно с первым, вторым, третьим и четвертым управляющими входами пятивходового мультиплексора 4. На входы переноса первого, второго, третьего и четвертого сумматоров 2 -й ступени преобразования, где =2,.., /2, подается логическая единица, а на первые входы подается соответственно инверсный код модуля, удвоенного модуля, утроенного модуля и учетверенного модуля. Информационный выход пятивходового мультиплексора 4 -й ступени преобразования, где =2, …, /2-1, соединен со сдвигом на два разряда в сторону старших с первым информационным входом пятого сумматора 4 (+1)-й ступени преобразования, а /2-й ступени преобразования является выходом 7 кода произведения чисел  и  по модулю .
На фиг. 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).
n
A
m
B
P
P
На вход 6 устройства подается  – разрядный двоичный код множимого . На вход 5 устройства подается – разрядный код множителя . На первые входы первых сумматоров 2 первой ступени преобразования подается инверсный код модуля , а на их входы переноса подается логическая единица. На первые входы вторых сумматоров 2 первой ступени преобразования подается инверсный код удвоенного модуля , а на их входы переноса подается логическая единица. На первые входы первых, вторых, третьих и четвертых сумматоров 2 второй и последующих ступеней преобразования подается соответственно инверсный код модуля, удвоенный инверсный код модуля, утроенный инверсный код модуля и учетверенный инверсный код модуля.
n
t
1
i
Вначале на первой ступени преобразования одновременно в (/2) узлах вычисляют величины , :
t
a
·
B
a
B
P
11
n
-1
n
-2
=(2· +·) mod,
t
a
·
B
a
B
P
12
n
-3
n
-4
=(2· +·) mod,
…  ,
t
a
·
B
a
B
P
1(
n
/2)
1
0
=(2· +·) mod.
a
B
a
·
B
a
B
P
P
i
i
i
-
1
Умножение разрядов множимого  на множитель  осуществляется с помощью ключей 1. Умножение на 2 осуществляется путем сдвига разрядов на один в сторону старших сигнала с информационных выходов первых ключей 1 каждого узла при подключении к первому информационному выходу третьего сумматора 2 соответствующего узла. Третий сумматор 2 каждого узла первой ступени преобразования осуществляет суммирование значений 2· и ·. Приведение получившейся суммы по модулю осуществляется с помощью первого и второго сумматоров 2 путем одновременного вычитания из нее значений и 2 и трехвходового мультиплексора 3 соответствующего узла, осуществляющего коммутацию на выход, поступивших на его информационные входы значений сигналов переноса, в соответствии с таблицей 1.
t
1
i
В результате на выходах всех узлов первой ступени преобразования образуются значения ,  в соответствии с выражением (13).
t
t
t
P
t
t
t
P
2
11
12
11
12
11
2
2
На второй ступени преобразования осуществляется вычисление значения =(2+) mod, где  и значения на выходах первого и второго узла первой ступени преобразования. Умножение значения на 2осуществляется сдвигом разрядов на два в сторону старшего. Приведение по модулю  осуществляется аналогичным образом путем одновременного вычитания из суммы значений модуля, удвоенного модуля, утроенного модуля и учетверенного модуля и выбором окончательного значения с помощью пятивходового мультиплексора 4 в зависимости от управляющих сигналов, подаваемых на его вход в соответствии с таблицей 2.
n
A
B
P
Аналогичные вычисления производятся и на последующих ступенях преобразования. В результате этих вычислений на выходе последней (/2)-й ступени преобразования образуется значение произведения чисел  и  по модулю .
Трехвходовый мультиплексор 3 (см. Фиг. 2) в зависимости от комбинаций сигналов на его управляющих входах, коммутирует на свой выход сигнал с одного из своих трех информационных входов.
P
t
P
t
P
1
i
1
i
Если управляющий сигнал появляется на двух управляющих входах трехвходового мультиплексора 3, что по таблице 1 соответствует диапазону 2≤  < (3- 3), то окажется открытым третий ключ 11. Первый и второй ключи 11 будут закрыты нулевым сигналом, поступающим на вторые входы элементов И 10 с выхода второго инвертора 9. В результате на выходе трехвходового мультиплексора 3 окажется величина  – 2.
P
t
P
t
P
1
i
1
i
Если управляющий сигнал появляется на одном управляющем входе трехвходового мультиплексора 3, что по таблице 1 соответствует диапазону
≤  < 2, то окажется открытым второй ключ 11. Третий ключ 11 будет закрыт нулевым сигналом со второго управляющего входа трехвходового мультиплексора 3, а первый ключ 11 будет закрыт нулевым сигналом, поступающим на первый вход второго элемента И 10 с выхода первого инвертора 9. В результате на выходе трехвходового мультиплексора 3 окажется величина  – .
t
1
i
Если оба управляющих сигнала трехвходового мультиплексора будут равны нулю, то окажется открытым первый ключ 11 и на выход поступит исходный сигнал  без вычитания.
Пятивходовый мультиплексор 4 (см. Фиг. 3) в зависимости от комбинаций сигналов на его управляющих входах, коммутирует на свой выход один из своих пяти информационных входов в соответствии с таблицей 2. Логика работы пятивходового мультиплексора 4 аналогична логике работы трехвходового мультиплексора 3.
n
A
B
P
Так как на каждой ступени преобразования осуществляется обработка одновременно двух разрядов множимого, то через (/2) преобразований на выходе 7 устройства сформируется двоичный код произведения чисел  и  по модулю .
Рассмотрим работу умножителя по модулю на примере.
A
B
P
n
m
10
2
10
2
10
2
Пусть множимое =248=11111000, множитель =23=00010111модуль =37=00100101, разрядность =8, разрядность =8.
P
P
P
P
Для заданных исходных данных умножитель по модулю будет содержать четыре ступени преобразования и четыре узла в первой ступени преобразования. Двоичные прямые и инверсные коды значений модуля , 2, 3, 4 представлены в табл. 3.
Таблица 3
Двоичный прямой код
Двоичный инверсный код
Модуль <i>P</i> =37
00100101
11011010
Значение 2<i>P</i> = 74
01001010
10110101
Значение 3<i>P</i> = 111
01101111
10010000
Значение 4<i>P</i> = 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
B
A
На информационные входы (строка «Инф. вх») ключей 1 подается двоичный код множителя , а на управляющие входы (строка «Упр. вх») подаются соответствующие двоичные разряды множимого , которые при нулевом значении закрывают соответствующий ключ 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
-
R
2
10
В результате на выходе пятивходового мультиплексора 4 четвертой ступени преобразования получаем значение =00000110=6. Непосредственной проверкой убеждаемся в правильности полученного результата: 248*23=5704≡6 mod 37.
n
n
В устройстве прототипе умножение осуществляется за (-1) последовательных шагов преобразования, а в предлагаемом устройстве за (/2) шагов. В результате быстродействие предлагаемого технического решения по сравнению с устройством прототипом будет выше практически в два раза.