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

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

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

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

Наиболее близким по технической сущности к заявляемому изобретению является умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №2015537, кл. G06F 7/49, 30.06.1994).

Недостатками данного устройства являются его ограниченные функциональные возможности, а именно ограниченный диапазон значений входных чисел х (0<х≤р-1, где р - значение модуля, по которому производится вычисление), а также отсутствие возможности умножения на число, отличное от двух.

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

Цель достигается путем перемножения значений входных чисел х и y, представленных в двоичной форме, с последующим приведением полученного значения z=x×y по модулю р в соответствии со следующим алгоритмом.

При проведении вычислений по модулю р значение z=x×y сравнивается со значением модуля р. Если полученное значение z≥p, то из z вычитается значение модуля р, а полученное в результате значение z₁=z-p вновь сравнивается со значением р. Если и в этом случае значение z₁≥p, то из z₁ вновь вычитается значение р, а полученное в результате значение z₂=z₁-p сравнивается со значением р. Данные операции проводятся до тех пор, пока значение z_n, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение z_n является результатом умножения числа х на число y по модулю р. Если уже на первом шаге входное значение z<p, значение z остается без изменений и является результатом умножения числа х на число y по модулю р.

Предлагаемый умножитель по модулю осуществляет данный метод путем параллельного выполнения n операций (где n - размер умножителя, определяемый количеством входящих в его состав сумматоров), в ходе i-й операции значение z=х×у сравнивается со значением i×p путем вычисления разности z-i×p, где i=1, ..., n. Как только при выполнении i-й операции значение полученной разности станет отрицательным, результатом умножения числа x на число у по модулю р будет являться значение разности, полученное в результате (i-1)-й операции. Диапазон значений входных чисел х и y для данного умножителя определяется размером умножителя и находится в пределах [0, ..., (n/4)p-1].

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

Умножитель по модулю содержит умножитель 1, n сумматоров 2, n инверторов 3, (n-1) умножителей на константу 4 и мультиплексор 5. Входы 6 и 7 служат для подачи двоичных кодов умножаемых чисел х и y, вход 8 служит для подачи двоичного кода модуля р. Выход 9 является выходом устройства.

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

На вход 6 подается двоичный код числа х, на вход 7 - двоичный код числа y, причем оба числа принадлежат диапазону [0, ..., (n/4)р-1], где р - модуль, n - размер умножителя, определяемый количеством сумматоров 2. Данные коды подаются на вход умножителя 1, который на выходе формирует двоичный код числа z=х×у. Код числа z поступает на первые входы сумматоров 2 и на первый информационный вход мультиплексора 5. Со входа 8 двоичный код модуля р подается на входы умножителей на константу 4 и на вход первого инвертора 3, причем значение модуля в k-м умножителе умножается на значение i=(k+1), где k=1, ..., n-1. С выхода k-го умножителя на константу 4 код значения i×p поступает на вход (k+1)-го инвертора 3. B j-м инверторе 3 поступающий на его вход код переводится в инверсный код, который подается на второй вход j-го сумматора 2, где j=1, ..., n. Таким образом, на второй вход каждого сумматора 2 поступает инверсный код значения i×p, где i - номер сумматора. На третий вход каждого сумматора 2 поступает код числа «1», служащий для перевода инверсного кода модуля в дополнительный код.

В общем виде сумматор 2 осуществляет операцию, описываемую выражением: где с - результат суммирования, z=x×y - результат умножения входных чисел, i - номер сумматора, р - модуль. Старший разряд сформированного значения с поступает на выход переноса сумматора 2, остальные разряды представляют разность z-i×p и поступают на информационный выход сумматора 2.

До тех пор, пока значение z превышает значение i×p, на выходе переноса i-го сумматора 2 будет формироваться «1», которая будет поступать на i-й управляющий вход мультиплексора 5. При превышении значением i×p значения z на выходе переноса i-го сумматора 2 сформируется «0». При поступлении на i-й управляющий вход мультиплексора 5 символа «0» с выхода переноса i-го сумматора 2 мультиплексор 5 проключит на выход 9 информационный вход, на который подается значение с информационного выхода (i-1)-го сумматора 2. Данное значение будет представлять результат умножения числа х на число y по модулю р.

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

Пусть x=5₁₀=00101₂, y=3₁₀=00011₂, z=x×y=15₁₀=01111₂, р=4₁₀=00100₂, Как показано выше, i-й сумматор 2 формирует значение поэтому для второго сумматора i×p=2×p=8₁₀=01000₂, для третьего сумматора i×p=3×p=12₁₀=01100₂, для четвертого сумматора i×p=4×p=16₁₀=10000₂, Тогда первый сумматор 2 сформирует значение c₁=01111₂+11011₂+1=101011₂, второй - c₂=01111₂+10111₂+1=100111₂, третий - с₃=01111₂+10011₂+1=100011₂, четвертый - c₄=01110₂+01111₂+1=011111₂.

Как видно из примера, на выходах переноса первых трех сумматоров 2 сформировано значение «1», на выходе же четвертого сумматора 2 сформировано значение «0», поэтому на выход 9 мультиплексора 5 поступит значение с информационного выхода третьего сумматора 2, равное 00011₂=3₁₀. Так как (5×3)(mod 4)=3, то правильность работы устройства очевидна.

Пусть теперь x=4₁₀=00100₂, y=3₁₀=00011₂, z=x×y=12₁₀=01100₂, р=15₁₀=01111₂, В этом случае первый сумматор 2 сформирует значение c₁=01100₂+10000₂+1=011101₂. Так как уже первый сумматор на выходе переноса формирует символ «0», на выход 9 мультиплексора поступит значение с выхода умножителя 1, то есть z=x×y=01100₂=12₁₀=(4×3)(mod 15).

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

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