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

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

Иллюстрации

Показать все

Реферат

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

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

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

Известно устройство для умножения чисел на два по модулю, содержащее сумматоры, инверторы, умножители и мультиплексор (см. пат. РФ №2299460, кл. G06F 7/523, 05.10.2005).

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

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

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

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

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

Сущность изобретения заключается в реализации следующего способа перемножения чисел x и y по модулю p. При перемножении значений входных чисел x и y, представленных в двоичной форме, с последующим приведением полученного значения z=x⋅y по модулю p, значение z_i сравнивается со значением 2^(n-i)p, где i=1…n - шаг вычислений. Если полученное значение z_i≥2^(n-i)p, то из z_i на i шаге вычислений вычитается значение 2^(n-i)р, и значению z_i+1 присваивается значение z_i-2^(n-i)p. Если же z_i<2^(n-i)p, то значению z_i+1 присваивается значение z_i. На первом шаге вычислений в качестве значения z₁ принимается значение z=x⋅y. На n-м шаге вычислений значение z_i является результатом умножения числа x на число y по модулю р. Значение 2^(n-i)p вычисляется посредством последовательного умножения значения модуля p на 2 путем сдвига кода модуля на один разряд в сторону старшего. Таким образом, можно исключить из схемы умножители на константу. Результатом умножения числа x на число y по модулю p будет являться значение разности, полученное в результате n-й операции. Предлагаемый умножитель по модулю осуществляет данный метод путем выполнения n операций, где n - разрядность модуля.

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

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

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

На вход 4 подается двоичный код числа x, на вход 5 - двоичный код числа y, причем оба числа принадлежат диапазону [0, …, (р-1)], где p - модуль. Данные коды подаются на входы умножителя 1, который на выходе формирует двоичный код числа z=x⋅y. Код числа z поступает на первый информационный вход первого сумматора 2 и на первый информационный вход первого мультиплексора 3. С входа 7 инвертированный двоичный код модуля p подается на вторые информационные входы сумматоров 2, начиная с n-го, причем на каждый последующий сумматор значение модуля p поступает со сдвигом на один разряд в сторону старшего путем непосредственного сдвига. При этом для перевода инверсного кода модуля в сумматорах 2 в дополнительный код необходимо подать на вход переноса 8 каждого сумматора логические единицы в младшие разряды в количестве, равном количеству сдвигов инвертированного кода модуля p относительно первоначального значения. Таким образом, на второй информационный вход каждого i-го сумматора 2 поступает код значения , где i - номер сумматора.

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

Когда значение z превышает значение 2^(n-i)⋅p, на выходе переноса i-го сумматора 2 будет формироваться логическая «1», которая будет поступать на управляющий вход i-го мультиплексора 3. Тогда i-й мультиплексор 3 будет переключать на выход значение с выхода i-го сумматора 2. Если значение z окажется меньше значения 2^(n-i)⋅p, то на выходе переноса i-го сумматора 2 сформируется логический «0». При поступлении на управляющий вход i-го мультиплексора 3 логического «0» с выхода переноса i-го сумматора 2, i-й мультиплексор 3 переключит на выход значение с выхода (i-1)-го мультиплексора 3. Значение с выхода n-го мультиплексора на выходе устройства 6 будет представлять результат умножения числа x на число y по модулю p.

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

Пусть х=5₁₀-0101₂, y=3₁₀=0011₂, z=x⋅y=15₁₀=1111₂, р=7₁₀=0111₂, . Поскольку разрядность модуля равна трем, то умножение по модулю будет произведено с использованием трех сумматоров 2. Как показано выше, i-й сумматор 2 формирует значение , поэтому на второй информационный вход третьего сумматора поступает , второго сумматора , первого сумматора . С учетом единиц, записываемых в младшие разряды с входа 8, значения слагаемых на сумматорах 2 будут выглядеть следующим образом: 1000₂ на третьем сумматоре, 10001₂ на втором сумматоре и 100011₂ - на первом сумматоре. Тогда первый сумматор 2 сформирует значение с₁=001111₂+100011₂+1 = 0110010₂, второй - с₂ = 01111₂+10001₂+1 = 100001₂, третий - с₃ = 0001₂+1000₂+1 = 01010₂.

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

Эффективность сокращения затрат на оборудование при использовании данного устройства определяется сокращением всех умножителей на константу и инверторов.

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