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

Описание патента на изобретение RU2299461C1

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

Известно устройство для умножения чисел по модулю, содержащее два входных регистра, два дешифратора, три группы элементов ИЛИ, четыре группы элементов И, табличный вычислитель значений вида α′β′(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 вычитается значение модуля р, а полученное в результате значение z1=z-p вновь сравнивается со значением р. Если и в этом случае значение z1≥p, то из z1 вновь вычитается значение р, а полученное в результате значение z2=z1-p сравнивается со значением р. Данные операции проводятся до тех пор, пока значение zn, полученное на n-м шаге вычислений, не станет меньше значения модуля р. В этом случае значение zn является результатом умножения числа х на число 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=510=001012, y=310=000112, z=x×y=1510=011112, р=410=001002, Как показано выше, i-й сумматор 2 формирует значение поэтому для второго сумматора i×p=2×p=810=010002, для третьего сумматора i×p=3×p=1210=011002, для четвертого сумматора i×p=4×p=1610=100002, Тогда первый сумматор 2 сформирует значение c1=011112+110112+1=1010112, второй - c2=011112+101112+1=1001112, третий - с3=011112+100112+1=1000112, четвертый - c4=011102+011112+1=0111112.

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

Пусть теперь x=410=001002, y=310=000112, z=x×y=1210=011002, р=1510=011112, В этом случае первый сумматор 2 сформирует значение c1=011002+100002+1=0111012. Так как уже первый сумматор на выходе переноса формирует символ «0», на выход 9 мультиплексора поступит значение с выхода умножителя 1, то есть z=x×y=011002=1210=(4×3)(mod 15).

Похожие патенты RU2299461C1

название год авторы номер документа
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299460C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2016
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Текеев Заур Хаджи-Муратович
RU2626654C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Карагулян Дмитрий Левонович
  • Мосин Олег Викторович
RU2324972C2
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2316042C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2016
  • Петренко Вячеслав Иванович
  • Текеев Заур Хаджи-Муратович
RU2630386C1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2009
  • Копытов Владимир Вячеславович
  • Петренко Вячеслав Иванович
  • Сидорчук Алеся Вячеславна
RU2445681C2
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ДВОЙНОМУ МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299462C1
СУММАТОР ПО МОДУЛЮ P 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2032934C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ 2007
  • Петренко Вячеслав Иванович
  • Сидорчук Алеся Вячеславовна
  • Кузьминов Юрий Владимирович
RU2368942C2
ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2025897C1

Реферат патента 2007 года УМНОЖИТЕЛЬ ПО МОДУЛЮ

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

Формула изобретения RU 2 299 461 C1

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

Документы, цитированные в отчете о поиске Патент 2007 года RU2299461C1

УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2015537C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1992
  • Краснобаев В.А.
  • Ирхин В.П.
  • Потапов В.В.
  • Можаев Н.И.
RU2023290C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов И.М.
  • Гульбин С.С.
RU2143723C1
Устройство для умножения чисел по модулю 1989
  • Фоменко Олег Николаевич
  • Краснобаев Виктор Анатольевич
  • Ирхин Валерий Петрович
  • Панков Владимир Михайлович
  • Уваров Владимир Николаевич
  • Куцый Сергей Иванович
  • Журавлев Александр Александрович
SU1667055A1
JP 2002251137, 06.09.2002
Сушилка проходного типа для ткани, основы и других подобных материалов 1961
  • Городов К.И.
  • Черкинский Б.М.
SU145533A1

RU 2 299 461 C1

Авторы

Петренко Вячеслав Иванович

Кузьминов Юрий Владимирович

Даты

2007-05-20Публикация

2005-10-05Подача