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

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

Иллюстрации

Показать все

Реферат

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

Известно устройство для умножения чисел по модулю, содержащее сумматор и мультиплексор (см. патент РФ №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).

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

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

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

При перемножении значений входных чисел 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_i, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение z является результатом умножения числа x на число у по модулю р. Если уже на первом шаге входное значение z<p, значение z остается без изменений и является результатом умножения числа x на число y по модулю p.

Предлагаемый умножитель по модулю осуществляет данный метод путем параллельного выполнения n-1 операций, где n=2^N-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 является выходом устройства.

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

На вход 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^S-х сумматоров 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.

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

Пусть х=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 сформировано значение «1», на выходе же третьего сумматора 2 сформировано значение «0», поэтому на выход 9 мультиплексора 5 поступит значение с информационного выхода второго сумматора 2, равное 000001₂=1₁₀. Так как (5⋅3)≡1(mod7), то правильность работы устройства очевидна.

Пусть теперь х=4₁₀=00100₂, y=3₁₀=00011₂, z=x⋅y=12_l0=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 раза меньше, чем в устройстве прототипе.

Умножитель по модулю, состоящий из умножителя, (n-1) сумматоров, где n=2^N-1, N - разрядность кода модуля, (n-1)/2-1 умножителей на константу, (n-1)/2 инверторов и мультиплексора, содержащего n информационных и (n-1) управляющих входов, причем вход записи двоичного кода первого из умножаемых чисел подключен к первому входу умножителя, вход записи двоичного кода второго умножаемого числа подключен ко второму входу умножителя, выход которого подключен к первому информационному входу мультиплексора и первым входам всех сумматоров, выход переноса i-го сумматора подключен к i-му управляющему входу мультиплексора, информационный выход i-го сумматора подключен к (i+1)-му информационному входу мультиплексора, где i=1, …, (n-1), ко входу переноса каждого сумматора подключен вход записи логической единицы, вход записи двоичного кода модуля устройства подключен ко входу первого инвертора и ко входу каждого умножителя на константу, выход j-го умножителя на константу соединен со входом (k+1)-го инвертора, где j=1, …, (n-1)/2 -1, а k=1, …,(n-1)/2, выход k-го инвертора соединен со вторым входом соответствующего нечетного i-го сумматора, выход мультиплексора является выходом устройства, отличающийся тем, что выходы k-х инверторов дополнительно подключены ко вторым входам l⋅2^S-х сумматоров, где , s=1, 2, 3 … и со сдвигом на s разрядов в сторону старшего, а к младшим s разрядам соответствующих сумматоров подключен вход записи логической единицы.