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

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

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

Известен умножитель на два по модулю, содержащий сумматор и мультиплексор (см. патент РФ №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 путем вычитания из х этих значений. Таким образом получаются разности х1=х-р, x2=x-2p,.… xi=x-ip, …, хN=х-nр. То значение xi,, где 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 сформирует значение c1=011112+110112+1=1010112, второй c2=011112+101112+1=1001112, третий - с3=011112+100112+1=1000112, четвертый - c4=011112+011112+1=0111112.

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

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

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

название год авторы номер документа
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299461C1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299460C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2016
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Текеев Заур Хаджи-Муратович
RU2626654C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2016
  • Петренко Вячеслав Иванович
  • Текеев Заур Хаджи-Муратович
RU2630386C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Карагулян Дмитрий Левонович
  • Мосин Олег Викторович
RU2324972C2
СУММАТОР ПО МОДУЛЮ P 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2032934C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2316042C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2020
  • Петренко Вячеслав Иванович
RU2751802C1
Устройство для вычисления свертки 1989
  • Каневский Юрий Станиславович
  • Корчев Дмитрий Вениаминович
  • Клименко Мария Константиновна
  • Весельская Маргарита Сергеевна
SU1688259A1
ПОЛИНОМИАЛЬНЫЙ МОДУЛЯРНЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ С ОБНАРУЖЕНИЕМ ОШИБОК 2015
  • Вишневский Артем Константинович
  • Михеев Николай Александрович
  • Жданов Сергей Георгиевич
RU2586574C1

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

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

Формула изобретения RU 2 445 681 C2

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

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

УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299460C1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2015537C1
WO 2008028529 A1, 13.03.2008.

RU 2 445 681 C2

Авторы

Копытов Владимир Вячеславович

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

Сидорчук Алеся Вячеславна

Даты

2012-03-20Публикация

2009-12-15Подача