Устройство для формирования элементов расширенных полей Галуа GF ( @ ) и кодовых последовательностей на их основе Советский патент 1988 года по МПК G06F7/49 

Намер almaHOpqxaMa

л;.. )

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

(ntoftn сброс .

Изобретение относится к приклад- 21, ной вычислительной технике и может 22, быть использовано в специализиро- 23, ванных вычислительных устройствах и с микропроцессорах для формирования, исследования свойств элементов полей GF(p), в системах кодирования в качестве устройств формирования кодовых комбинаций, построение которых Q базируется на теории полей GFCp) также 3 системах связи с шумоподоб- ными широкополосными сигналами в качестве устройств формирования дискретных сигналов,15

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

Из теории полей GFCp) известно, что, если б - первообразный элемент поля GF(p), то все элементы поля 25 GF(p) являются степенями , т.е.

GF(p) 0°,е...,

f

(modd:a(x),p).30

При этом а(х) является первообразным неприводимым полиномом степени п и а(0) О,

Таким образом, любой А элемент

А

2х -ьх-И

хЧ1

2х+2

А

А

А-

поля GF(p) может быть найден путем Дя результат по модулю р

чаем А„ 1/А.а 1 (mod

возведения х

дения А х

0 в степень k и привепо modd а.(х),р, т.е. двойному модулю. Если известен А -и элемент поля, то для нахождения А АГ элемента достаточно -и элемент умножить на X и результат привести

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

а(х) , р 3; XX (modd а(х),р)

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

Рассмотрим некоторые п поле GF(3). Чтобы коэффициентов при степеня элемента А(т.е.А , А, А точно провести следующие коэффициентами А, А, А А и а,,, а,, а j -.первообр нома а(х): умножая А на

а I (той , и прибавляя получаем после привед

3 А 1/А|.а, + е

жая А;, на а А

А А

к-(

по modd а(х),р, т.е. (modd а(х),р).

Ниже приведены вычисленные элементы поля GF(3): GF(3,P 3; n 3; а(х) at 0.

45

дулю р J A l 1/,А.а,+ умножая A на a и прибав зультату Af после приведе

7

дулю р 3 получаем Аа. Таким образом, А Далее, например, коэфф

х -х-2;

2; а, I,линома А образом;

А

ВЫЧИСЛЯЮТСЯ сл

о г

я 7 «АЛ

.Э1

А , А

х +х+2

2

2

2х 2к 2х+1 х +2х+1 2х +2х+2

2х -ьх-И

хЧ1

2х+2

2х +2х

А

А

А-

21, 22, 23, с Q 5

0

5

0

Дя результат по модулю р

чаем А„ 1/А.а 1 (mod

Г

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

а(х) , р 3; () ; XX (modd а(х),р).

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

Рассмотрим некоторые примеры на поле GF(3). Чтобы пол -чить значение - коэффициентов при степенях х, х , х . элемента А(т.е.А , А, А ) , достаточно провести следующие операции с коэффициентами А, А, А элемента А и а,,, а,, а j -.первообразного полинома а(х): умножая А на a и приво 3, полуа I (той 3), wHo- , и прибавляя к результату получаем после приведения по мо 3 А 1/А|.а, +А е

жая А;, на а А

5

дулю р J A l 1/,А.а,+Лд J (mod умножая A на a и прибавляя к результату Af после приведения по мо7

дулю р 3 получаем Аа. 1 (mod р) . Таким образом, А . Далее, например, коэффициенты полинома А образом;

А

ВЫЧИСЛЯЮТСЯ следутощим

о г

я 7 «АЛ

.Э1Z

А , А.

,+

АГ

2;

.Af

0

AV АГ-а + А7 0; коэффициенты полинома i следующим образом:

вычисляются

.2S

АО

- Aj. ар

1 (mod 3);

А

19

+ А

2

5

. гй .1 . А г А. Ai-a, +А

- О (mod 3); 2-.

ч , Таким образом, данное рекуррентное правило сводится к следук1щег.;у: коэффициенты каждого последующе- м ги лино3)

элемента поля GF(p) вычисляются с использованием коэффициентов предыдущего полинома - эле- . мента А и первообразного полинома а(х) по правилу:

. а (mod р); А . А ;

X aj А (mod р).

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

|U,

fu |u , k О, 1,. ,, p -21 ,

fyCe - -), если б -t- 4) (mod p); 1 1 , если 9 + I 0 (mod p).

где

V(b)e Jдвузначный характер элемента b поля GF(p);

u - индекс, определяемый из условия

b 0 (modd а(х),р),

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

А А + 6 + (modd а(х),р),

после чего ш позиции кода присвоить значению характера (f (А + 1) у (А ), Если i О (mod 2), то /иц 1, если i I (mod 2), то |Ц, -1. Такая методика отражает процедуру построения характеристических кодов.

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

На фиг. I преде-давлена функциональная схема предлагаемого устройства} на фиг. 2 - функциональная схема . блока сложения.

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

0

134

возможности известного устройства по формированию элементов полей GFCp) для любых простых р и любых целых п. Из теории кодирования известно, . что на использовании свойств и характеров элементов поля Gl (p) базируются правила построения, например, характеристических кодов. Так, для характеристических кодов правило кодирования формулируется следующим образом:

, если u О (mod 2) -I, если u I (mod 2)

25 на их основе содержит первую группу I умножителей, группу 2 сумматоров, вторую группу 3 умножителей, сумматор 4, блок 5 сложения, блок 6 коммутации, блок 7 памяти, первьй

30 счетчик 8, первый элемент ИЛИ 9, первый триггер 10, генератор И тактовых импульсов, второй счетчик 12, второй триггер 13, третий счетчик 14, второй элемент ИЛИ 15,

2g Первая группа 1 умножителей предназначена для умножения по модулю р коэффициента А|, предьщущего элемента поля на соответствующие коэффициенты полинома а ; (j О,...,

40 n-l). Группа 2 сумматоров предназначена для сложения по модушо р произведения AJа;с коэффициентом.элемента поля GF(p) А-,. Вторая группа 3 умножителей предназначена для

45 умножения по модулю р коэффициентов элементов поля GF(p) на соответствующие им степени первообразного

элемента х

X,

, , . Сумматор 4 предназначен для сложения по модулю

0

h,г- .к 1

р у А-X , т.е. на выходе сумматоj e

pa 4 действует значение, соответствующее элементу поля Aj. Блок 5 сложения предназначен для прибавления 5 единицы к значению А-. Блок 5 коммутации предназначен для коммутации первых входов блока 7 памяти с выходами либо сумматора 4, либо блока 5 сложения в зависимости от управля51

ющего сигнала. Блок 7 памяти предназначен для записи индексов по модулю два элементов поля по адресу А| и считьшания их по адресу А , . Пер

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

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

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

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

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

414136

элемента поля Галуа GF(p), с которо- го начинается формирование этого поля, а на вторые входы первой 1 и втоg рой 3 групп умножителей подаются коды

коэффициентов первообразного полинома а(х) и коды первообразного элемента , степени х , х, ..., соответственно. При поступлении на счетный вход

10 первого счетчика 8 тактовых импульсов импульс переполнения появляется последовательно на одном из его выходов. При появлении его на первом выходе в первой группе 1 умножителей

15 происходит умножение по модулю р коэффициента А „ предьдутцего элемента поля GF(P) на соответствующие коэф- фициенты полинома а(х), aj.(j 0,п-1), т.е. группа 1 умножителей реализует

20 вычисление произведения А„.,-а: (mod р) (J О, п-).. При последовательном появлении импульса на 2 - п выходах первого счетчика 8 в группе 2 сумматоров последовательно произ25 водится суммирование по модулю р ре- зультата произведения А|, aj(modp) со значением коэффициента А , . Таким образом, на выходах группы 2 сумматоров действуют значения коэффици-

tf4-l

30 ентов очередного элемента поля А /I (j 0,п-1),. вычисленные по рекур- : рентному правилу. При появлении импульса на (п+1)-выходе первого счетчика 8 во второй -группе 3 умножите35 лей реализуется умножение коэффи- циентов AV на значение первообразного элемента степени x4j 1 ,п-1) . При появлении импульса на (п+-2)-м

выходе первого счетчика В в сумма

торе 4 производится сложение А,

4-А- х 4 ... А:;:;хК4.1

т.е. на выходах сумматора действует значение, соответствующее очередному элементу поля GFfp). Этот же им- пульс через элемент ИЛИ 9 сбрасывает в нулевое состояние первый счетчик 8 и переводит в противоположное состояние триггер 10.

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

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

I/

адресу А. Затем счетчик 8 опять генерирует импульсы управления и через

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

I/ J

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

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

10

15

20

ходе появляется импульс, под действием которого на втором выходе третьего счетчика 14 появляется импульс переполнения, который отключает генератор 11 тактовых импульсов, перев о- дит через второй элемент ИЛИ 15 второй триггер 13 в нулевое состояние и поступает на выход устройства как сигнал готовности его к формированию очередной кодовой последовательности. i

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

На входы сумматора. 16 в двоичном коде подается значение элемента поII

ля А . В сумматоре 16 производится сложение единицы. С вькодов сумU

матора 16 двоичный код А +1 поступает на первые входы блока 17 поразрядного сложения по модулю два и на вторые входы блока 20 ключей. Блок 17 реализует поразрядное сложение по модулю два кодов А +l и р. Если ре6 коммутации коммутирует свои выходы 25 зультат суммирования по модулю два равен нулю, т.е. р, то на всех входах элемента ИЛИ-НЕ 18 действуют нулевые значения, следовательно на его выходе действует единица, которая через элемент ИЛИ 21 считывается на выход блока 5 сложения. Одновременно элемент НЕ 19 инвертирует эту единицу и на первый вход блока 20 ключей поступает нулевое значение, т.е. блок 20 ключей не пропускает на вЬкод блока 5 сложения значение кода А « , поступающего на его вторые входы из сумматора 16.

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

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

l«v

1, если & + 1 О (mod 2), -1, если 0 + (mod 2),

k О,

,

где /K| - элемент кодовой последовательности;

в - первообразный элемент, поля GF().

Через очередные (п+2Хр -1) тактов работы на выход устройства считываются все элементы кодовой последовательности, после чего второй счетчик 12 переполняется, на его вы0

5

0

ходе появляется импульс, под действием которого на втором выходе третьего счетчика 14 появляется импульс переполнения, который отключает генератор 11 тактовых импульсов, перев о- дит через второй элемент ИЛИ 15 второй триггер 13 в нулевое состояние и поступает на выход устройства как сигнал готовности его к формированию очередной кодовой последовательности. i

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

На входы сумматора. 16 в двоичном коде подается значение элемента поII

ля А . В сумматоре 16 производится сложение единицы. С вькодов сумU

матора 16 двоичный код А +1 поступает на первые входы блока 17 поразрядного сложения по модулю два и на вторые входы блока 20 ключей. Блок 17 реализует поразрядное сложение по модулю два кодов А +l и р. Если результат суммирования по модулю два ра

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

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

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

55

1

А + 1, если А + I

Р,

если

А -н 1

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

I

Устройство для формирования элементов расширенных полей Галуа GF(p) и кодовых последовательностей на их основе, содержащее первую группу КЗ п-1 умножителей и группу из п-1 сумматоров, вход первого слагаемого k-ro сумматора группы (k ,...,n-), соединен с выходом k-r умножителя первой группы, стробирую- щие входы всех умножителей первой группы объединены, о. тличаю- щ а е с я тем, что, с целью расши- рения функциональных возможностей по обеспечению формирования элементов расширенных полей GF(p) и на их основе рекуррентных последовательностей за счет нахождения характера ра ширенного поля GF(p), в него введены вторая группа из п-1 умножителей, сумматор, блок коммутации, блок памяти, три счетчика, два элемента ИЛИ, два триггера, генератор тактовых импульсов, а в первую группу умножителей введен п-й умножитель причем входы первых сомножителей умножи1 елей первой группы являются входами коэффициентов полинома уст- ройства, вход первого сомножителя а-го умножителя второй группы (а ,..,,п-2) соединен с выходами а-го сумматора группы и входами второго сла гаемого ()-го сумматора группы, входы первого сомножителя ()-го умножителя второй группы соединен с выходом (п-1)-го сумматора группы, входом кода автоморфизма устройства и входами вторых сом- ножителей умножителей первой группы, выход.п-го умножителя которой соединен с входом второго слагаемого первого сумматора группы и первым входом сумматора, с второго по п-й входы которого соединены с выходами с первого по (п-).-й З множи- телей второй группы соответственно, входы вторых сомножителей которых

являются соответствующими входами задания первообразного элемента устройства, выход сумматора соединен с входом блока сложения и первым информационным входом блока коммутации, второй информационный вход которого соединен с выходом блока сложения, вькод коммутатора соединен с адресным входом блока памяти, информационный вход которого соединен с выходом первого триггера, вход управления записью-считыванием блока памяти соединен с управляющим входом блока коммутации и выходом второго триггера, информационный выход блока памяти является информационным выходом устройства, первый выход первого счетчика соединен со стробирующи- ми входами умножителей первой группы га-й выход счетчика (га 2,...,п) соединен со стробирующим входом k-ro (k n-1,...,)сумматора группы, (п+1)-й выход счетчика соединен со стробирующими входами умножителей второй группы, (п+2)-й выход счетчика соединен со стробирующими входом сумматора, счетными входами первого триггера и второго счетчика и первым входом первого элемента ИЛИ, второй вход которого соединен с входом обнуления второго счетчика и входом сброса устройства, выход первого элемента ИЛИ подключен к входу обнуления первого счетчика, счетный вход которого соединен с выходом генератора тактовых импульсов, вход запуска которого является входом импульса старта устройства, а вход останова соединен с выходом переполнения третьего счетчика, вьгxoдo f готовности устройства и первым входом второго элемента ИЛИ, второй вход которого подключен к выходу третьего счетчика, счетный вход которого подключен к входу сброса и выходу переполнения -зторого счетчика, выход второго элемента ИЛИ подключен к счетному входу второго триггера.

.2