Устройство для формирования элементов мультипликативных групп полей галуа @
Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа GF(P) и формирования кодовых рекуррентных последовательностей. построение которых основы1зается на теории полей Галуа GF(P). Цель изобретения - расширение функциональных возможностей устройства за счет формирования элементов мультипликативных групп полей Галуа GF(Р) при любом модуле Р. Устройство содержит блок умножения, элементы И, ИЛИ, ИЛИ-НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй сумматоры , первый и второй элементы задержки , регистр, счетчик, формирователь импульсов, дифференциальную цепочку . В основу работы устройства положен алгоритм последовательного определения а; 9 (mod р), для i 0, 1, ...,Р-1 . Устройство позволяет формировать элементы мультипликативных групп полей Галуа GF(P) при любом модуле Р. 1 нл. ю СЛ
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИН (ц 4 G 06 Р 15/20
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
Н А ВТОРСИОМУ СВИДЕТЕЛЬСТВУ
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3854482/24-24 (22) 31,10,84 (46) 07.06.86.Бюл. № 21 (72) И. И. Сныткин и В. И. Петренко (53) 681.32(088.8) (56) Авторское свидетельство СССР № 4073!3, кл. С 06 F 11/08, 1971.
Авторское свидетельство СССР
¹ 849895, кл. G 06 F 15/20, 1979. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ
ЭЛЕМЕНТОВ МУЛЬТИПЛИКАТИВНЫХ ГРУПП
ПОЛЕЙ ГАЛУА GF(P) (57) Изобретение относится к вычисли тельной технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа GF(P) и формирования кодовых рекуррентных последовательностей, „„SU„„1236497 A 1 построение которых основывается на теории полей Галуа GF(P). Цель изобретения — расширение функциональных возможностей устройства за счет формирования элементов мультипликативных групп полей Галуа GF(P) при любом модуле P. Устройство содержит блок умножения, элементы И, ИЛИ, ИЛИ НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй сумматоры, первый и второй элементы задержки, регистр, счетчик, формирователь импульсов, дифференциальную цепочку. В основу работы устройства положен алгоритм последовательного определения а; = 8 (mod P), для
= О, 1, ...,Р-1 ° Устройство позволяет формировать элементы мультипликативных групп полей Галуа GF(P) при любом модуле P. 1 ил.
236497 2
Построение и функционирование устройства основано на алгоритме форми рования элементов мультипликативных групп полей Галуа GF(P), представлен ном в виде
1 1
Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа GF(P) и формирования кодовых рекуррентных последовательностей, построение которых оСновывается на теории полей Галуа GF(P) .
Целью изобретения является расширение функциональных возможностей устройства за счет формирования элементов мультипликативных групп полей
Галуа GF(P) для произвольного моду ля P.
На чертеже показана функциональная схема устройства формирования элементов мультипликативных групп полей Галуа GF(P) .
Устройство содержит блок 1 дифференцирования, первый элемент ИЛИ 2, элемент ИЛИ-НЕ 3, группу элементов
ИСКЛОЧАЮ1ЦЕЕ ИЛИ 4-1 - 4-К, регистр 5, счетчик 6, сумматор 7, формирователь 8 импульсов, элемент И 9, группу элементов И 10 1-10 К, первый элемент ll задержки, второй элемент 12 задержки, второй элемент ИЛИ 13, сумматор 14, блок 15 умножения, элемент
ИСКЛЮЧАЮЩЕЕ ИЛИ 16, третий элемент
ИЛИ 17, четвертый элемент ИЛИ 18,, вход 19 записи первообразного элемента, первый управляющий вход 20 записи единицы, вход 21 сигнала начала работы устройства, второй управляющий вход 22 обнуления множимого, вход 23 записи значения приводящего модуля, тактовый вход 24. а 9 (mod P) при i 0,1,...,P- 1, Вычисление а; складывается из операций вычисления значения 8 и приведения 8 по модулю P в полях GF(P) .
Работа устройства для каждого значения P описывается сле1цующей последовательностью. а< А,(mod P) где A,èÎ; а в » А (znod Р), где А а, 9 6 (mod Р)1 е е е, а а А, (mod Р), где А - а,, g = д (mod Р); и т.д.
Формирования остаточных классов по произвольному модулю Р происходит путем вычитания из числа А q раз выбранный модуль Р, до тех пор, пока не будет выполняться условие А „—
-qP1 = а„ i Р, ° Равенство остатка а„ модулю Р; означает тождественное равенство нулю числа A „, т. е, А „
=(а - Р; ) = 0(mod Р) .
Устройство работает следующим образом.
Перед началом работы на вход 22 поступает импульс, который обнуляет регистр множимого блока 15 и счетчик
6, на вход 20 поступает импульс, обнуляющий регистр 5 и регистр множителя блока l5, на в:ход 23 подается код модуля Р и записывается в регистр 5 и в сумматор 7, в регистр множителя блока 15 с входа 19 поступает двоич ный код числа первообразного элемента 8;, в регистр множимого блока 15 эаписйвается единичный элемент. При подаче импульса на вход 21 устройство начинает выполнять операцию умно женил ° Блок 15 умножения умножает единицу на 6; и записывает в параллельном коде результат умножения я
I сумматор 14, который является вычитающим. В результате на выходе суммато» ра 14 образуется код числа А, = 9, 1 который поступает на входы элемента
ИЛИ 13, образуя íà его выходе единич» ный потенциал, который открывает элемент И 9 а также поступает на вход дифференциальной цепочки, на выходе которой образуется единичный импульс, поступающий на обнуляющий регистр множимого вход блока 15 умножения и через элемент ИЛИ 2 на обнуляющий вход счетчика 6, в результате чего счетчик 6 и регистр множимого, блока
l5 умножения обнуляются. Через откры тый элемент И 9 тактовые импульсы с входа 24 поступают на вход второго слагаемого сумматора 14 и на инфор мационный вход счетчика 6. Последний осуществляет суммирование поступив
mего на его вход количества тактовых импульсов. Суммирование осуществляет ся до тех пор, пока на выходах счет» чика 6 не образуется число в двоичном коде, численно равное модулю P и по-. ступающее на вторые входы группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-! - 4-К, на первые входы которых с выходов регис г ра 5 поступает двоичный код выбран
1236497 ного модуля P. В результате на выходе каждого элемента 4-1 - 4-К окажутся нулевые сигналы, которые поступают на входы элемента ИЛИ-НЕ 3, на выходе последнего образуется единичный сигнал, который через элемент ИЛИ 2 поступает на вход установки в О" счет» чика 6, и подсчет тактовых импульсов начнется заново.
Таким образом, на вторые входы 10 группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-1—
4-К поступают двоичные коды чисел от 1 до Р, В течение этого времени хотя бы на одном из выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-1 - 4-К будет 15 единичный сигнал, вследствие чего на выходе элемента ИЛИ-НЕ 3 будет нулевой сигнал . Как только счетчик 6 сосчитает количество тактовых импульсов, равныхныбранному модулюР, опять, 20 произойдет его обнуление. Данная операция будет происходить до тех лор, пока не обнулится сумматор 14, Обнуление последнего произойдет в том случае, когда количество поступивших 25 на его вход второго слагаемого тактовых импульсов будет численно равно числу А,, записанному на сумматоре
14. В результате этого с выхода элемента ИЛИ 13 поступает нулевой сиг- 30 нал, элемент И 9 закроется и тактовая последовательность перестанет посту пать на входы сумматора 14 счетчика
6. Поэтому на выходах счетчика 6 останется остаток а, числа А по вью» бранному модулю P. Под воздействием среза единичного импульса, поступивmего с выхода элемента ИЛИ 13, форми рователь 8 сформирует импульс, кото -рый откроет элементы И 10 1 - 10-К, 40 на первые входы которых поступает ос» таток а числа At с выхода счетчика
6. Тем самым обеспечивается считывание остатка а, от числа А< по модулю P на выходы устройства и его за- 4 лись на регистр множимого блока 15.
Импульс с выхода формирователя 8 импульсов поступит через элемент ИЛИ 17 на вычитающий вход второго слагаемо-. го сумматора 7 и через элемент 11 за- 0 держки на первый вход элемента ИСКЛЮ
ЧАЮЩЕЕ ИЛИ 16, Элемент 11 задержки рассчитан на задержку импульсов на один такт. За это время остаток а, от числа А< по модулю Р запишется в регистр множимого блока 15. Так как иа второй вход элемента ИСКЛЮЧАЮЩЕЕ
ИЛИ 16 поступает нулевой сигнал,,сслничс<ьсй с.лгвал, ttot я уллс<я;лй вл < < первый o õî.t,, с<кажет< .я g. записывается в сумь<лтор 1». <аI 1 тем повторяется цикл онер 1llt Процесс формирования данной последонательности кодов остатков продолжается до тех лор, пока сумматор 7 числа элементов, на вход второго слагаемого которого поступают сигналы с выхода формирователя 8, не обнулнтся и не выдаст сигнал обив ения, поступающий через элемент 12 задержки на второй вход элемента ИСКЛЮЧА10ЩЕЕ ИЛИ 16. Время задержки элемента 12 равно времени задержки элемента 11 ° В результате блок 15 умножения прекратит свою работу и устройство окажется готовым к новому циклу ны» числения остатков а;. Записывая в устройство коды пернообразных элементов 8;, можно сформировать любые последовательности элементов мчльтилликативной группы поля GF(P) а изменяя модуль Р, с целью формирования остатков по иному модулю Р; можно сформировать последовательности элементон мультилликативных групп и других полей Галуа GF(P ) . Формула изобретения Устройство для формирования элементов мультилликативных групп полей Галуа GF(P), содержащее первый э.яемент ИЛИ, блок умножения, группу из К эле» ментов И, где К - разрядность мультипликативных групп, первый и второй элементы задержки, первый сумматор, входы значения первообразного элемента устройства подключены к входам множителя блока умножения, первый ус» тановочный вход устройства подключен к входу установки в нулевое состояние 1236497 регистра множителя, второй установочный вход устройства подключен к входу установки в нулевое состояние регист ра множимого и к первому входу перво5 ro элемента ИЛИ, входы значения приводящего модуля устройства подключены к входам первого слагаемого первого сумматора, выходы элементов И группы подключены к входам множимого блока 1р умножения и к выходам результата уст» ройства, выход первого сумматора подключен к входу второго элемента задержки, о т л и ч а ю щ е е с я тем, что, с целью расширения функцио- 1 нальных воэможностей устройства за счет формирования элементов мультипликативных групп полей Галуа FG(P) при любом модуле P в него введены элементы ИЛИ с второго по четвертый, эле- 2р мент ИЛИ-НЕ, элемент И, второй сумматор, одновибратор, блок дифференцирования, счетчик, регистр, группа из К элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, входы значения приво- 2S дящего модуля устройства подключены к информационным входам регистра, вход установки в нулевое состояние которого подключен к первому установочному входу устройства,i (i 1, 2, ...,К) Зо выход регистра подключен к первому входу ъ-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. группы, к второму входу которого подключены д-й выход счетчика и второй вход i-го элемента И группы, выходы элементов ИСКЛЮЧА16ЦЕЕ ИЛИ группы подключены к входам элемента ИЛИ-НЕ, выход которого подключен к второму входу первого элемента ИЛИ, третий вход которого подключен к выходу блока дифференцирования, выходы блока умножения подключены к входам первого слагаемого второго сумматора, вход второго слагаемого второго сумматора подключен к выходу элемента И и к информационному входу счетчика, вход установки в нулевое состояние которого подключен к выходу первого элемента ИЛИ, выходы второго сумматора подключены к входам второго элемента ИЛИ, выход которого подключен к входам блока дифференцирования, одновибратора и к первому входу элемента И, второй вход которого подклю» чен к синхровходу устройства, выход одновибратора подключен к первым входам элементов И группы, первому входу третьего элемента ИЛИ и к входу первого элемента задержки, второй 1" вход третьего элемента ИЛИ подключен к входу запуска устройства и к первому входу четвертого элемента ИЛИ, второй вход которого подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы которого подключены соответственно к выходам перво» ro и второго элементов задержки, выход четвертого элемента ИЛИ подклю; чен к синхровходу блока умножения, выход третьего элемента ИЛИ подключен к входу втового слагаемого первого сумматора. 1236497 Составитель В. Смирнов Редактор Р. Цицика,Техред Г.Гербер Корректор М. Самборская Заказ 3093/53 Твфаж 671 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раувская наб., д. 4/5 Производствениополиграфическое предприятие, г. Ужгород, ул. Проектная, 4
