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

Авторы патента:

G06F7/523 - Способы и устройства для обработки данных с воздействием на порядок их расположения или на содержание обрабатываемых данных (логические схемы H03K 19/00)

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

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

Пусть х=5₁₀-0101₂, y=3₁₀=0011₂, z=x⋅y=15₁₀=1111₂, р=7₁₀=0111₂, . Поскольку разрядность модуля равна трем, то умножение по модулю будет произведено с использованием трех сумматоров 2. Как показано выше, i-й сумматор 2 формирует значение , поэтому на второй информационный вход третьего сумматора поступает , второго сумматора , первого сумматора . С учетом единиц, записываемых в младшие разряды с входа 8, значения слагаемых на сумматорах 2 будут выглядеть следующим образом: 1000₂ на третьем сумматоре, 10001₂ на втором сумматоре и 100011₂ - на первом сумматоре. Тогда первый сумматор 2 сформирует значение с₁=001111₂+100011₂+1 = 0110010₂, второй - с₂ = 01111₂+10001₂+1 = 100001₂, третий - с₃ = 0001₂+1000₂+1 = 01010₂.

Как видно из примера, на выходе переноса первого сумматора 2 сформировано значение «0», поэтому на вход второго сумматора 2 поступит значение с информационного выхода умножителя 1, на выходе переноса второго сумматора 2 сформировано значение «1», поэтому на вход третьего сумматора 3 поступит значение с информационного выхода второго сумматора, равное 00001₂, на выходе третьего сумматора 2 сформировано значение «0», поэтому на выход 6 третьего мультиплексора 3 поступит значение с информационного выхода второго сумматора 2, равное 00001₂=1₁₀. Так как (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.

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

Логический преобразователь // 2629452

Логический преобразователь // 2629451

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

Способ определения похожести составных файлов // 2628922

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

Устройство для мажоритарного выбора сигналов // 2628890

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

Устройство для поиска минимального значения интенсивности размещения в тороидальных системах при направленной передаче информации // 2628329

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

Мажоритарный модуль "три из пяти" // 2628117

Мажоритарный модуль для отказоустойчивых систем // 2626347

Многофункциональный мажоритарный модуль // 2626346

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

Логический вычислитель // 2626345

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

Настраиваемый логический модуль // 2626343

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

Логический вычислитель // 2630391

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

Интегрированная система управления // 2630393

Логический модуль // 2630394

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

Способ передачи команд управления // 2631147

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

Троичный поразрядный умножитель // 2631166

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

Арифметическое устройство // 2632411

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

Устройство для определения количества старших единиц (нулей) в двоичном числе // 2633110

Изобретение относится к области вычислительной техники. Технический результат: расширение функциональных возможностей в части возможности определения старших единичных или нулевых разрядов для двоичных чисел со знаком, а также простое увеличение разрядности входной информации. Результат достигается за счет того, что устройство содержит буферы с тремя состояниями с прямым 5 и инверсным 4 входами разрешения, n разрядов входного двоичного числа D1, D2, …, Dn, знак входного числа Sign, n разрядов внутренней шины X1, Х2, …, Xn, (k+1) разрядов (k=[log2n] меньшее целое) выходного двоичного кода В0, В1, …, Bk, входной блок 1, выходной блок 3, первый элемент И 8 и второй элемент И 9, причем буферы с тремя состояниями объединены в пирамидальную структуру, состоящую из (m-1) ступеней (m=]log2n[ большее целое), и в выходной блок 3, содержащий k буферов с тремя состояниями с инверсным входом разрешения 4 и k буферов с тремя состояниями с прямым входом разрешения 5, при этом каждая i-я ступень 2i (i=1, …, (m-1)) содержит (2i-1) буферов с тремя состояниями с инверсным входом, в каждую i-ю ступень 2i введены логические элементы И 7, а входной блок 1 содержит n буферов с тремя состояниями с инверсным входом разрешения 4 и n буферов с тремя состояниями с прямым входом разрешения и инверсным информационным входом 6. 2 ил., 1 табл.

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

Группа изобретений относится к устройству и способу определения потребности для системы централизованного технического обслуживания (ЦТО) для летательного аппарата. Устройство содержит модуль ввода параметров, модуль проверки, модуль генерирования файлов определения потребности, модуль хранения генерируемых файлов. Для осуществления способа определяют области конфигурирования системы ЦТО, профили пользователей для каждой определенной области, вводят параметры области в зависимости от профилей пользователей, проверяют соответствие введенных параметров областям конфигурирования, генерируют файл конфигурирования ЦТО в ответ на этап проверки. Обеспечивается диагностика в реальном времени общего состояния летательного аппарата и его систем. 2 н. и 6 з.п. ф-лы, 2 ил., 2 табл.

Устройство для поиска минимального значения интенсивности размещения в полносвязных матричных системах при двунаправленной передаче информации // 2634198

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

Логический преобразователь // 2634229

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