M - последовательности на основе произведения многочленов

Рассмотрим способ построения схемы линейного регистра сдвига на основе характеристического многочлена, задаваемого как произведение

 

многочленов, при

 

a0 =0 .

 

Опр ед ел ени е 2 . 5 . Многочлены

f ( x) и

g ( x)

называются взаимно

 

простыми, если их наибольший общий делитель - многочлен

 

константа.

h( x)

есть

 

·Пусть

f ( x)

и g ( x)

– взаимно простые многочлены над полем

GF (2) ,

 

тогда

 

[9].

ord

f * g = [ord f ,

ord g ]

– наименьшему общему кратному порядков

 

Из этого утверждения следует, что если выбраны неприводимые

 

полиномы

f ( x) и

g ( x) , которым соответствуют ЛРП с взаимно простыми

 

периодами

L1 и

L2 , определяемыми порядками этих многочленов, тогда

 

характеристическому полиному

f (x) * g ( x)

 

L =L1 * L2 .

соответствует ЛРП с периодом

 

Пример 2.4. Пусть заданы неприводимые примитивные полиномы

 

f ( x) = x 2 + x + 1 и

 

вида

g ( x) = x3 + x + 1, а также характеристический полином

 

f ( x) * g ( x) = ( x 2 + x + 1)( x3 + x + 1) = x5 + x 4 + 1.

 

Соответствующая схема ГПСП представлена на рис. 2.6, она порождает

 

ЛРП с периодом L = 3*7 = 21 при

X (t0 ) =<00001 >.

 

 

T1 T2

T3 T4

 

 

Рис. 2.6. Схема ГПСП для

f (x) =x5

+x4 +1

 

 

Например, ЛРП, снимаемая с 5-того разряда регистра имеет вид

 

100001111101010011000, если

X (t0 ) =<00001 >. При

X (t0 ) =<10011 > и

 

X (t0 ) =<01101 >

ЛПР имеют периоды соответственно

L = 7

и L = 3 .

 

Замечание 2.3. Максимальный период, равный произведению взаимно простых периодов можно получить и другим способом – почленным сложением по модулю два двоичных ЛРП, определяемых неприводимыми многочленами.

Пример 2.5. Пусть заданы примитивные многочлены из предыдущего

 

примера:

f (x) =x2 +x +1 и

g(x) =x3 +x +1.

 

Схемы, соответствующие этим многочленам представлены на рис. 2.7.

 

Сложим по модулю два двоичные последовательности, снимаемые с

 

первых разрядов схем. Элементы последовательностей разделены запятой.

 

101,101,1 01,101,10 1,101,101

 

100 101 1,10 010 11,1 001 011

– ЛРП для многочлена

 

– ЛРП для многочлена

f ( x) = x 2 + x + 1;

 

g(x) =x3 +x +1;

 

001 000 0 11 111 01 0 100 110

– результирующая последовательность с

 

периодом L = 21

 

 

T1 T2

T1 T2

 

 

Схема ГПСП для

f ( x) = x 2 + x + 1

g ( x) = x3 + x + 1

Рис. 2.7

Схема ГПСП для