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

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

 

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

Известен умножитель по модулю (патент RU 2299461 С1, МПК G06F 7/523, G06F 7/72, 2007), который содержит умножитель, n сумматоров, n инверторов, (n-1) умножителей на константу, где n- размер умножителя, мультиплексор, два выхода для подачи двоичных кодов умножаемых чисел, вход для подачи двоичного кода модуля p, выход.

Недостатком данного устройства являются значительные схемные (аппаратные) затраты на его реализацию.

Основной задачей является снижение аппаратных затрат на выполнение операции умножения по модулю.

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

Указанный технический результат достигается за счет введения 16 двухвходовых элементов И, 6 двухвходовых сумматоров по модулю два, 4 многовходовых сумматоров по модулю два.

При проведении умножения по модулю p(z)=z4+z+1, двух операндов A(z) и B(z), степени которых удовлетворяют условию:

Могут быть получены результаты, которые являются элементами поля Галуа GF(24). В таблице 1 приведены ненулевые элементы поля GF(24), порождаемые неприводимым полиномом p(z)=z4+z+1.

Таблица 1

Так как операнды А и В представляют собой четырехразрядные комбинации, то максимальная степень их полиномиальной формы записи будет равна трем. Поэтому необходимо определить результаты каждого разряда первого операнда A(z) на каждый разряд операнда B(z).

Пусть A{z)=1. Тогда результаты умножения A(z)B(z) по модулю p(z)=z4+z+1 приведены в таблице 2.

Пусть A(z)=z. Тогда результаты умножения приведены в таблице 3.

Пусть A(z)=z2. Тогда результаты умножения приведены в таблице 4.

Пусть A{z)=z3. Тогда результаты умножения приведены в таблице 5.

Обобщая данные, приведенные в таблицах 2-5, можно определить, какие разряды операндов A(z) и B(z) участвуют в получении каждого разряда произведения A(z)B(z) mod p(z). Результаты приведены в таблице 6.

Рассмотрим первую строку данной таблицы. Для того чтобы получить произведение A(z)B(z) mod p(z)=1, при условии, что операнд A(z)=1, необходимо условие, что B(z)=1. Таким образом, для выполнения операции умножения по модулю для данных разрядов операндов достаточно использовать двухвходовой элемент И. Аналогичный результат получается для строки 2, 3, 4, 5, 9, 10, 13, 14, 15 таблицы 6.

Рассмотрим шестую строку таблицы 6. Для того чтобы получить значения произведения A(z)B(z)modp(z)=z при условии, что первый операнд A(z)=z, значение второго операнда A(z)=z может быть 1 или z. Это обусловлено равенствами

z·1modz4+z+1=z,

z·z3 modz4+z+1=z4 mod z4+z+1=z+1,

в произведениях которых присутствует значение z.

Если одновременно подать единичный сигнал на разряды 1 и z3 второго операнда B(z), при условии, что A(z)=z, то получаем результат:

A(z)B(z)modz4+z+1=(z(z3+1))modz4+z+1=(z4+z)modz4+z+1=1.

Данный результат можно получить, если сложить результаты двух произведений по модулю два:

(z·1)modz4+z+1+(z-z3)modz4+z+1=z+z+1=1.

Значит, чтобы решить данную проблему, необходимо использовать двухвходовой сумматор по модулю два, на входы которого подаются сигналы с 1 и z3 второго операнда B(z). Выход этого сумматора по модулю два подключается на второй вход элемента И, на первый вход которого поступает сигнал в разряде z первого операнда A(z). Аналогичный результат получается для строк 6, 7, 8, 11, 12, 16 таблицы 6.

