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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей.
Известно устройство для умножения чисел по модулю, содержащее сумматор и мультиплексор (см. патент РФ №2015537, кл. G06F 7/49, 30.06.1994).
Недостатком данного устройства являются его ограниченные функциональные возможности, а именно ограниченный диапазон значений входных чисел x(0<x≤p-1), где p - значение модуля, по которому производится вычисление), а также отсутствие возможности умножения на число, отличное от двух.
Известно устройство для умножения чисел на два по модулю, содержащее сумматоры, инверторы, умножители и мультиплексор (см. патент РФ №2299460, кл. G06F 7/523, 05.10.2005).
Недостатком данного устройства являются его ограниченные функциональные возможности, а именно ограниченный диапазон значений входных чисел x(0<x≤(n/2)p-1), а также отсутствие возможности умножения на число отличное от двух.
Наиболее близким по технической сущности к заявляемому изобретению является устройство для умножения чисел по модулю, содержащее умножитель, сумматоры, инверторы, умножители на константу, мультиплексор (см. патент РФ №2299461, кл. G06F 7/523, 25.05.2005).
Недостатком данного устройства является большой объем оборудования.
Техническим результатом, достигнутым при осуществлении заявленного изобретения, является сокращение объема оборудования.
Технический результат достигается путем исключения из схемы всех четных умножителей на константу, а также части инверторов следующим образом.
1
1
1
2
1
i
При перемножении значений входных чисел x и y, представленных в двоичной форме, с последующим приведением полученного значения z=x⋅y по модулю p, значение z=x⋅y сравнивается со значением модуля p. Если полученное значение z≥p, то из z вычитается значение модуля p, а полученное в результате значение z=z-p вновь сравнивается со значением р. Если и в этом случае значение z≥p, то из z вновь вычитается значение p, а полученное в результате значение z=z-p сравнивается со значением р. Данные операции проводятся до тех пор, пока значение z, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение z является результатом умножения числа x на число у по модулю р. Если уже на первом шаге входное значение z<p, значение z остается без изменений и является результатом умножения числа x на число y по модулю p.
N
Предлагаемый умножитель по модулю осуществляет данный метод путем параллельного выполнения n-1 операций, где n=2-1, N - разрядность сомножителей и модуля. В ходе i-й операции значение z=x⋅y сравнивается со значением i⋅p путем вычисления разности z-i⋅p, где i=1 , …, n. Как только при выполнении i-й операции значение полученной разности станет отрицательным, результатом умножения числа x на число y по модулю p будет являться значение разности, полученное в результате (i-1)-й операции. Уменьшение объема оборудования достигается за счет исключения части умножителей на константу, осуществляющих умножение модуля p на четные числа. Получение недостающих произведений i⋅p, где i - четное, достигается путем сдвига произведений  на один разряд в сторону старшего, что эквивалентно в двоичной системе счисления умножению на 2. Например, произведение 6р может быть получено из произведения 3p путем сдвига разрядов на один в сторону старшего. Таким образом, достаточно иметь лишь умножители на константу для нечетных констант, а умножители на константу для четных констант можно исключить.
На фиг. 1 представлена схема умножителя по модулю.
Умножитель по модулю содержит умножитель 1, (n-1) сумматоров 2, (n-1)/2 инверторов 3, (n-1)/2-1 умножителей на константу 4, и мультиплексор 5, содержащий n информационных и (n-1) управляющих входов. Входы 6 и 7 служат для подачи двоичных кодов умножаемых чисел х и у, вход 8 служит для подачи двоичного кода модуля р. Выход 9 является выходом устройства.
Умножитель по модулю работает следующим образом.
S
На вход 6 подается двоичный код числа x, на вход 7 - двоичный код числам, причем оба числа принадлежат диапазону [0, …, (р-1)], где p - модуль. Данные коды подаются на входы умножителя 1, который на выходе формирует двоичный код числа z=x⋅y. Код числа z поступает на первые входы сумматоров 2 и на первый информационный вход мультиплексора 5. Со входа 8 устройства двоичный код модуля p подается на вход первого инвертора 3 и на входы умножителей на константу 4. Значение модуля в j-м умножителе на константу 4 умножается на значение i=2 j+1, где j=1, …, (n-1)/2-1 - порядковый номер умножителя на константу. С выхода j-го умножителя на константу 4 код значения i⋅p поступает на вход (j+1)-го инвертора, где j=1, …, (n-1)/2-1. Инверсный код с выходов k-x инверторов 3 подается на вторые входы 2k-1-х сумматоров 2 и дополнительно со сдвигом на вторые входы l⋅2-х  сумматоров 2, где , s=1, 2, 3 … и , при этом сдвиг осуществляется на s разрядов в сторону старшего, а к младшим s разрядам вторых входов соответствующих сумматоров 2 подключен вход записи логической единицы. На вход переноса каждого сумматора 2 поступает код числа «1», служащий для перевода инверсного кода модуля в дополнительный код.
В общем виде сумматор 2 осуществляет операцию, описываемую выражением: , где с - результат суммирования, z=x⋅y - результат умножения входных чисел, i - номер сумматора, p - модуль. Старший разряд сформированного значения с поступает на выход переноса сумматора 2, остальные разряды представляют разность z-i⋅p и поступают на информационный выход сумматора 2.
До тех пор, пока значение z превышает значение i⋅p, на выходе переноса i-го сумматора 2 будет формироваться логическая «1», которая будет поступать на i-й управляющий вход мультиплексора 5. При превышении значением i⋅p значения z на выходе переноса i-го сумматора 2 сформируется логический «0». При поступлении с выхода переноса i-го сумматора 2 на i-й управляющий вход мультиплексора 5 логического «0» мультиплексор 5 переключит на выход 9 информационный вход, на который подается значение с информационного выхода (i-1)-го сумматора 2. Данное значение будет представлять результат умножения числа x на число у по модулю p.
Рассмотрим работу умножителя на примере.
10
2
10
2
10
2
10
2
10
2
10
2
1
2
2
2
2
2
2
2
3
2
2
2
Пусть х=5=000101, y=3=000011, z=x⋅y=15=001111, p=7=000111,  Как показано выше, i-й сумматор 2 формирует значение , поэтому для второго сумматора i⋅р=2⋅p=14=001110,  для третьего сумматора i⋅p=3⋅р=21=010101,  Тогда первый сумматор 2 сформирует значение c=001111+111000+1=1001000, второй - с=001111+110001+1=1000001, третий - с=0001111+101010+1=0111010.
2
10
Как видно из примера, на выходах переноса первых двух сумматоров 2 сформировано значение «1», на выходе же третьего сумматора 2 сформировано значение «0», поэтому на выход 9 мультиплексора 5 поступит значение с информационного выхода второго сумматора 2, равное 000001=1. Так как (5⋅3)≡1(mod7), то правильность работы устройства очевидна.
10
2
10
2
l0
2
10
2
1
2
2
2
2
10
Пусть теперь х=4=00100, y=3=00011, z=x⋅y=12=01100, р=15=01111,  В этом случае первый сумматор 2 сформирует значение с=01100+10000+1=011101. Так как уже первый сумматор на выходе переноса формирует символ «0», на выход 9 мультиплексора поступит значение с выхода умножителя 1, то есть z=x⋅y=01100=12=(4⋅3)(mod 15).
Эффективность сокращения затрат на оборудование при использовании данного устройства определяется уменьшением количества умножителей на константу и инверторов. В общем случае количество умножителей на константу в предлагаемом устройстве в (2n-2)/(n-3) раз, а инверторов - в 2 раза меньше, чем в устройстве прототипе.