Устройство для формирования остатка по произвольному модулю от числа

 

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования сигнальнокодовых конструкций в конечных полях. Цель изобретения - расширение функциональных возможностей за счет обеспечения формирования индексов мультипликативных групп полей Галуа GF(P). Устройство содержит блок умножения 1, блоки сравнения 2,3, вычитатель 4, регистры 5,6, счетчик 7, группы 8 и 9 элементов ИЛИ, группу 10 элементов И, элементы ИЛИ 11-13, формирователи импульсов 14,15, элемент задержки 16, вход Начало вычислений 17, вход модуля 18, входы 19 записи первообразного элемента поля, входы 20 элемента поля, выход Конец вычислений 21, выходы индекса 22. Если 0-первообразный элемент поля GF(P), то для любого элемента a GF(P) существует единственное целое число GF (Р) такое, что а в г , которое и называется индексом элемента а по основанию в. 1 ил. ч

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (si)s H 03 М 7/18

ГОСУДАРСТВЕННЫИ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4759135/24 (22) 15,11.89 (46) 23.10,91. Бюл. М 39 (72) И.И,Сныткин, В.И.Петренко и А.М,Еремин (53) 681.3(088.8) (56)Авторское свидетельство СССР

М 1185339, кл. 6 06 F 11/08, 1984.

Авторское свидетельство СССР

М 1396281, кл. Н 03 M 7/18, 1986. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

0Т ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования сигнальнокодовых конструкций в конечных полях.

Цель изобретения — расширение функцио„„SU„„1б8б702 А1 нальных возможностей за счет обеспечения формирования индексов мультипликативных групп полей Галуа GF(P). Устройство содержит блок умножения 1, блоки сравнения 2,3, вычитатель 4, регистры 5,6, счетчик

7, группы 8 и 9 элементов ИЛИ, группу 10 элементов И, элементы ИЛИ 11 — 13, формирователи импульсов 14,15, элемент задержки 16, вход "Начало вычислений" 17, вход модуля 18, входы 19 записи первообразного элемента поля, входы 20 элемента поля, выход "Конец вычислений" 21, выходы индекса

22. Если 0-первообразный элемент поля

GF(P), то для любого элемента à G F(P) существует единственное целое число гс- GF (P) такое, что а = О ", которое и называется индексом элемента а по основанию О. 1 ил, 1686702