На фигуре 1 приведена структура умножителя по модулю. Он содержит входы 1-4, на которые поступает в двоичном коде первый операнд A(z), входы 5-8, на которые подается двоичный код второго операнда B{z), блок двухвходовых сумматоров по модулю два 9.1-9.6, блок двухвходовых элементов И 10.1-10.16, сумматоры по модулю два 11-14, выходы которых являются выходом умножителя по модулю. При этом младшие разряды «1» первого и второго операндов A(z) и B(z) поступают на входы 1 и 5 соответственно, а старший разряд z3 - соответственно на входы 4 и 8. Первый вход 1 первого операнда A(z) подключен к первым выходам элементов И 10.1-10.4. Второй вход 2 первого операнда A(z) подключен к первым входам элементов И 10.5-10.8. Третий вход, по которому передается разряд z2 первого операнда A(z), подключен к первым входам элементов И 10.9-10.12. Четвертый вход 4 умножителя по модулю, по которому передается разряд z3 первого операнда A(z), подключен к первым входам элементов И 10.13-10.16. Пятый вход 5 умножителя по модулю, по которому подается разряд 1 второго операнда B(z), подключен ко второму входу элемента И 10.1, а также к первым входам сумматоров по модулю два 9.1, 9.3, 9.6. Шестой вход 6 умножителя по модулю, по которому подается разряд z второго операнда B(z), подключен ко вторым входам элементов И 10.2, 10.7, 10.12, 10.13 и первому входу сумматора по модулю два 9.4. Седьмой вход умножителя по модулю, по которому подается разряд z2 второго операнда B(z), подключен ко второму входу элементов И 10.3, 10.8, 10.9 и первому входу сумматоров по модулю два 9.2 и 9.5, а также второму входу сумматора по модулю два 9.4. Восьмой вход 8 умножителя по модулю, по которому подается разряд z3 второго операнда B(z), подключен ко второму входу элементов И 10.4, 10.5 и второму входу сумматоров по модулю два 9.1, 9.2, 9.3, 9.5, 9.6. Выходы сумматоров по модулю два 9.1- 9.6 подключены ко вторым входам элементов И 10.6, 10.10, 10.11, 10.14, 10.15, 10.16 соответственно. Входы сумматора по модулю два 11 соединены с выходами элементов И 10.1, 10.5, 10.9, 10.13. Входы сумматора по модулю два 12 соединены с выходами элементов И 10.2, 10.6, 10.10, 10.14. Входы сумматора по модулю два 13 соединены с выходами элементов И 10.3, 10.7, 10.11, 10.15. Входы сумматора по модулю два 14 соединены с выходами элементов И 10.4, 10.8, 10.12, 10.16. Выход сумматора по модулю два 11 соответствует младшему разряду произведения, а выход сумматора по модулю два 14 - старшему разряду произведения A(z)B(z) mod p(z).

Рассмотрим работу умножителя по модулю. Пусть A(z)=z3+z2+1 и B(z)=z3+1. Тогда их произведение по модулю p(z)=z4+z+1 равно:

(z3+z2+1)(z3+1)modz4+z+1=(z6+z5+z3+z3+z2+1)modz4+z+1=(z6+z5+z2+1)modz4+z+1=z3+z2+z+1.

В соответствии с выбранными значениями A(z) и B(z) единичный сигнал будет на входах 1, 3, 4, 5, 8 умножителей по модулю, а на остальных - нулевой сигнал. Выходные сигналы сумматоров по модулю два 9.1- 9.6 приведены в таблице 7.

Таким образом, единичный сигнал будет на выходах сумматоров по модулю два 9.2, 9.5.

Выходные сигналы элементов И 10.1- 10.16 приведены в таблице 8.

Таким образом единичный сигнал будет на выходе элементов 10.1, 10.4, 10.10, 10.15.

Выходные сигналы сумматоров по модулю два 11-14 определяются из таблиц 9-12.

Таким образом, на выходе умножителя по модулю получен двоичный код произведения 1111, который в полиномиальной форме имеет вид z3+z2+z+1, что соответствует контрольному просчету.

1. Умножитель по модулю имеет четыре входа для первого операнда, четыре входа для второго операнда, шесть двухвходовых сумматоров по модулю два, 16 элементов И, четыре многовходовых сумматора по модулю два, при этом младшие разряды первого и второго операндов поступают на первый и пятый входы соответственно, а старший разряд операндов - соответственно на четвертый и восьмой входы умножителя по модулю, первый вход умножителя по модулю подключен к первым входам 1-4 элементов И, второй вход подключен к первым входам 5-8 элементов И, третий вход подсоединен к первым входам 9-12 элементов И, четвертый вход умножителя подключен к первым входам 13-16 элементов И, пятый вход умножителя - ко второму входу первого элемента И, а также к первым входам 1, 3, 6 двухвходовых сумматоров по модулю два, шестой вход умножителя по модулю подсоединен ко вторым выходам 2, 7, 12, 13 элементов И и к первому входу 4 двухвходового сумматора по модулю два, седьмой вход умножителя по модулю подключен ко вторым входам 3, 8, 9 элементов И, первому входу 2 и 5, а также ко второму входу 4 двухвходовых сумматоров по модулю два, восьмой вход умножителя по модулю подсоединен ко вторым входам 4 и 5 элементов И и вторым входам 1, 2, 3, 5, 6 двухвходовых сумматоров по модулю два, выходы 1-6 двухвходовых сумматоров по модулю два подключены ко вторым входам 6, 10, 11, 14, 15, 16 элементов И соответственно, вход первого многовходового сумматора по модулю два подключен к выходам 1, 5, 9, 13 элементов И, вход второго многовходового сумматора по модулю два подключен к выходам 2, 6, 10, 14 элементов И, вход третьего многовходового сумматора по модулю два подключен к выходам 3, 7, 11, 15 элементов И, вход четвертого многовходового сумматора по модулю два подключен к выходам 4, 8, 12, 16 элементов И, выходы многовходовых сумматоров по модулю два являются выходом умножителя по модулю, причем выход первого многовходового сумматора по модулю два соответствует нулевому разряду произведения, а выход четвертого многовходового сумматора по модулю два - старшему разряду произведения.



 

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

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

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

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

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

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

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

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

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

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

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

