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

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

Известен умножитель на два по модулю, содержащий два сумматора, элементы ИЛИ-НЕ и элементы ИЛИ с соответствующими связями (см. Пухальский Т.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах. Справочник. М.: Радио и связь, 1990, с.205, рис.3.131).

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

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

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

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

Известно, что любое число х, представленное в двоичной форме, можно умножить на два путем сдвига всех разрядов числа на один в сторону старшего с записью значения "0" в младший разряд. При проведении вычислений по модулю р значение а=2х сравнивается со значением модуля. Если полученное значение а≥р, то из а вычитается значение модуля р, а полученное в результате значение а₁=а-р вновь сравнивается со значением р. Если и в этом случае значение а₁≥р, то из а₁ вновь вычитается значение р, а полученное в результате значение а₂=а₁-р сравнивается со значением р. Данные операции проводятся до тех пор, пока значение a_n, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение a_n является результатом умножения числа х на два по модулю р. Если уже на первом шаге входное значение а<р, значение а остается без изменений и является результатом умножения числа х на два по модулю.

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

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

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

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

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

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

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

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

Пусть x=7₁₀=00111₂, 2х=14₁₀=01110₂, p=4₁₀=00100₂, Как показано выше, i-й сумматор 1 формирует значение , поэтому для второго сумматора i×p=2×p=8₁₀=01000₂, для третьего сумматора i×p=3×p=12₁₀=01100₂, для четвертого сумматора i×p=4×p=16₁₀=10000₂, Тогда первый сумматор 1 сформирует значение c₁=01110₂+11011₂+1=101010₂, второй c₂=01110₂+10111₂+1=100110₂, третий - c₃=01110₂+10011₂+1=100010₂, четвертый - c₄=01110₂+01111₂+1=011110₂.

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

Пусть теперь х=3₁₀=0011₂, 2x=6₁₀=0110₂, p=7₁₀=0111₂, В этом случае первый сумматор 1 сформирует значение c₁=0110₂+1000₂+1=01111₂. Так как уже первый сумматор на выходе переноса формирует символ "0", на выход 7 мультиплексора поступит значение со входа 5 умножителя, то есть 2х=0110₂=6₁₀=(3×2)(mod 7).

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей. Техническим результатом является расширение функциональных возможностей за счет расширения диапазона значений входных чисел. Устройство содержит сумматоры, инверторы, умножители, мультиплексор. 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-го сумматора, к третьему входу каждого сумматора подключен вход записи логической единицы, выход мультиплексора является выходом умножителя.