4.4. Генератор последовательностей GMW на основе сдвигов т-последовательностей.

Касаясь практической реализации генератора [46], надо отметить, что, несмотря на свою достаточно простую и компактную структуру, его разработчику предстоит решить целый ряд далеко не тривиальных задач, обусловленных особенностями данного метода.

Остановимся на этом вопросе более подробно.

возможна ситуация, когда в существующих таблицах полинома с такими параметрами может не оказаться. Заметим, что синтез примитивного полинома является достаточно непростой математической задачей, которая обычно выполняется на компьютере с помощью специально составленных алгоритмов.

Следующая задача связана с построением самого генератора q-ичной т-последовательности по имеющемуся примитивному полиному. Возникающие здесь трудности обусловлены необходимостью использования нетривиальных арифметических операций над GF(q). Очевидно, что и в этом случае также не обойтись без написания специальных компьютерных программ.

И, наконец, последняя по порядку, но не по сложности задача связана с разработкой ПЗУ генератора. Дело в том, что в силу метода построения структура ПЗУ полностью определяется элементами подполя GF(2m) поля GF(2N), представленного в базисе 1, р, р2,..., Р"1*1, где р - примитивный элемент подполя GF(2m). Трудности, возникающие в связи с решением перечисленных задач, в значительной мере ограничивают практическое использование последовательностей GMW в технике связи. Поэтому вполне своевременным представляется нахождение такого метода генерации, который бы способствовал более широкому их практическому применению. Предлагаемый новый, более простой метод генерации последовательностей GMW основан на формировании сдвинутых копий двоичной m-последовательности значности v. При рассмотрении этого метода будем опираться на известные свойства линейных функционалов над полями Галуа [45].

Пусть L-линейный функционал из GF(2N) в GF(2) такой, что Ц1)=1.

L0(L2(x)P)=L(xp) для VpeGF(2m). (4.2)

Обозначим через {CJ}, 0^j<2m-l, базисную последовательность длины 2т-1, образованную на основе некоторого разностного множества с параметрами (2.17). Тогда, используя результаты [14], можно показать, что любая последовательность GMW с точностью до сдвига может быть представлена в следующем виде:

b„=f(L2(an)) , (4.3)

где a - примитивный элемент GF(2N), 0f(PJ)=Cj для всех 0^<2т-1 и f(0)=0 . (4.4)

Заметим, что при f==Lo последовательность {Cj} уже сама определяется условиями (4.4), при этом последовательности {bn} и {Cj} являются ш-последовательностями со значностями соответственно V и w. Рассмотрим теперь последовательность {mn}, определяемую условием:

m„=L2(an), 0Согласно [4,13] последовательность {mn} является q-ичной т-последовательностью злачности 2N-1. Представим последовательность {т„} в виде двумерной таблицы размерности EXW, в которой каждый элемент т„ СТОИТ на пересечении і-ой строки и j-ro столбца, где. 0<і<є и 0{pSl+J} ,(4.5) где 0<і<є, 0?jНетрудно убедиться, что все такие ненулевые строки являются циклическими сдвигами друг друга и могут быть получены из первой строки с і=0 вида {р-1}, 0^=Ь0(Р3)для всех 0Согласно построению последовательность {d,} есть m-последовательность значности 2т-1. Введем теперь функционал L\: GF(2m) -> GF(2m), определяемый из следующих условий:

Li(W*dj + +...

Покажем, что Li есть взаимно однозначное отображение GF(2m)—>GF(2fn). Воспользуемся для этого известным свойством m-последовательности, иногда называемым свойством окна. Согласно этому свойству любой ненулевой набор из m последовательных символов т-последовательноста значности 2т-1, встречается на ее периоде ровно один раз, причем число различных таких наборов равно 2т-1. А поскольку коэффициенты при степенях р в правой части выражения (4.7) образуют именно такие наборы, то Li - взаимно однозначное отображение.

Обозначим через g: GF(2m)-> GF(2) функционал, определяемый следующими условиями:

gOLiWOHd и g(0)=0. Тогда в силу построения последовательность {bn } вида:

Ь„Ч(Ьі(Ь2(ап))) . (4.8) оказывается эквивалентной последовательности {b,,}, определяемой (4.3). Подставляям (4.7) в (4.8) с учетом (4.2), (4.5) и (4.6), в итоге получаем:

bo'=g(L(an)+ ЦОР+...+ ЦоҐ*"1'1^"1-1) . (4.9) Из анализа (4.9) видно, что коэффициенты L(an), L(an+t),... L(an+€(m",)) представляют собой сдвинутые на є чипов копии m-последовательности {Ца")}. С другой стороны эти коэффициенты могут быть интерпретированы как m-разрядные адреса, по которым в ПЗУ записаны символы последовательности {CJ}, причем по нулевому адресу в ПЗУ всегда должен находиться символ "О". В результате построенный в соответствии с (4.9) генератор

128

последовательностей GMW будет состоять из последовательно включенных генератора сдвинутых копий m-последовательности злачности v и ПЗУ базисной ПСП, состоящего из 2Ш однобитных слов. Функциональная схема этого генератора представлена на Рис.4.6.

Рис. 4.6.

Генератор ПСП GMW по схеме Кренгеля-Мешковского.

Сопоставление нового генератора с генератором [46] показывает, что, несмотря на почти одинаковую элементную сложность, новый генератор оказывается более предпочтительным в виду явно очевидной простоты его реализации. Главным неоспоримым преимуществом предлагаемого генератора является то, что все арифметические операции выполняются в нем исключительно по правилам двоичной логики над GF(2).

сверхдлинных последовательностей, применяемых для защиты передаваемых по каналам связи данных. Следует отметить, что область применения этого метода не ограничивается только последовательностями GMW. Данный метод может быть также использован для генерации и других двоичных последовательностей, ооразованных на основе 2 -ичнои т-последовательности и разностных множеств [18].

В заключении в качестве примера рассмотрим генерацию последовательности GMW

12 12

значности v=2 -1=4095,где N=12 и ш=3. Пусть примитивный элемент а поля GF(2 )

является корнем неприводимого примитивного полинома [68]:

X^+X'^X'+xVl. (4.10)

Тогда генератор сдвинутых копий m-последовательности должен формировать т=3 сдвинутых последовательностей bn, bn+585, bn+ii70 , где bn=L(an). Нетрудно убедиться, что

последовательности b„+ss5 и bn+ii70 являются задержанными соответственно на 3510 и 2925 чипов копиями m-последовательности bn. Формирование задержанных копий т-последовательносги наиболее просто осуществить суммированием по модулю два соответствующих разрядных выходов регистра сдвига генератора m-последовательности Ь„, выполненного по схеме с вынесенными сумматорами. Однако вид обратной связи при этом будет уже определяться полиномом:

X^+X^XVX+I , (4.11) двойственным к полиному (4.10). Пусть у корень примитивного полинома (4.11), а bn, b„-i, ...,bn^N.i) - последовательности, образующиеся на разрядных выходах регистра сдвига генератора m-последовательности. Тогда последовательность Ь„.і для всех 0^1bn-i=lobn+l і bn.