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

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

 

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

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

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

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

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

Цель изобретения - увеличение диапазона значений входных чисел.

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

Сущность изобретения заключается в реализации следующего способа умножения на два по модулю.

Пусть требуется умножить число х на два и сформировать остаток r получившегося выражения по модулю p.

Число х лежит в пределах 0<х≤np-1. Перед умножением на два формируется остаток r1 по модулю р двоичного числа х. Для этого х одновременно сравнивается со значениями p, 2p, …, ip, …, np путем вычитания из х этих значений. Таким образом получаются разности х₁=х-р, x₂=x-2p,.… x_i=x-ip, …, х_N=х-nр. То значение x_i,, где i=1, …, n, которое окажется больше 0 и меньше р, и будет результатом формирования остатка r1 по модулю p двоичного числа х. Получившееся значение r1 умножается на два и снова приводится по модулю p тем же способом.

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

Умножитель на два по модулю содержит n+1 сумматоров 1, n+1 инверторов 2, n-1 умножителей 3, 1 мультиплексор 4.1, имеющий n управляющих и (n+1) информационных входов и 1 мультиплексор 4.2, имеющий 1 управляющий и 2 информационных входа. Вход 5 служит для подачи двоичного кода числа х, вход 6 служит для подачи двоичного кода модуля р. Выходы переноса первых n сумматоров 1 подключены к управляющим входам мультиплексора 4.1, а их информационные выходы подключены к информационным входам мультиплексора 4.1. Информационный выход мультиплексора 4.1 подключен к информационному входу (n+1)-го сумматора 1 и информационному входу мультиплексора 4.2. Выход переноса (n+1)-го сумматора 1 подключен к управляющему входу мультиплексора 4.2, информационный выход (n+1)-го сумматора 1 подключен к информационному входу мультиплексора 4.2. Выход мультиплексора 4.2 подключен к выходу 7 и является выходом устройства.

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

На вход 5 подается код числа из диапазона 0<x≤np-1, где х - умножаемое число, p - модуль, n - размер умножителя, определяемый количеством сумматоров 1. Данный код поступает на первые входы первых n сумматоров 1 и на первый информационный вход мультиплексора 4.1. Со входа 6 код модуля (подается на входы умножителей 3, на вход первого и (n+1)-го инвертора 2, причем значение модуля в k-м умножителе умножается на значение i=(k+1), где k=1,.…, n-1. С выхода k-го умножителя 3 код произведения ixp поступает на вход (k+1)-го инвертора 2. В j-м инверторе 2 поступающий на его вход код переводится в инверсный код, который подается на второй вход j-го сумматора 1, где j,.…, n+1. Таким образом, на второй вход каждого сумматора 1 поступает инверсный код значения i×p, где i=1,.…, n - номер сумматора. На вход переноса каждого сумматора 1 поступает код числа «1», служащий для перевода инверсного кода модуля в дополнительный код.

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

До тех пор, пока значение х превышает значение i×p, на выходе переноса i-го сумматора 1 будет формироваться «1», которая будет поступать на i-й управляющий вход мультиплексора 4.1. При превышении значением i×p значения х на выходе переноса i-го сумматора 1 сформируется «0». При поступлении на i-й управляющий вход мультиплексора 4.1 символа «0» с выхода переноса i-го сумматора 1 мультиплексор 4.1 переключит на вход (n+1)-го сумматора 1 и на первый вход мультиплексора 4.2, со сдвигом разрядов на один в сторону старшего разряда, информационный вход, на который подается значение с информационного выхода (i-1)-го сумматора 1. Мультиплексор 4.2 переключит на выход 7 информационный вход с мультиплексора 4.1, если 2 с<p, или информационный вход с сумматора 1, если 2 с≥p. В последнем случае на выходе мультиплексора 4.2 будет значение m=2 с - p. Данное значение будет представлять результат умножения числа х на два по модулю ρ.

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

Пусть Как показано выше, i-й сумматор 1 формирует значение поэтому для второго сумматора для третьего сумматора для четвертого сумматора

Тогда первый сумматор 1 сформирует значение c₁=01111₂+11011₂+1=101011₂, второй c₂=01111₂+10111₂+1=100111₂, третий - с₃=01111₂+10011₂+1=100011₂, четвертый - c₄=01111₂+01111₂+1=011111₂.

Как видно из примера, на выходах переноса первых трех сумматоров 1 сформировано значение «1», на выходе же четвертого сумматора 1 сформировано значение «0», поэтому на выход мультиплексора 4.1 поступит значение с информационного выхода третьего сумматора 1, равное 00011₂=3₁₀.

Полученное значение умножается на 2, путем сдвига разрядов на один в сторону старшего. На первый информационный вход мультиплексора 4.2 и на первый информационных вход сумматора 1 поступает значение 0110₂. (n+1)-ый сумматор 1 формирует значение Т.к. на выходе переноса сумматора 1 сформировано значение «1», поэтому на выход мультиплексора 4.2 поступит значение с информационного выхода сумматора 1, равное 0010₂=2₁₀. Так как (15)(mod 4)=3, (3×2)(mod 4)=2, то правильность работы устройства очевидна.

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