Устройство для формирования элементов мультипликативных групп полей галуа

236497 2 Построение и функционирование устройства основано на алгоритме форми рования элементов мультипликативных групп полей Галуа СГ(Р), представлен ном в виде 1 1Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для вычисления элементов полей Галуа СГ(Р) и формирования кодовых рекуррентных последовательностей,построение которых оСновывается натеории полей Галуа СГ(Р) .Целью изобретения является расширение функциональных возможностейустройства за счет формирования элементов мультипликативных групп полейГалуа СГ(Р) для произвольного модуля Р.На чертеже показана функциональная схема устройства формированияэлементов мультипликативных групп полей Галуа СГ(Р) .Устройство содержит блок 1 дифференцирования, первый элемент ИЛИ 2,элемент ИЛИ-НЕ 3, группу элементовИСКЛОЧАЮЦЕЕ ИЛИ 4-1 - 4-К, регистр 5,счетчик 6, сумматор 7, формирова".тель 8 импульсов, элемент И 9, группу элементов И 10 1-10 К, первый элемент 11 задержки, второй элемент 12задержки, второй элемент ИЛИ 13, сумматор 14, блок 15 умножения, элементИСКЛЮЧАЮЩЕЕ ИЛИ 16, третий элементИЛИ 17, четвертый элемент ИЛИ 18вход 19 записи первообразного элемента, первый управляющий вход 20 записи единицы, вход 21 сигнала началаработы устройства, второй управляющийвход 22 обнуления множимого, вход 23записи значения приводящего модуля,тактовый вход 24,а 6 (йод Р) при0,1,Р Вычисление а; складывается из операций вычисления значения 6 и приведения 8 по модулю Р в полях СГ(Р) . Работа устройства для каждого значения Р описывается сле 1 цующей последовательностью: а д А,(шод Р) где А,иО; а в в А (вой Р), где А 2 а,9 щ 6 (вой Р); ;фа, - А, (щоа Р),где А а= д (тос 1 Р); и т.д.формирования остаточных классов па произвольному модулю Р, происходит путем вычитания из числа А Ч раз выбранный модуль Р; до тех пор, пока не будет выполняться условие А- -с 1 Р 1 = аР,Равенство остатка а модулю Р; означает тождественное равенство нулю числа А , т. е, А=(а- Р; ) ЕО(гпой Р).Устройство работает следующим образом.Перед началом работы на вход 22 поступает импульс, который обнуляет регистр множимого блока 15 и счетчик 6, на вход 20 поступает импульс, обнуляющий регистр 5 и регистр множителя блока5, на вход 23 подается код модуля Р и записывается в регистр 5 и в сумматор 7, в регистр множителяблока 5 с входа 19 поступает двоичный код числа первообразного элемента 8;, в регистр множимого блока 5эаписйвается единичный элемент. Приподаче импульса на вход 2 устройство начинает выполнять операцию умноженил. Блок 5 умножения умножаетединицу на 6; и записывает в параллельном коде результат умножения я сумматор 14, который является вычитающим. В результате на выходе сумматора 14 образуется код числа А, = 9, 1который поступает на входы элементаИЛИ 13, образуя на его выходе единичный потенциал, который открывает элемент И 9, а также поступает на входдифференциальной цепочки, на выходекоторой образуется единичный импульс,поступающий на обнуляющий регистрмножимого вход блока 15 умножения ичерез элемент ИЛИ 2 на обнуляющийвход счетчика 6, в результате чегосчетчик 6 и регистр множимого, блока1.5 умножения обнуляются. Через открытый элемент И 9 тактовые импульсы свхода 24 поступают на вход второгослагаемого сумматора 14 и на информационный вход счетчика 6. Последнийосуществляет суммирование поступив щего на его вход количества тактовыхимпульсов, Суммирование осуществляется до тех пор, пока на выходах счетчика б не образуется число в двоичном коде, численно равное модулю Р и по-.ступающее на вторые входы группы элементов ИСКЛЮЧАМЩЕЕ ИЛИ 4- - 4-К, на первые входы которых с выходов регисг ра 5 поступает двоичный код выбранного модуля Р. В результате на выходе каждого элемента 4-1 - 4-К окажутся нулевые сигналы, которые поступают на входы элемента ИЛИ-НЕ 3, на выходе последнего образуется единичный сиг нал, который через элемент ИЛИ 2 поступает на вход установки вО" счетчика 6, и подсчет тактовых импульсов начнется заново.Таким образом, на вторые входы 10группы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-в 4-К поступают двоичные коды чисел от 1 до Р, В течение этого времени хотя бы на одном из выходов элементов ИСКЛЮЧАЮЩЕЕ ИЛИ 4-1 - 4-К будет 15 единичный сигнал, вследствие чего на выходе элемента ИЛИ-НЕ 3 будет нулевой сигнал . Как только счетчик 6 сосчитает количество тактовых импульсов, равныхныбранному модулюР, опять, 20произойдет его обнуление. Данная операция будет происходить до тех пор,пока не обнулится сумматор 4, Обнуление последнего произойдет в томслучае, когда количество поступивших 25на его вход второго слагаемого тактовых импульсов будет численно равночислу А записанному на сумматоре14. В результате этого с выхода элемента ИЛИ 13 поступает нулевой сигнал, элемент И 9 закроется и тактоваяпоследовательность перестанет поступать на входы сумматора 14 счетчика6. Поэтому на выходах счетчика 6 останется остаток а, числа А 1 по вьюбранному модулю Р, Под воздействиемсреза единичного импульса, поступившего с выхода элемента ИЛИ 13, формирователь 8 сформирует импульс, кота" .рый откроет элементы И 10 1 - 10-К, 40на первые входы которых поступает остаток а числа А с выхода счетчика6. Тем самым обеспечивается считывание остатка а, от числа А, по модулю Р на выходы устройства и его запись на регистр множимого блока 15.Импульс с выхода формирователя 8 импульсов поступит через элемент ИЛИ 17на вычитающий вход второго слагаемого сумматора 7 и через элемент 11 за держки на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 16, Элемент 11 задержкирассчитан на задержку импульсов наодин такт. За это время остаток а,от числа А по модулю Р запишется в 15регистр множимого блока 15. Так какна второй вход элемента ИСКЛЮЧАЮЩЕЕИЛИ 16 поступает нулевой сигнал,ивичьЙ сигнал цо увв вапервый вход, окажется ва выхце в поступит на вход начала ьпслевя операции умножения бл,ка 15, 1 б - - чивая умножение множимого чпа, = А(гпо Р) на множитель , . 1 езультат умножения - числе А. = а,8;=- - 6. записывается в сумат 1 р 1. .1 а 1тем повторяется цикл операвй, ои- санных раньше для числа А, и ца вьгходных шинах устройства появляется код остатка а = А(пог 1 Р 1, который в блоке 15 умножается на д; и в сумматоре 14 записывается результат Аа Ц; и т.д. Таким образом на выходных шинах устройства появляется последовательность кодов остатков а, = О;. (той Р) а к В; (нос Р), а, = 8, (тпос Р) и т.д.Процесс формирования данной последонательности кодов остатков продолжается до тех пор, пока сумматор 7 числа элементов, на вход второго слагаемого которого поступают сигналы с выхода формирователя 8, не обнулится и не выдаст сигнал обив ения, поступающий через элемент 12 задержки на второй вход элемента ИСКЛЮЧА 10- ЩЕЕ ИЛИ 16, Время задержки элемента 12 равно времени задержки элемента 11В результате блок 15 умножения прекратит свою работу и устройство окажется готовым к новому циклу ньг числения остатков а;.Записывая в устройство коды пернообразных элементов 8; , можно сформировать любые последовательности элементов мчльтипликативной группы поля СР(Р), а изменяя модуль Р, с целью формирования остатков по иному модулю Р, можно сформировать последовательности элементон мультипликативных групп и других полей Галуа СР(Р ) .Формула изобретенияУстройство для формирования элементов мультипликативных групп полей Галуа СР(Р), содержащее первый э.аемент ИЛИ, блок умножения, группу из К эле ментов И, где К - разрядность мультипликативных групп, первый и второй элементы задержки, первый сумматор, входы значения первообразного элемента устройства подключены к входам множителя блока умножения, первый ус тановочный вход устройства подключен к входу установки в нулевое состояниерегистра множителя, второй установочный вход устройства подключен к входу установки в нулевое состояние регист ра множимого и к первому входу перво 5 го элемента ИЛИ, входы значения приводящего модуля устройства подключены к входам первого слагаемого первого сумматора, выходы элементов И группы подключены к входам множимого блока О умножения и к выходам результата уст ройства, выход первого сумматора подключен к входу второго элемента задержки, о т л и ч а ю щ е е с я тем, что, с целью расширения функцио нальных воэможностей устройства за счет формирования элементов мультипликативных групп полей Галуа РС(Р) при любом модуле Р, в него введены элементы ИЛИ с второго по четвертый, эле О мент ИЛИ-НЕ, элемент И, второй сумматор, одновибратор, блок дифференцирования, счетчик, регистр, группа из К элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ, входы значения приводящего модуля устройства подключены к информационным входам регистра, вход установки в нулевое состояние которого подключен к первому установочному входу устройства,-й (д 1, 2, ,К) Зо выход регистра подключен к первому входу -го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. группы, к второму входу которого подключены д-й выход счетчика и второй вход д-го элемента И группы, выходы элементов ИСКЛЮЧАКЮЕЕ ИЛИ группы подключены к входам элемента ИЛИ-НЕ,выход которого подключен к второмувходу первого элемента ИЛИ, третийвход которого подключен к выходублока дифференцирования, выходы блока умножения подключены к входам первого слагаемого второго сумматора,вход второго слагаемого второго сумматора подключен к выходу элементаИ и к информационному входу счетчика,вход установки в нулевое состояниекоторого подключен к выходу первогоэлемента ИЛИ, выходы второго сумматора подключены к входам второгоэлемента ИЛИ, выход которого подключен к входам блока дифференцирования,одновибратора и к первому входу элемента И, второй вход которого подключен к синхровходу устройства, выхододновибратора подключен к первым входам элементов И группы, первому входу третьего элемента ИЛИ и к входупервого элемента задержки, второй "вход третьего элемента ИЛИ подключенк входу запуска устройства и к первому входу четвертого элемента ИЛИ,второй вход которого подключен к выходу элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы которого подключены соответственно к выходам первого и второго элементов задержки,выход четвертого элемента ИЛИ подклю;чен к синхровходу блока умножения, выходтретьего элемента ИЛИ подключен к входувтооого слагаемого первого сумматора.,Техред Г.Гербер Корректор М. Самборская Редакто акаэ 3093/5 Ти 1 Подписноеенного комитета СССРтений и открытий5, Раувская н д. дарс иэоб ва,аб.,твенно полигра 4 аческое пр рои ВНИИПИ Го по делам 13035, Мос тие, г. Ужгород, ул. Проектная,