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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК А 067 15 20 ЕТЕН истемах связ енко, Д ,А. Быч.Е. Гл ковски льств/84,3 СНОВЕ 57) И ретение отнй вычислител обласники итс риклад циали спольз может овсп ных ус для ф ойств ованных вычислит рмиро- леменвах и микр вания, исс оцессо ования снов е. мер аввю ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБР Н А ВТОРСМОМУ СВИДЕТЕПЬСТ(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ЗЛ- МЕНТОВ РАСШИРЕННЫХ ПОЛЕЙ ГАЛУА СГ(Р ") И КОДОВЬ 1 Х ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ИХ О тов полей СГ(р"), в си с шумоподобными широкополосными сигналами в качестве устройств формирования дискретных сигналов. С целью расширения функциональных возможностей по обеспечению формирования элементов расширенных полей СР(р ) и на их основе рекуррентньж последовательностей, в устройство до полнительно введены группа 3 умножителей, сумматор 4, блок 5 сложения, блок 6 коммутации, блок 7 памяти, три счетчика 8, 12, 14, два элемента ИЛИ 9, 15, два триггера 1 О, 13, генератор 11 тактовых импульсов. Дополнительно введенные блоки обеспечивают формирование расширенных полей Галуа для любых простых р и целых и, а также позволяют генерировать кодовые последовательности на(тпосЫ,а (х), р) . При этом а(х) является первообразным неприводимым полиномом степенипи а(О) = О.КТаким образом, любой А элементполя СР(р ) может быть найден путемвозведения х = 0 в степень с и приведения А : х по тпосЫ а(х),р, т.е,к,. к3 с-тдвойному модулю. Если известен А -йкэлемент поля, то для нахождения А -гоэлемента достаточно А -й элементумножить на х и результат привестипо шосЫ а(х),р, т.е. А = Ах(тпосЫ а(х),р),Ниже приведены вычисленные элементы поля СР(3 ):СР(3),р = 3; и = 3; а(х) = х -х,а 2," а,=1;аг=О,хг+ххг+х+2х + 222 х2 х2 х+12 х +хх +2 х+2 х +2 х+2 Л тс 13, Лц 14. А 15. А 1 6, АбАп 18. А 8 19. А 20. А 1. А 2. Л 3. А 4. А 5, А 6, А Ат 8. А 9. Л 10. А5 О- хгхх+2х +2 х2 х +х+2х +х+хг+2 х+22 х +2к+1 Изобретение относится к прикладной вычислительной технике и можетбыть использовано в специализированных вычислительных устройствах имикропроцессорах для формирования,исследования свойств элементов полей СР(рп),в системах кодирования вкачестве устройств формирования кодо.вых комбинаций, построение которых Обазируется на теории полей СР(р")атакже з системах связи с шумоподоб"ными широкополосными сигналами в качестве устройств формирования дискретных сигналов. 5Целью изобретения является расширение функциональных возможностейпо обеспечению формирования элементов расширенных полей СР(р") и на ихоснове рекуррентных последовательностей за счет нахождения характерарасширенного поля СР(р"),Из теории полей СР(р ) известно,что, если 8 - первообразный элементполя СГ(р ), то все элементы поляСР(р ) являются степенями О, т.е.21 А г = 2 х+х+123. А = 2 х+2 Л г 4 2 хг+2 х 25. А = 2 х+2 к+1 26, А = 2 х +1 Действительно, например 6-й элемент А вычисляется путем умноженияэлемента А на х и приведения резульХтата по двойному модулю:а(х) = х -х; р = 3; А -х = (х +2 х)к9 9 Яхх = 2 х+х+2 (шосЫ а(х),р)Таким образом, для отыскания всехэлементов (полиномов) поля СР(р ) неиобходимо умножать ранее вычисленныйпредшествующий элемент А (полином)на х и результат приводить по тпосса(х),р. Эта операция тождественнасдвигу влево полинома предыдущегоэлемента (т.е, увеличению на единцустепени х каждого члена полинома) иесли наибольшая степень при х равнаи, из результата необходимо вычитатьполином а(х) столько раз, чтобы результат вычитания не имел степени х,равной и, а затем результат привестипо модулюРассмотрим некоторые примеры наполе СГ(3 ). Чтобы получить значение"о 1 гкоэффициентов при степенях х , х , хэлемента А (т.е,А Л 7, Л), дсточно провести следующие операции сб б бкоэффициентами А , Л , Аг элементаб оА и ао, а а г в . первообразного полибнома а(х): умножая А на аи приводя результат по модулю р = 3, получаем А 7 = 1/А .а =(тпо 0 3), умнобОжая А, на а и прибавлял к результату6А , получаем после приведения по моодулю р = 3 А, = 1/А а, + Л",=-(тпос 3)бумножая Аг на а и прибавляя к результату А после приведения по моб7дулю р = 3 получаем А= 1 (тпос р),Таким образом, А = х +х+.гДалее, например, коэффициенты поги.линома Авычисляютсл следующимобразом:Л, = Л а,= 2; Л = А а,+ Л, = 2;г бкоэффициенты полинома А вычисляются следующим образом;А = А .а, = 1 (птос 3)и гА, =А а, +А .= О (тпос 3);гб г л,Л = А а + А , = 2.Таким образом, данное рекурревтноеправило сводится к следупппему: коэффиттиенты каждого ттоследующеги т.т ттттно1413 возможности известного устройствапо формированию элементов полей СР(р )для любых простых р и любых целых и.Из теории кодирования известно, .что на использовании свойств и характеров элементов поля С 1(р" ) базируются правила построения, например,характеристических кодов, Так, для 1 О характеристических кодов правило кодирования формулируется следующим образом: О =1 к з 1 с О, 3 р -2 (17(6 +1), если 6 + 1 Ф О (тпос 1 р); 1 , если О" + 1 Ф О (тпос 1 р),т 1(Ь)егде двузначный характер элемента Ь поля 25СГ(рп),тт - индекс, определяемый изусловия Ь = 3 (тпоЫ а(х),р),30Из данного правила видно, что для формирования характеристического кода достаточно найти все р -1 элементов поля СР(р ), а затем осуществить операцию отыскания т и 1 с элементов, отличающихся друг от друга на 1, так, чтоА = Л += 6 + 1к К(тпосЫ а(х),р),40 после чего р позиции кода присвоить значению характера(А +1) = тт (А), Если= О (тпос 1 2), то р= 1, если 1 = 1 (тпос 2) то а = -1. Такая меф" к45 тодика отражает процедуру построения характеристических кодов.Таким образом, появляется возможность формирования рекуррентных последовательностей, построение которых основывается на использовании свойств и характеров элемет тов полей СР(р )На фиг.предс;авлена функциональная схема предлагаемого устройства, на фиг. 2 - функциональная схема блока сложения. 55 з 144 ма - элемента А поля СР(р") вычисляются с использованием коэффициентов предыдущего полинома - элеКмента А и первообразного полинома а(х) по правилу:кх а + А, (тпой р). Из вышеприведенного следует, что могут быть расширены функциональные Устройство для формирования элементов расширенных полей Галуа СР(р") и кодовых последовательностей на их основе содержит первую группуумножителей, группу 2 сумматоров,вторую группу 3 умножителей, сумматор 4, блок 5 сложения, блок 6коммутации, блок 7 памяти, первыйсчетчик 8, первый элемент ИЛИ 9,первый триггер О, генератор 1 тактовых импульсов, второй счетчик 12,второй триггер 13, третий счетчик14, второй элемент ИЛИ 15,Первая группа 1 умножителей предназначена для умножения по модулю рккоэффициента А, предыдущего элемента поля на соответствующие коэффициенты полинома а(1 = Ои). Группа 2 сумматоров предназначена для сложения по модулю р прокизведения А а с коэффициентом,зле тт кмента поля СР(р") А ,. Вторая груп-.па 3 умножителей предназначена дляумножения по модулю р коэффициентовэлементов поля СР(р") на соответствующие им степени первообразногоэлемента х, хх " . Сумматор 4предназначен для сложения по модулюкрА х , т.е. на выходе суммато 1 =6ра 4 действует значение, соответствующее элементу поля А . Блок 5 сло 3жения предназначен для прибавленияединицы к значению А . Блок 5 комму,ттации предназначен для коммутациипервых входов блока 7 памяти с выходами либо сумматора 4, либо блока5 сложения в зависимости от управля14414 25 ющего сигнала. Блок 7 памяти предназначен для записи индексов по модулю два элементоч поля по адресуА и считывания их по адресу А. Первйй счетчик 8 предназначен для управления работой устройства, Первыйтриггер 1 О предназначен для формирования индексов элементов поля по модулю два. Второй 12 и третий 14 счетчики предназначены для управлениязаписью - считыванием блока 7 памяти: третий счетчик 14 предназначентакже для выдачи сигнала готовностиустройства к формированию очередного 15сигнала, Второй триггер 13 предназначен для выдачи сигналов записи -считывания на второй вход блока 7памяти, "0" - запись, "1" - считывание. 20Блок сложения 5 содержит сумматор 16, блок 17 поразрядного сложения по модулю 2, элемент ИЛИ-НЕ 18,элемент НЕ 19, блок 20 ключей, элемент ИЛИ 21,Первые входы сумматора 16 являются входами блока 5 сложения, выходы сумматора 16 соединены с вторымивходами блока 20 ключей и перчымивходами блока 17 поразрядного сложе- З 0ния по модулю два, выходы которогосоединены с входами элемента ИЛИ-НЕ18, выход которого соединен с входомэлемента НЕ 19, выход которого еоединен с первым входом блока 20 ключей, первый выход которого соединен с первым входом элемента ИЛИ 21;выходы блока 20 ключей являются выходами блска 5 сложения, причем первый из них через элемент ИЛИ 21 соединен с выходом элемента ИЛИ-НЕ 18.Устройство работает следующим образом.В начальный момент времени на ши-ну Сброс" поступает импульс сброса, 45который устанавливает первый 8 и третий 14 счетчики в исходное состояние, на выходе первого триггера висходном состоянии действует напряжение нуля. Одновременно с этим на 50вход генератора 1 тактовых импульсов поступает сигнал "Старт", по которому с выхода генератора 11 начинают поступать тактовые импульсы напервые входы первой группы 1 умножителей подается двоичный код номераавтоморфизма (циклической сдвижки)псевдослучайного сигнала, представкляющий собой код коэффициентов А,-го 13 6элемента поля Галуа СР(р"), с которого начинается формирование этого поля, а на вторые входы первой 1 и второй 3 групп умножителей подаются коды коэффициентов первообразного полинома а(х) и коды первообразного элемента степени х, хх " соответственно. При поступлении на счетный вход первого счетчика 8 тактовых импульсов импульс переполнения появляется последовательно на одном из его выходов. При появлении его на первом выходе в первой группе 1 умножителей происходит умножение по модулю р коэфефициента А , предыдущего элемента поля СРр") на соответствующие коэффициенты полинома а(х), а 1,(1 эе О,п), т.е. группа 1 умножителей реализуетк вычисление произведения А, "а; (вой р) ( = О, и), При последовательном появлении импульса на 2 - и выходах первого счетчика 8 в группе 2 сумматоров последовательно производится суммирование по модулю р результата произведения А, а;(пой р)ксо значением коэффициента А , . Так ким образом, на выходах группы 2 сумматоров действуют значения коэффицик. ентон очеренного элементе поля А ( Ц =О,п),. вычисленные по рекур-: рентному правилу. При появлении импульса на (и+1)-выходе первого счетчика 8 во второй группе 3 умножителей реализуется умножение коэффициентов А".+ на значение первообраз- ного элемента степени х Ц = 1,п), При появлении импульса на (и+2)-м выходе первого счетчика 8 в сумматоре 4 производится сложение А, +км т.е. на выходах сумматора действует значение, соответствующее очередному элементу поля СРр"). Этот же импульс через элемент ИЛИ 9 сбрасывает в нулевое состояние первый счетчик 8 и переводит в противоположное состояние триггер 10. На выходе второго триггера 13 действуетнулевое значение, в соответствии с которым к выходам блока 6 поцключены его первые входы, а блок 7 памяти находится в режиме записи. Таким образом, в блок 7 памяти записывается значение по модулю два индекса 1 элемента А поля СР(рп) покадресу А. Затем счетчик 8 опять генерирует импульсы управления и через144143 с =О, р,л к + 1= очередные и+2 такта работы устройства в блок 7 памяти записываетсякц значение к+ (той 2) по адресу А Вычисление индекса Е по модулю два обеспечивает первый триггер счетный, который при поступлении на его вход очередного импульса с (и+2)-го выхода первого счетчика 8 переключается в противоположное состояние, 1 ОТаким образом, через .(и+2) ф(р -1) тактов работы устройства в блок 7 памяти записываются значения по модулю два индексов 1 по адресам элементов поля А , В этот момент второй 5 счетчик 12, коэффициент переполненния которого равен р -1, переполняется и на его выхода формируется импульс, под действием которого появляется импульс на первом выходе 20 третьего счетчика 14, который через второй элемент ИЛИ 15 переключает второй триггер 3 в единичное состояние, в соответствии с которым блок 6 коммутации коммутирует свои выходы 25 с вторыми входами, а блок 7 памяти переходит в режим считывания. Импульс с выхода счетчика 12 сбрасывает его в исходное состояние. Затем устройство работает по алгоритму, описан ному выше, за исключением того, что на адресные входы блока 7 поступают значения элементов поля А", увеличенные на единицу (эта операция реализуется в блоке 5 сложения), и на выход устройства из блока 7 памяти считываются значения индексов Е по модулю два по адресу А +1.кТаким образом, устройство реализует правило формированйя нелинейных 40 рекуррентных последовательностей, построенных на основе полей Галуа: к р= 1, если 0 + 1 ф 0 (щой 2),к 45-1, если 0 + 1 =- 0 (шод 2), где рк - элемент кодовой последовательности,О - первооб.азный элемент. поляСЕ(р"). Через очередные (и+2)ф(р"-1) тактов работы на выход устройства счи 55 тываются все р"- элементыкодовой последовательности, после чего второй счетчик 12 переполняется, на его выходе появляется импульс, под действием которого на втором выходе третьего счетчика 14 появляется импульспереполнения, который отключает гейератор 11 тактовых импульсов, перево"дит через второй элемент ИЛИ 15 второй триггер 3 в нулевое состояние ипоступает на выход устройства как сигнал готовности его к формированию очередной кодовой последовательности,Блок 5 сложения работает следующимобразом.На входы сумматора 16 в двоичномкоде подается значение элемента поля А . В сумматоре 6 производитсякксложение А и единицы. С выходов сум"матора 16 двоичный код А +1 поступаетна первые входы блока 17 поразрядного сложения по модулю два и на вторые входы блока 20 ключей. Блок 17реализует поразрядное сложение помодулю два кодов А +1 и р . Если рекьзультат суммирования по модулю два равен нулю, т.е. А +1 = р , то на всехнвходах элемента ИЛИ-НЕ 18 действуютнулевые значения, следовательно наего выходе действует единица, которая через элемент ИЛИ 21 считываетсяна выход блока 5 сложения. Одновременно элемент НЕ 19 инвертирует этуединицу и на первый вход блока 20ключей поступает нулевое значение,т.е. блок 20 ключей не пропускает навыход блока 5 сложения значение кода.кА +1, поступающего на его вторые входы из сумматора 16.Если же результат суммирования помодулю два в блоке 17 не равен нулю,т,е. А +1 Ф р ", то хотя бы на одномиз входов элемента ИЛИ-НЕ 18 присутствует единица, следовательно на выходе элемента ИЛИ-НЕ 8 - нуль, который инвертируется элементом НЕ 9 вединицу и подается на первый входблока 20 ключей, разрешая тем самымпрохождение через него кода А +1,поМступающего с выходов сумматора 16,т.е. на выходе блока 5 сложения дей-,к1ствует двоичный код А + 1,Такимобразом, блок 5 сложенияреализует равенство: к к нА + 1, если А + 1 г рК и1 , если А + 1 " РФормула изобретения Устройство для формирования элементов расширенных полей Галуа СР(р") и кодовых последовательностей на их основе, содержащее первую группу нэ иумножителей и группу из исумматоров, вход первого слагаемого 1-го сумматора группы (11 О1п), соединен с выходом 1 с-го умножителя первой группы, стробирующие входы всех умножителей первой группы объединены, о т л и ч а ю - щ е е с я тем, что, с целью расши рения функциональных возможностей по обеспечению формирования элементов расширенных полей СГ(р ) и на их основе рекуррентных последовательностей за счет нахождения характера рас Л 1 ширенного поля СР(р"), в него введены вторая группа из иумножителей, сумматор, блок коммутации, блок памяти, три счетчика, два элемента ИЛИ, два триггера, генератор 25 тактовьи импульсов, а в первую группу умножителей введен и-й умножитель причем входы первых сомножителей умножителей первой группы являются входами коэффициентов полинома устройства, вход первого сомножителя а-го умножителя второй группы (а- 1п) соединен с вьиодами а-го сумматора группы и входами второго слагаемого (а+1)-го сумматора группы, входы первого сомножителя (и)-го умножителя второй группы соединен с выходом (и)-го сумматора группы, входом кода автоморфизма устройства и входами вторых сомножителей умножителей первой группы, выход.п-го умножителя которой соединен с входом второго слагаемого первого сумматора группы и первым входом сумматора, с второго по и-й входы которого соединены с выходами с первого по (и)-й умножителей второй группы соответственно, входы вторых сомножителей которых являются соответствующими входамизадания первообразного элемента устройства, вьиод сумматора соединенс входом блока сложения и первым информационным входом блока коммутации, второй информационный вход которого соединен с выходом блокасложения, выход коммутатора соединен с адресным входом блока памяти,информационный вход которого соединен с выходом первого триггера, входуправления записью-считыванием блокапамяти соединен с управляющим входомблока коммутации и выходом второготриггера, информационный выход блокапамяти является информационным выходом устройства, первый выход первого счетчика соединен со стробирующими входами умножителей первой группы,ш-й выход счетчика (ш = 2п) соединен со стробирующим входом Е-го(и+1)-й выход счетчика соединен состробирующими входами умножителейвторой группы, (п+2)-й выход счетчика соединесо стробирующими входомсумматора, счетными входами первоготриггера и второго счетчика и первым входом первого элемента ИЛИ,второй вход которого соединен с входом обнуления второго счетчика ивходом сброса устройства, выход первого элемента ИЛИ подключен к входуобнуления первого счетчика, счетныйвход которого соединен с выходом генератора тактовых импульсов, вход запуска которого является входом импульса старта устройства, а вход останова соединен с выходом переполнения третьего счетчика, выходом го -товности устройства и первым входомвторого элемента ИЛИ, второй входкоторого подключен к выходу третьегосчетчика, счетный вход которого подключен к входу сброса и выходу переполнения второго счетчика, выход второго элемента ИЛИ подключен к счетному входу второго триггера,1441413 Составитель Ю. Тесленко Техред М.Дидык Корректор М. Демчик Редактор И. Рыбченко Заказ 6290/53 Тираж 704 В 11 ИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5