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

 

Изобретение относится к области прикладной вычислительной техники и может быть использовано в специализированных вычислительньтх устройствах и микропроцессорах для формирования , исследования свойств элементов полей CF(p), в системах связи с шумоподобными широкополосными сигналами в качестве устройств формирования дискретных сигналов. С целью расширения функциональных возможностей по обеспечению формирования элементов расширенных полей GF(p) и на их основе рекуррентных последовательностей, в устройство дополнительно введены группа 3 умножителей , сумматор 4, блок 5 сложения, блок 6 коммутации, блок 7 памяти, три счетчика 8, 12, 14, два элемента ИЛИ 9, 15, два триггера 10, 13, генератор 11 тактовых импульсов. Дополнительно введенные блоки обеспечивают формирование расширенных полей Галуа для любых простых р и целых п, а также позволяют генерировать кодовые последовательности на их основе. 2 ил. У9 сл

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

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

РЕСПУБЛИК (19) (11) (SI) 4 9 06 F 15/20

/Вмер айтюмор(щр у фив. l

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

ПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

H А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 4230384/24-?4 (; 2) 15.01.87 (46) 30.11.88. Бюл. И- 44 (72) И.Д. Горбенко, Д.Е. Глазин, A.A. Замула, И.A. Бычковский и А.Т. Захаров (53) 681.325(088 ° 8) (56) Авторское свидетельство СССР

9 995?92, кл. Н 03 К 3/84, )983.

Патент США 11 4037093, кл. С 06 Е 7/52,,977. (54) УСТ - ОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ЗЛ МЕНТОВ РАСШИРЕННЫХ ПОЛЕЙ ГАЛУА СР(Р )

И КОДОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА ИХ

ОСНОВЕ (57) Изобретение относится к области прикладной вычислительной техники и может быть использовано в специализированных вычислительных устройствах и микропроцессорах для формирования, исследования свойств элементов полей GF(p"), в системах связи с шумоподобными широкополосными сигналами в качестве устройств формирования дискретных сигналов. С целью расширения функциональных возможностей по обеспечению формирования элементов расширенных полей

GF(p ) и на их основе рекуррентньж последовательностей, в устройство дополнительно введены группа 3 умножителей, сумматор 4, блок 5 сложения, блок 6 коммутации, блок 7 памяти, три счетчика 8, 12, 14, два элемента ИЛИ 9, 15, два триггера 10, 13, генератор ll тактовых импульсов. Дополнительно введенные блоки обеспечивают формирование расширенных полей Галуа для любых простых р и целых и а также позволяют генерировать кодовые последовательности на их основе. 2 ил.

14414)3

Oд п01 Р -2 ь (modd:à (х), p) .

ЗО

При этом а(х) является первообразным неприводимым полиномом степени пи a(g) = О.

Ic

Таким образом, любой А элемент поля GF(p ) может быть найден путем возведения х = 0 в степень k и приведения А =- х по modd a.(õ),р, т.е к к

k-1 двойному модулю. Если известен А -й к элемент поля, то для нахождения А -го элемента достаточно А -й элемент умножить на х и результат принести по modd a.(õ),ð, т.е. А = A ° х (modd а(х),р) .

Ниже приведены вычисленные элементы поля GF(3 ):

GP(3 ),р = 3; n = 3; а(х) = х -х-2; а 2," а,= l; а2= О. х2+х х2+x+2 х + 2

2х

2х

2x+1

2х +х х +2х+1

2х +2х+2

)! Ач

)2. А

13. A

14. А

15. A

I6. A"

17 А"

)8. А"

)9. А

20. А

1. А

2. А1

3. А

4. А

5. А

6. А

7 А7

8. А

9. А

10. А

5Π— х

2 х х+2 х +2х

2х +х+2

2 х +х+) х1+2x+2

2х +2

= x+1

