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

Классы МПК:G06F7/523 только для умножения
G06F7/72 с помощью арифметического остатка
Автор(ы):, ,
Патентообладатель(и):Государственное образовательное учреждение высшего профессионального образования "Ставропольский государственный университет" (RU)
Приоритеты:
подача заявки:
2009-12-15
публикация патента:

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

умножитель на два по модулю, патент № 2445681

Формула изобретения

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

Описание изобретения к патенту

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

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

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

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

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

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

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

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

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

Число х лежит в пределах 0<хумножитель на два по модулю, патент № 2445681 np-1. Перед умножением на два формируется остаток r1 по модулю р двоичного числа х. Для этого х одновременно сравнивается со значениями p, 2p, умножитель на два по модулю, патент № 2445681 , ip, умножитель на два по модулю, патент № 2445681 , np путем вычитания из х этих значений. Таким образом получаются разности х1=х-р, x2=x-2p,.умножитель на два по модулю, патент № 2445681 xi=x-ip, умножитель на два по модулю, патент № 2445681 , хN=х-nр. То значение xi,, где i=1, умножитель на два по модулю, патент № 2445681 , 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умножитель на два по модулю, патент № 2445681 np-1, где х - умножаемое число, p - модуль, n - размер умножителя, определяемый количеством сумматоров 1. Данный код поступает на первые входы первых n сумматоров 1 и на первый информационный вход мультиплексора 4.1. Со входа 6 код модуля (подается на входы умножителей 3, на вход первого и (n+1)-го инвертора 2, причем значение модуля в k-м умножителе умножается на значение i=(k+1), где k=1,.умножитель на два по модулю, патент № 2445681 , n-1. С выхода k-го умножителя 3 код произведения ixp поступает на вход (k+1)-го инвертора 2. В j-м инверторе 2 поступающий на его вход код переводится в инверсный код, который подается на второй вход j-го сумматора 1, где j,.умножитель на два по модулю, патент № 2445681 , n+1. Таким образом, на второй вход каждого сумматора 1 поступает инверсный код значения i×p, где i=1,.умножитель на два по модулю, патент № 2445681 , n - номер сумматора. На вход переноса каждого сумматора 1 поступает код числа «1», служащий для перевода инверсного кода модуля в дополнительный код.

В общем виде n сумматоров 1 осуществляют операцию, описываемую выражением:умножитель на два по модулю, патент № 2445681 где с - результат суммирования, х - число, i - номер сумматора, p - модуль. Старший разряд сформированного значения с поступает на выход переноса сумматора 1, остальные разряды представляют разность х - i×p и поступают на информационный выход сумматора 1. (n+1)-ый сумматор 1 осуществляют операцию, описываемую выражением:умножитель на два по модулю, патент № 2445681 где 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 сумножитель на два по модулю, патент № 2445681 p. В последнем случае на выходе мультиплексора 4.2 будет значение m=2 с - p. Данное значение будет представлять результат умножения числа х на два по модулю умножитель на два по модулю, патент № 2445681 .

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

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

Тогда первый сумматор 1 сформирует значение c1=011112+110112+1=101011 2, второй 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 формирует значение умножитель на два по модулю, патент № 2445681 Т.к. на выходе переноса сумматора 1 сформировано значение «1», поэтому на выход мультиплексора 4.2 поступит значение с информационного выхода сумматора 1, равное 00102 =210. Так как (15)(mod 4)=3, (3×2)(mod 4)=2, то правильность работы устройства очевидна.

Класс G06F7/523 только для умножения

способ перемножения десятичных чисел -  патент 2525477 (20.08.2014)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2500018 (27.11.2013)
устройство предсказания исключительной ситуации "потеря точности" блока операции "умножение с накоплением" -  патент 2498392 (10.11.2013)
способ и устройство умножения чисел в коде "1 из 4" -  патент 2467377 (20.11.2012)
способ и устройство умножения двоично-десятичных кодов -  патент 2386998 (20.04.2010)
функциональная структура умножителя, в котором входные аргументы имеют формат двоичной системы счисления f(2n), а выходные аргументы сформированы в формате позиционно-знаковой системы счисления f(+/-) -  патент 2373563 (20.11.2009)
устройство для умножения чисел по модулю -  патент 2338241 (10.11.2008)
устройство для умножения чисел по произвольному модулю -  патент 2316042 (27.01.2008)
устройство для умножения чисел по модулю -  патент 2313124 (20.12.2007)
умножитель по модулю -  патент 2299461 (20.05.2007)

Класс G06F7/72 с помощью арифметического остатка

устройство для преобразования из полиномиальной системы классов вычетов в позиционный код -  патент 2513915 (20.04.2014)
способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах -  патент 2509345 (10.03.2014)
устройство для определения знака модулярного числа -  патент 2503995 (10.01.2014)
устройство для сравнения чисел, представленных в системе остаточных классов -  патент 2503992 (10.01.2014)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2500018 (27.11.2013)
накапливающий сумматор по модулю -  патент 2500017 (27.11.2013)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2485574 (20.06.2013)
полный одноразрядный сумматор по модулю -  патент 2484519 (10.06.2013)
устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в эвм, функционирующих в системе остаточных классов -  патент 2483346 (27.05.2013)
ячейка однородной вычислительной среды, однородная вычислительная среда и устройство для конвейерных арифметических вычислений по заданному модулю -  патент 2477513 (10.03.2013)
Наверх