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



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

 


Владельцы патента RU 2630386:

Федеральное государственное автономное образовательное учреждение высшего образования "Северо-Кавказский федеральный университет" (RU)

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

 

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

Известно устройство для умножения чисел по модулю, содержащее сумматор и мультиплексор (см. пат. РФ №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), то правильность работы устройства очевидна.

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

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



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано для построения средств автоматики, функциональных узлов систем управления и др. Технический результат заключается в обеспечении однородности состава и упрощении реализации параллельного набора шести простых симметричных булевых функций, зависящих от параллельного набора шести аргументов - входных двоичных сигналов. Логический вычислитель содержит двадцать мажоритарных элементов (11, …, 120), за счет которых обеспечиваются однородность состава и реализация целевых функций без использования настроечных сигналов. 1 ил., 1 табл.

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

Изобретение предназначено для воспроизведения пяти простых симметричных булевых функций, зависящих от пяти аргументов - входных двоичных сигналов, и может быть использовано в системах цифровой вычислительной техники как средство преобразования кодов. Техническим результатом является расширение функциональных возможностей за счет обеспечения параллельной реализации упомянутых функций. Логический модуль содержит девять элементов И (11, …, 19) и девять элементов ИЛИ (21, …, 29) и связи между ними. 1 ил.

Изобретение относится к вычислительным комплексам и компьютерным сетям с устройствами для обработки данных с воздействием на порядок расположения данных и на их содержание. Техническим результатом является расширение функциональных возможностей за счет автоматического преобразования данных об исходной команде управления, сформированных в ведущей системе управления, в данные о функции этой команды, передачи их по адресу, формирования данных о выходной команде управления с учетом данных о функции и передачи их в ведомую систему управления. Способ характеризуется этапами, в которых на передающей стороне принимают данные об исходной команде, включая адрес ведомой системы управления, инструкцию, которую надо выполнить, информацию, используемую при этом. При этом данные об инструкции принимаются в кодах ведущей системы управления. Исходные данные преобразуются в данные о функции команды и передаются по адресу в сети передачи данных. На приемной стороне производят обратные преобразования с учетом данных о функции и передают в ведомую систему управления данные о команде, включая инструкцию, которую надо выполнить, адрес компонента, над которым должны выполняться действия, и информацию, используемую при этом. Причем данные об инструкции передаются в кодах ведомой системы управления. 4 з.п. ф-лы, 8 ил.

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

Изобретение относится к вычислительной технике и может использоваться в специализированных цифровых вычислительных машинах, работающих в двоичной системе счисления с числами с фиксированной запятой. Технический результат - повышение достоверности определения переполнения сумматора. Арифметическое устройство содержит первый и второй регистры, регистр результата, комбинационный сумматор, триггер, логические элементы И, И-НЕ, а также НЕ, связанные с триггером, фиксирующие разные знаки слагаемых и определяющие факт переполнения сумматора с учетом переносов из (и в) знакового разряда сумматора при осуществлении им операций сложения и умножения. 1 ил., 1 табл.
Наверх