Изобретение относится к вычислительной технике v vo»(eT быть vcrlorlb3OBBHO B устройствах для формирования сигнальнокОдовых кОнструкций в конечных полях.

Цель изобретения — расширение функциональных возможностей за счет обеспечения формирования (яндексов элементов мультипликативных групп полей Галуа

GF(P).

На чертеже приведена схема устройства, Устройство содержи блок 1 умножения, блоки 2 и 3 сравнения, вы-,итатель 4, регистры 5 и 6, счетчик 7, группы 8 и 9 элементов ИЛИ, группу10элементов И, элементы NflN 11-13, формирователи 14 и 15 импульсов, элемент 16 задержки, вход "Начало вычислений" 17, входы 18 разрядов модуля, входы 19 записи первообразного элемента поля, входы 20 элемента поля, выход "Конец вычислений" 21, выходы 22 индекса.

Устройство работает следующим обраЗОМ.

Если О-первообразный элемент поля

GF(P), то для любого элемента BaGF(P) существует единственное целое число r e GF(P) такое, что а =- 0, которое и называется индексом элемента а по основанию О.

В исходном состоянии Все регистры.обнулены (не показано). Импульс "Начало Вычислений" поступает на вход 17 и обнуляет счетчик 7 и осушествляет запись единицы в регистp множимого блОКЗ 1 умно»(ения. 4одуль, rlo которому осуществляется фоомировзние Остатков, задается параллельным двоичным кОдОм, подаваемым нз вход 18, Импульс "Начало вычислений", прОйдя через элем8НТ 16 задеря(к 1, через элемент ИЛИ 13 запускает блок 1 умножения. В регистр множителя блока 1 умнохсения по Входу 19 Записывается первообрззный элемен поля, После пер8мнОжения импульс конца умножения под считывается счетчиком 7 и, пройдя через элемент ИЛИ 12, пос.гупает нз вход разр шения сравнения блока 2 сравнения. 1(од произведения проходит через группу 8 элементов ИЛИ на информационный вход блоKB 2 сраВнения, нз Дру1ОН ЙнформзцNOHHblw

Вход которого с Bxo+8 18 rloc rl88T Kop, No- дуля, В результате сравнения могут возникнуть следующие ситуации.

ПроизвеДение по сВОему значению меньше мОдуля. В этОм случз8 блок 2 сравнения Выдз8т импульс по Выходу "Меньше", который поступает на Вход элемента ИЛИ

11 и нз вход разрешения зап си ре.:-р

Нз информационный ВХОД регистра 5 В это(момент подается код произведения с выходов группы 8 элементов ИЛИ. В результате код произведения оказывается записанным в регистре 5.

Если произведение по своему значению численно равно модулю, блок 2 сравнения выдает импульс по выходу "Равно", который обнуляет регистр 5 и через элемент ИЛИ 11 поступает на разрешающий вход блока 3 сравнения, Если произведение по своему значению больше модуля, блок 2 сравнения выдает импульс по Выходу "Больше", который поступает на вход формирователя 14 импульсов и на Вход разрешения вычитателя 4. На вход вычитаемого вычитателя 4 поступает значение модуля с входа 18 устройства, а на вход уменьшаемого — значение произведения через группу 9 элементов ИЛИ. Значение разности с выхода вычитателя 4 под

Воздействием импульса, сформированного. формирователем 14 импульсов, по фронту входного импульса записывается в регистр 6, По срезу импульса, сформированного формирователем 14 импульсов, формирователь 15 импульсов сформирует импульс, ко-горый открывает группу 10 элементов И и поступает через элемент ИЛИ 12 на вход разрешения блока 2 сравнения, Код числа, записанного в регистр 6, через группу 10 элементов И и группу 8 элементов ИЛИ поступает на вход блока 2 сравнения, на другой вход которого поступает с входа 18 код модуля. Под действием импульса с выхода элемента ИЛИ 12 блок 2 сравнивает коды чисел, поступающие на его входы. Б результате сравнения вновь могут возникнуть описанные выше три ситуации. Процесс

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

20 устройства, Если остаток от проиэведения не равен элементу поля, то с выхода "He равно" блока 3 сравнения импульс поступает на вход элемента ИЛИ 13 и с его выхода на запускающий вход блока 1 умножения.

Процесс формирования повторяется снача"".à, а количество перемножений подсчитыВается сч8тчиком 7.

Если остаток OT произведения по модулю численно равен элементу поля, то с вы1686702 хода "Равно" блока 3 сравнения поступает импульс, который обнуляет регистр множимого блока 1 умножения, и поступает на выход 21 "Конец вычисления", свидетельствуя о том, что вычисление законно, а на выходах счетчика 7 сформирован индекс от заданного на входах 20 устройства элемента поля по первообраэному элементу, заданному на входах 19 устройства. ходом "Конец вычислений" устройства и соединен с входом разрешения выдачи результата счетчика и входом установки в нулевое состояние блока умножения, выход

"Конец умножения" которого соединен с вторым входом второго элемента ИЛИ и счетным входом счетчика, выходы разрядов которого являются выходами индекса устройства.

Составитель В. Горохов

Техред M.Ìîðãåíòàë Корректор О. Кравцова

Редактор M. Янкович

Заказ 3611 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

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

Устройство для формирования остатка по произвольному модулю от числа, содержащее вычитатель, первый блок сравнения, два регистра, две группы элементов ИЛИ, группу элементов И, первый и втооой элементы ИЛИ и два формирователя импульсов, причем входы разрядов модуля устройства соединены с входами соответствующих разрядов вычитаемого вычитателя и соответствующими информационными входами первой группы первого блока сравнения, выходы "Меньше" и "Равно" которого соединены соответственно с первыми и вторыми входами первого элемента ИЛИ и соответственно с входами разрешения записи и установки в нулевое состояние первого регистра, информационные входы которого объединены с соответствующими входами второй группы первого блока сравнения и подключены к выходам соответствующих элементов ИЛИ первой группы, первые и вторые входы которых попарно объединены с первыми и вторыми входами соответствующих элементов ИЛИ второй группы, выходы которых соединены с входами соответствующих разрядов уменьшаемого вычитателя, выходы разрядов которого соединены с соответствующими информационными входами первого регистра, выходы разрядов которого соединены с первыми входами соответствующих элементов И группы, выходы которых соединены с первыми входами соответствующих элементов

ИЛИ первой группы, выход второго элемента ИЛИ соединен с входом разрешения сравнения первого блока сравнения, выход

"Меньше" которого соединен с входом разрешения вычитания вычитателя и входом

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

GF(P), в него введены блок умножения, счетчик, второй блок сравнения, третий элемент

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