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

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

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

Известно устройство для умножения чисел по модулю, содержащее сумматор и мультиплексор (см. пат. РФ №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, значение zi сравнивается со значением 2(n-i)p, где i=1…n - шаг вычислений. Если полученное значение zi≥2(n-i)p, то из zi на i шаге вычислений вычитается значение 2(n-i)р, и значению zi+1 присваивается значение zi-2(n-i)p. Если же zi<2(n-i)p, то значению zi+1 присваивается значение zi. На первом шаге вычислений в качестве значения z1 принимается значение z=x⋅y. На n-м шаге вычислений значение zi является результатом умножения числа 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.

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

Пусть х=510-01012, y=310=00112, z=x⋅y=1510=11112, р=710=01112, . Поскольку разрядность модуля равна трем, то умножение по модулю будет произведено с использованием трех сумматоров 2. Как показано выше, i-й сумматор 2 формирует значение , поэтому на второй информационный вход третьего сумматора поступает , второго сумматора , первого сумматора . С учетом единиц, записываемых в младшие разряды с входа 8, значения слагаемых на сумматорах 2 будут выглядеть следующим образом: 10002 на третьем сумматоре, 100012 на втором сумматоре и 1000112 - на первом сумматоре. Тогда первый сумматор 2 сформирует значение с1=0011112+1000112+1 = 01100102, второй - с2 = 011112+100012+1 = 1000012, третий - с3 = 00012+10002+1 = 010102.

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

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

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

название год авторы номер документа
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2016
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Текеев Заур Хаджи-Муратович
RU2626654C1
УМНОЖИТЕЛЬ ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299461C1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2009
  • Копытов Владимир Вячеславович
  • Петренко Вячеслав Иванович
  • Сидорчук Алеся Вячеславна
RU2445681C2
Устройство для умножения чисел 1990
  • Бобровский Алексей Иванович
  • Прохорович Андрей Михайлович
SU1714595A1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299460C1
ПРОГРАММИРУЕМЫЙ ЦИФРОВОЙ ФИЛЬТР 1991
  • Басюк М.Н.
  • Попов А.А.
RU2006936C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
  • Карагулян Дмитрий Левонович
  • Мосин Олег Викторович
RU2324972C2
Устройство для умножения комплексных чисел в модулярной системе счисления 1987
  • Василевич Леонид Николаевич
  • Коляда Андрей Алексеевич
  • Селянинов Михаил Юрьевич
SU1587503A1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ 2006
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2316042C1
ВЫЧИСЛИТЕЛЬНЫЙ ЭЛЕМЕНТ ДЛЯ ОСУЩЕСТВЛЕНИЯ БЫСТРОЙ СВЕРТКИ 1991
  • Куликов А.Л.[Ua]
  • Брандис П.А.[Ua]
  • Аблехин Д.М.[Ua]
RU2028666C1

Иллюстрации к изобретению RU 2 630 386 C1

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей. Техническим результатом является сокращение объема используемого оборудования умножителя по модулю за счет исключения из схемы всех умножителей на константу и инверторов. Для этого предлагаемый умножитель по модулю осуществляет данный метод путем выполнения n операций, где n - разрядность модуля. В ходе i-й операции значение z=x⋅y (где x и y - значения входных чисел) сравнивается со значением 2(n-i)⋅p путем вычисления разности z-2(n-i)⋅p, где i=1, …, n. Результатом умножения числа x на число y по модулю p будет являться значение разности, полученное в результате n-й операции. Значение 2(n-i)⋅p вычисляется посредством последовательного умножения значения модуля на 2 путем сдвига на один разряд кода модуля p в сторону старшего. Таким образом, можно исключить из схемы умножители на константу. Диапазон значений входных чисел для данного умножителя определяется размером умножителя и находится в пределах [0, …, (р-1)]. 1 ил.

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

Умножитель по модулю, состоящий из умножителя, 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.

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

УМНОЖИТЕЛЬ ПО МОДУЛЮ 2005
  • Петренко Вячеслав Иванович
  • Кузьминов Юрий Владимирович
RU2299461C1
УМНОЖИТЕЛЬ НА ДВА ПО МОДУЛЮ 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2015537C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ S-ИЧНЫХ ЦИФР В ПОЗИЦИОННО-ОСТАТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ 1991
  • Евстигнеев В.Г.
  • Ермакова Т.Б.
  • Кошарновский А.Н.
  • Крюков В.П.
RU2006919C1
US 5784306 A1, 21.07.1998.

RU 2 630 386 C1

Авторы

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

Текеев Заур Хаджи-Муратович

Даты

2017-09-07Публикация

2016-11-28Подача