Изобретение относится к прикладной вычислительной технике и может быть использовано в специализированных вычислительных устройствах и микропроцессорах для формирования, исследования свойств элементов полей GF(р ),в системах кодирования в качестве устройств формирования кодовых комбинаций, построение которых базируется на теории полей GF(p")>а также з системах связи с шумоподобными широкополосными сигналами в качестве устройств формирования дискретных сигналов. 1I5

Целью изобретения является расширение функциональных возможностей по обеспечению формирования элементов расширенных полей GF (p") и на их основе рекуррентных последовательностей за счет нахождения характера расширенного поля СР(р"), Из теории полей GF(p ) известно, что, если й) — первообразный элемент поля GF(p ), то все элементы поля

GF(p ) являются степенями О, т.е. г 2х 2+x+

23. А = 2х+2

24, А 4 = 2х +2х

25. A = 2x +2ê+1

26. А = 2х +1

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

a(x) = х -х-2 р = 3; А -х = (х +2х)к

9 9 1

xx = 2х +х+2 (шо сЫ а(х),р) .

Таким образом, для отыскания всех элементов (полиномов) поля GF(p ) неи обходимо умножать ранее вычисленный предшествующий элемент А (полином) на х и результат приводить по modd а(х),р. Эта операция тождественна сдвигу влево полинома предыдущего элемента (т.е, увеличению на единцу степени х каждого члена полинома) и если наибольшая степень при х равна и из результата необходимо вычитать полином а(х) столько раз, чтобы результат вычитания не имел степени х, равной и, а затем результат привести ( по модулю

Рассмотрим некоторые примеры на поле СГ(3 ). Чтобы получить значение -

1 о < 2 коэффициентов при степенях х, х, х элемента А (т.е,А7, А7, А ), достаточно провести следующие операции с б б б коэффициентами А, А, А2 элемента б о

А и а, à,, à 1 —. первообразного полиб нома а(х): умножая А на а „ и приводя результат по модулю р = 3, получаем A = 1/А .а = 1 (гпо0 3), умнобО жая А, на а и прибавлял к результату

А, получаем после приведения по моо дулю р = 3 А7 = 1/А а, + А",=- (mod 3)

6 умножая А> на а и прибавляя к результату А после приведения по мо— б

7 дулю р = 3 получаем А2 = 1 (mod р) .

Таким образом, А = х +х+ .

Далее, например, коэффициенты по2 .линома А вычисляютсл следующим образом:

A = A а,= 2; А = А а,+ Л, = 2; г 2( коэффициенты полинома Л вычисляются следующим образом:

А = А .а, = ) (mod 3);

16

A, = А1.а, + Л = 0 (mod 3);

z6 25 а1 + А, Таким образом, данное рекуррентное правило сводится к следукппему: коэффициенты каждого последующе .". лино1413 возможности известного устройства по формированию элементов полей GF(p ) для любых простых р и любых целых и.

Из теории кодирования известно, что на использовании свойств и характеров элементов поля GF(р" ) базируются правила построения, например, характеристических кодов. Так, для

10 характеристических кодов правило кодирования формулируется следующим образом: и (в =(p„k = О, f, р -23 (! (6 +», если e" + I Ф 0 (mod p);

l, если 0 + 1 ф 0 (mod р), y(b)e "!, если u = 0 (mod 2)

-1, если u = 1 (mod 2) где

b = 9 (modd а(х),р), 30

Из данного правила видно, что для формирования характеристического кода достаточно найти все р -1 элементов поля GF(p ), а затем осуществить .х М операцию отыскания i u k элементов, отличающихся друг от друга на

1, так, что

А =Л +1=6 +1

1 К k (modd а(х),р), 40 после чего 1н позиции кода присвоить значению характера Р (А +1) = P (А ), Если i = 0 (mod 2), то р „= 1, если

i = (mod 2) то (u = -1. Такая ме "" к °

45 тодика отражает процедуру построения характеристических кодов.

Таким образом, появляется возможность формирования рекуррентных последовательностей, построение которых основывается на использовании свойств и характеров элемент тов полей GF(p ).

На фиг. предс;авлена функциональная схема предлагаемого устройства, на фиг. 2 — функциональная схема блока сложения. з 144 ма — элемента А поля СГ(р") вычисляются с использованием коэффициентов предыдущего полинома — элеk мента А и первообразного полинома а (х) по правилу: к х а + А., (mod р).

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

GF(р ), u — индекс, определяемый из условия

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

GF(p") и кодовых последовательностей на их основе содержит первую группу

I умножителей, группу 2 сумматоров, вторую группу 3 умножителей, сумматор 4, блок 5 сложения, блок 6 коммутации, блок 7 памяти, первый счетчик 8, первый элемент ИЛИ 9, первый триггер 10, генератор II тактовых импульсов, второй счетчик 12, второй триггер 13, третий счетчик

l4, второй элемент ИЛИ 15, Первая группа 1 умножителей предназначена для умножения по модулю р к коэффициента А„, предыдущего элемента поля на соответствующие коэффициенты полинома à (j = О,..., и — 1). Группа 2 сумматоров предназначена для сложения по модулю р прок изведения А а с коэффициентом,эле п к мента поля СР(р") A,. Вторая груп= па 3 умножителей предназначена для умножения по модулю р коэффициентов элементов поля СГ(р") на соответствующие им степени первообразного элемента х, х, ...,х " . Сумматор 4 предназначен для сложения по модулю к р А. х, т. е. на выходе сумматоi=е ра 4 действует значение, соответствующее элементу поля А . Блок 5 слоJ жения предназначен для прибавления единицы к значению А . Блок 6 комму3 тации предназначен для коммутации первых входов блока 7 памяти с выходами либо сумматора 4, либо блока

5 сложения в зависимости от управля14414

25 ющего сигнала. Блок 7 памяти предназначен для записи индексов по модулю два элементоч поля по адресу

A и считывания их по адресу А +< . Первйй счетчик 8 предназначен для управления работой устройства. Первый триггер 10 предназначен для формирования индексов элементов поля по модулю два. Второй 12 и третий 14 счет- 10 чики предназначены для управления записью — считыванием блока 7 памяти: третий счетчик 14 предназначен также для выдачи сигнала готовности устройства к формированию очередного 15 сигнала. Второй триггер 13 предназначен для выдачи сигналов записи— считывания на второй вход блока 7 памяти, "О" — запись, "1" — считывание. 20

Блок сложения 5 содержит сумматор 16, блок 17 поразрядного сложения по модулю 2, элемент ИЛИ-НЕ 18, элемент НЕ 19, блок 20 ключей, элемент ИЛИ 21.

Первые входы сумматора 16 являются входами блока 5 сложения, выходы сумматора 16 соединены с вторыми входами блока 20 ключей и перчыми входами блока 17 поразрядного сложе- ч0 ния по модулю два, выходы которого соединены с входами элемента ИЛИ-НЕ

18, выход которого соединен с входом элемента НЕ 19, выход которого еоединен с первым входом блока 20 ключей, первый выход которого соединен с первым входом элемента ИЛИ 21; выходы блока 20 ключей являются выходами блска 5 сложения, причем первый из них через элемент ИЛИ 21 соединен с выходом элемента ИЛИ-HE 18.

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

В начальный момент времени на ши- ну "C6poc поступает импульс сброса, 45 который устанавливает первый 8 и третий 14 счетчики в исходное состояние, на выходе первого триггера в исходном состоянии действует напряжение нуля. Одновременно с этим на 50 вход генератора 11 тактовых импульсов поступает сигнал "Старт", по которому с выхода генератора II начинают поступать тактовые импульсы1 на первые входы первой группы 1 умножителей подается двоичный код номера автоморфизма (циклической сдвижки) псевдослучайного сигнала, представк ляющий собой код коэффициентов А„,-ro

13 6 элемента поля Галуа GF(p"), с которого начинается формирование этого поля, а на вторые входы первой 1 и второй 3 групп умножителей подаются коды коэффициентов первообразного полинома а(х) и коды первообразного элемента степени х, х,...,x " соответственно. При поступлении на счетный вход первого счетчика 8 тактовых импульсов импульс переполнения появляется последовательно на одном из его выходов. При появлении его на первом выходе в первой группе 1 умножителей происходит умножение по модулю р коэфе фициента А „, предыдущего элемента поля СР1р") на соответствующие коэффициенты полинома а(х), а1.(1= О,п-l), т.е. группа I умножителей реализует к вычисление произведения А„, "а; (mod p) (j = О, п-1) ° . При последовательном появлении импульса на 2 — и выходах первого счетчика 8 в группе

2 сумматоров последовательно производится суммирование по модулю р результата произведения А„, а, (mod р) к со значением коэффициента А, ТаV ким образом, на выходах группы 2 сумматоров действуют значения коэффицика ентон очеренного элементе поля А

J ! (j =О,п-l), . вычисленные по рекур-: рентному правилу. При появлении импульса на (и+1)-выходе первого счетчика 8 во второй -группе 3 умножителей реализуется умножение коэффициентов А".+ на значение первообразного элемента степени xj(j = l,п-l).

При появлении импульса íà (n+2) -м выходе первого счетчика 8 в сумматоре 4 производится сложение А, +

x+t т.е. на выходах сумматора действует значение, соответствующее очередному элементу поля GF(p"). Этот же импульс через элемент ИЛИ 9 сбрасывает в нулевое состояние первый счетчик

8 и переводит в противоположное состояние триггер 10.

На выходе второго триггера 13 действует нулевое значение, в соответствии с которым к выходам блока 6 поцключены его первые входы, а блок

7 памяти находится в режиме записи.

Таким образом, в блок 7 памяти записывается значение по модулю два индекса k элемента А поля GF(p") по к адресу А. Затем счетчик 8 опять генерирует импульсы управления и через

14414!3

k = О, р -2, и

)+1= с очередные и+2 такта работы устройства в блок 7 памяти записывается

Кб! значение k+1 (mod 2) по адресу А

Вычисление индекса k no модулю два обеспечивает первый триггер счетный, который при поступлении на его вход очередного импульса с (и+2)-ro выхода первого счетчика 8 переключается в противоположное состояние. 10

Таким образом, через .(и+2) (р -)) тактов работы устройства в блок 7 памяти записываются значения по модулю два индексов k no адресам элементов поля А . В этот момент второй 15 счетчик 12, коэффициент переполнеи ния которого равен р -1, переполняется и на его выхода формируется импульс, под действием которого появляется импульс на первом выходе 20 третьего счетчика 14, который через второй элемент ИЛИ 15 переключает второй триггер 13 в единичное состояние, в соответствии с которым блок

6 коммутации коммутирует свои выходы 25 с вторыми входами, а блок 7 памяти переходит в режим считывания. Импульс с выхода счетчика 12 сбрасывает его в исходное состояние. Затем устройство работает по алгоритму, описан- 30 ному выше, за исключением того, что на адресные входы блока 7 поступают значения элементов поля А", увеличенные на единицу (эта операция реализуется в блоке 5 сложения), и на выход устройства из блока 7 памяти считываются значения индексов k no модулю два по адресу А +1. к

Таким образом, устройство реализует правило формированйя нелинейных 40 рекуррентных последовательностей, построенных на основе полей Галуа:

p„= 1, если Q + 1 ф 0 (шоц 2) к 45

-1, если 8 + 1 =- 0 (mod 2), где к — элемент кодовой последова- 50 тельности;

0 — первооб! азный элемент. поля

GF(pN) .

Через очередные (и+2)(р"-1) тактов работы на выход устройства счи55 тываются все р"-1 элементыкодовой последовательности, после чего второй счетчик 12 переполняется, на его вы ходе появляется импульс, под действием которого на втором выходе третьего счетчика 14 появляется импульс переполнения, который отключает гейератор 11 тактовых импульсов, переводит через второй элемент ИЛИ 15 второй триггер !3 в нулевое состояние и поступает на выход устройства как сигнал готовности его к формированию очередной кодовой последовательности. !

Блок 5 сложения работает следующим образом.

На входы сумматора 16 в двоичном коде подается значение элемента поля А . В сумматоре 16 производится к к сложение А и единицы. С выходов сумк матора 16 двоичный код А +I поступает на первые входы блока 17 поразрядного сложения по модулю два и на вторые входы блока 20 ключей. Блок 17 реализует поразрядное сложение по модулю два кодов А +1 и р . Если рек зультат суммирования по модулю два равен нулю, т.е. А +1 = р, то на всех и входах элемента ИЛИ-НЕ 18 действуют нулевые значения, следовательно на

его выходе действует единица, кото-. рая через элемент ИЛИ 21 считывается на выход блока 5 сложения. Одновременно элемент НЕ 19 инвертирует эту единицу и на первый вход блока 20 ключей поступает нулевое значение т.е. блок 20 ключей не пропускает на выход блока 5 сложения значение кода. к

А +I, поступающего на его вторые входы иэ сумматора 16.

Если же результат суммирования по модулю два в блоке 17 не равен нулю, т.е. А +1 Ф р ", то хотя бы на одном из входов элемента ИЛИ-НЕ 18 присутствует единица, следовательно на выходе элемента ИЛИ-НЕ 18 — нуль, который инвертируется элементом НЕ !9 в единицу и подается на первый вход блока 20 ключей, разрешая тем самым прохождение через него кода А +I,поМ ступающего с выходов сумматора 16, т.е. на выходе блока 5 сложения дей-, к ! ствует двоичный код А + 1.

Таким образом, блок 5 сложения реализует равенство: к к и

А +1, еслиА +1 f Ð

К и

1, если А + 1 р

1441413

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

Ф

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

СР(р") и кодовых последовательностей на их основе, содержащее первую группу нз и-1 умножителей и группу из и-1 сумматоров, вход первого слагаемого k-го сумматора группы (k 10

l,...,n-l), соединен с выходом k-го умножителя первой группы, стробирующие входы всех умножителей первой группы объединены, о т л и ч а ю— щ е е с я тем, что, с целью расши- 15 рения функциональных возможностей по обеспечению формирования элементов расширенных полей GF(p ) и на их ос-. нове рекуррентных последовательностей за счет нахождения характера рас-2п ширенного поля GF(p"), в него введены вторая группа из и-1 умножителей, сумматор, блок коммутации, блок памяти, три счетчика, два элемента ИЛИ, два триггера, генератор 25 тактовых импульсов, а в первую группу умножителей введен и-й умножитель причем входы первых сомножителей умножителей первой группы являются входами коэффициентов полинома устройства, вход первого сомножителя а-го умножителя второй группы (а — l,...,п-2) соединен с выходами а-го сумматора группы и входами второго слагаемого (а+1)-го сумматора группы, входы первого сомножителя (n-1)-го умножителя второй группы соединен с выходом (n-i)-ro сумматора группы, входом кода автоморфизма устройства и входами вторых сомножителей умножителей первой группы, выход.п-го умножителя которой соединен с входом второго слагаемого первого сумматора группы и первым входом сумматора, с второго по и-й входы которого соединены с выходами с первоrо пî (n-1).-й умножителей второй группы соответственно, входы вторых сомножителей которых являются соответствующими входами задания первообразного элемента уст. ройства, выход сумматора соединен с входом блока сложения и первым информационным входом блока коммутации, второй информационный вход которого соединен с выходом блока сложения, выход коммутатора соединен с адресным входом блока памяти, информационный вход которого соединен с выходом первого триггера, вход управления записью-считыванием блока памяти соединен с управляющим входом блока коммутации и выходом второго триггера, информационный выход блока памяти является информационным выходом устройства, первый выход первого счетчика соединен со стробирующими входами умножителей первой группы, m-й выход счетчика (m = 2,...,n) соединен со стробирующим входом k-го (k = п-1,...,1)сумматора группы, (и+1)-й выход счетчика соединен со стробирующими входами умножителей второй группы, (n+2)-й выход счетчика соедине co стробирующими входом сумматора, счетными входами первого триггера и второго счетчика и пер— вым входом первого элемента ИЛИ, второй вход которого соединен с входом обнуления второго счетчика и входом сброса устройства, выход первого элемента ИЛИ подключен к входу обнуления первого счетчика, счетный вход которого соединен с выходом генератора тактовых импульсов, вход saпуска которого является входом импульса старта устройства, а вход останова соединен с выходом переполнения третьего счетчика, выходом го— товности устройства и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего

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

144! 413

Составитель Ю. Тесленко

Техред М.Дидык

Корректор М ° Ac to<

Редактор И. Рыбченко

Заказ 6290/53

Тираж 704

В11ИИПИ Государственного комитета СССР по делам изобретений и открытий

1!3035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производст.,свпо-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4