Материал: Статистическая теория систем. практикум. Володько А.В., Останков А.В

Длина q-ичной М-последовательности

совпадает с длиной двоичной М-последовательности. Чтобы в этом убедиться,

подставим в (24) q 2m1 :

m

N (2m1 ) m1 1 2m 1.

Характеристический полином двоичной М-последовательности имеет степень m. Для q-ичной М-последовательности также можно найти характеристический полином, его степень равна m/m1. Элементы q-ичной М- последовательности и коэффициенты ее характеристического полинома степени m/m1 являются элементами конечного поля, которое обозначается GF(q). В этом случае говорят об М-последовательности и о полиноме над полем GF(q). При q 2m1 элементы поля GF(q) GF(2m1 ) могут быть представлены в виде полинома над полем GF(2)- коэффициенты в таком полиноме принимают только два значения 0 или 1. Степень полинома не превышает m1 -1. Полиномы над GF(2) могут быть представлены в двоичном виде: m1 -разрядными двоичными комбинациями, символами которых являются коэффициенты 0 или 1 при соответствующей степени переменной в полиноме.

В схеме генератора (рис. 3.1) генератор М- последовательности над полем GF(2m1 ) выдает элементы в двоичном виде. Элементы в q-ичной М- последовательности являются адресными сигналами для ПЗУ. В ПЗУ записана двоичная последовательность длины N1 , имеющая двухуровневую АКФ.

Основной задачей при синтезе генератора ГМВ последовательности является определение характеристического полинома над полем GF(2m1 ) степени k mm1 .

3.1.4. Определение характеристического полинома степени m/m1 над полем GF(2m1)

Элементы q-ичной М-последовательности и коэффициенты ее характеристического полинома являются элементами поля GF(q) (последовательность и полином над полем GF(q)). Элементы этого поля не являются корнями характеристического полинома. Его корнями будут элементы поля GF(qk ), для которого поле GF(q) является подполем. Если в поле GF(qk ), выбрать элемент , который является корнем характеристического полинома, то элементы q , q1 ,..., qk 1 также будут корнями

65

После перемножения получим коэффициенты в виде i и i1 ... ii0 . Эти коэффициенты надо выразить через элементы подполя GF(q). Для этого в поле GF(qk ) выбираем примитивный полином, одним из корней которого является

.

Поясним методику определения характеристического полинома на

следует выразить через элементы поля GF(42 ). Для этого среди элементов поля GF(42 ) следует найти такой элемент, который образует мультипликативную

5; 10; 15 1 (последнее равенство обусловлено тем, что элемент является примитивным, т.е. его период является максимальным и равным 15). Тогда элементы подполя GF(4) обозначаются следующим образом:

66

которого будет элемент . Для длины ПСП 15, т.е. поля GF(24 ), имеется два примитивных полинома:

Эти два полинома определяют две различные 4-ичные М- последовательности длины 15. В связи с тем, что других примитивных полиномов в поле GF(24 ) не существует, 4-ичных М-последовательностей длины 15 будет только две.

При построении генератора q ичной М-последовательности следует выбрать базис представления q ичных элементов. Базис должен содержать K элементов подполя GF(q). Для рассматриваемого примера выбираем степенной

должны умножаться на 5 . В результате умножения может получиться какая то степень элемента 5 которую надо опять представить с помощью степенного базиса 1, 5 . Для получения представления элементов подполя GF(4) через степенной базис можно использовать генератор двоичной М- последовательности со встроенными сумматорами по модулю два [22], построенный в соответствии с характеристическим полиномом степени m1 . Для длины N 15 генератор М-последовательности строится в соответствии с характеристическим полиномом x2 x 1.

Схема этого генератора представлена на рис. 3.2. Генератор формирует двоичную М-последовательность длины 3. При начальной установке 1 0 он формирует последовательные степени элемента , т.е. их двоичные представления. В соответствии с этой схемой 10 может быть представлено через степенной базис в 10 1 5 .

67

GF(23) (1, 9 , 18, 27 , 36 , 45 , 54 ) . В качестве степенного базиса выбираем элементы 1, 9 , 18 , т.е. 0,1 и 2-ю степени элемента 9 .

Для представления элементов поля GF(23 ) через степенной базис 1, , 2 надо задать примитивный полином поля GF(23) . Для этого поля существуют два

Следует выбрать тот полином, который является характеристическим полиномом короткой ПСП при матричном разложении двоичной М- последовательности длины 63. Номер М-последовательности определяется номером выбранного примитивного полинома в поле GF(26 ). Из этого следует, что для М- последовательности с номером N характеристический полином короткой ПСП будет x3 x2 1. (двоичное представление 1101). На рис. 3.3. представлена схема генератора, построенного в соответствии с этим полиномом, который дает представление в степенном базисе последовательных степеней элемента 9 : элемент 36 , например, можно выразить через базисные элементы

36 1 9 18 .

Рис. 3.3. Схема генератора со встроенными сумматорами по модулю два для характеристического полинома x3 x2 1, а также представление степеней элемента через степенной базис

Подобным образом вычисляются характеристические полиномы других q ичных М-последовательностей длины 63, а также для других длин. Укажем на особенности вычисления характеристического полинома для N 511. В этом случае 511 29 1 и m 9, m1 3 и K =3. Как и в случае длины 63, формируем М- последовательность над полем GF(23 ). Но характеристический полином этой последовательности будет иметь третью степень, так как K =3. Характеристический полином имеет три корня: , 8, 64.

69