Изобретение относится к области защиты информатики. Технический результат - увеличение эффективности защиты информации от помех и несанкционированного доступа. Устройство защищенного информирования содержит: генератор тактовых импульсов, электронный ключ ввода тактовых импульсов, переключатель тактовых импульсов, устройства ввода и вывода информации, устройство регистрации ввода данных, регистратор с возможностью запоминания их значений состояниями триггеров "включено" и "выключено", логический блок формирования кода, линию связи, устройство приема кода; устройство вывода информации; при этом устройство наделено функцией формирования самозащищенного кода, каждая кодовая комбинация которого состоит из трех составляющих S1, S2 и S3, содержащих соответственно n1, n2 и n3 элементов, с общей их суммой n=n1+n2+n3, образующих в своей совокупности диапазон пространственно-временного изменения расположения и величины информационного содержания второй, средней, составляющей; самоорганизация процесса формирования самозащищенного кода обеспечена реализацией сетевого управления информационными коммуникациями по закону комбинаторики устройства ввода данных, содержащего решетку информационных коммуникаций из пересекающихся m V-образно изогнутых шин с числом узлов их пересечений и, соответственно, их коммуникаций К, равным числу сочетаний из m по два, , пространственно расположенных в виде треугольника и их изгибов вдоль его основания; при отсутствии искажения от воздействия помех и несанкционированного доступа имеем равенство значений параметров элементов каждой составляющей самозащищенного кода, при наличии искажения - их неравенство. 4 ил., 2 табл.

Изобретение относится к способу и аппарату для управления интеллектуальным освещением. Технический результат заключается в точности управления освещением с использованием конфигураций светового эффекта в зависимости от обстановки. Способ включает в себя: получение информации о состоянии текущей обстановки, определение соответствия с информацией о заданном состоянии, генерацию команды управления светом, соответствующей заданному условию обстановки, и отправку сгенерированной команды управления светом системе интеллектуального освещения так, что система интеллектуального освещения создает световой эффект, соответствующий заданному условию обстановки. 3 н. и 14 з.п. ф-лы, 12 ил.

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

Группа изобретений относится к области вычислительной техники и может быть использована в устройствах защиты данных. Техническим результатом является уменьшение объема памяти при заданной разрядности процессоров. Способ содержит этапы, на которых задают разрядность W процессора вычислительной системы, равную целочисленной степени числа 2, задают доступный объем памяти вычислительной системы М бит, задают размер s сообщения S, причем s кратно W, задают значение разрядности n регистра сдвига с линейной обратной связью (РСЛОС) по схеме Галуа, формируют РСЛОС по схеме Галуа, модифицируют РСЛОС, осуществляют R тактов работы модифицированного РСЛОС, вычисляют выходное состояние ячеек модифицированного РСЛОС, получают после R тактов работы РСЛОС линейное преобразование блоков s сообщения S, считывают из ячеек модифицированного РСЛОС блоки s линейно преобразованного сообщения S, объединяют блоки и получают линейно преобразованное сообщение S. 2 н.п. ф-лы, 14 ил., 3 табл.

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

Изобретение относится к системе управления транспортным средством. Технический результат заключается в обеспечении возможности автоматизированного управления транспортным средством. Система содержит транспортное средство, обрабатывающее материалы, включающее в себя: шину сети с абонентским доступом (CAN) и, по меньшей мере, один собственный управляющий модуль, соединенный с шиной CAN транспортного средства, обрабатывающего материалы, которое генерирует относящиеся к транспортному средству данные и пересылает относящиеся к транспортному средству данные по шине CAN, информационное устройство связи, физически соединенное с транспортным средством, обрабатывающим материалы, соединено с шиной CAN транспортного средства, обрабатывающего материалы, в котором интерфейс шины CAN получает и хранит относящиеся к транспортному средству данные от шины CAN, и приемопередатчик, физически соединенный с транспортным средством, обрабатывающим материалы, который соединен с информационным устройством связи, где приемопередатчик передает по радио информацию, относящуюся к данным по транспортному средству по беспроводной сетевой среде, и получает по радио информацию для передачи по шине CAN к, по меньшей мере, одному собственному блоку управления из беспроводной сетевой среды. 2 н. и 15 з.п. ф-лы, 17 ил.

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

Изобретение относится к вычислительной технике и может быть использовано в отказоустойчивых, радиационно-стойких программируемых логических интегральных схемах (ПЛИС) для вычисления логических функций. Техническим результатом является повышение отказоустойчивости. Устройство содержит группу n инверторов переменных, n групп, n - число входных переменных, основных передающих транзисторов по 2i, i=1, n транзисторов в группе, группу 2n инверторов настройки, выходной инвертор, 2n+1-1 подгрупп дополнительных передающих транзисторов для каждого основного четного и нечетного транзистора n групп передающих транзисторов, состоящих из трех транзисторов. В каждый инвертор из группы 2n инверторов настройки, группы n инверторов переменных, выходной инвертор введены три дополнительных транзистора n-МОП и три дополнительных транзистора p-МОП. 5 ил., 3 табл.

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

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

Наверх