М-последовательности. ГПСЧ типа ЛРС1

 

Опр ед ел ени е. Последовательностью над полем

 

GF ( p)

 

будем

 

называть любую функцию

U p : N ®F p , заданную на множестве N и

 

принимающую значения в поле

GF ( p) .

 

Рассмотрим класс последовательностей

U p , получаемых на основе

 

схемы линейного регистра сдвига с обратной связью (ЛРС), изображенной на

 

рис. 2.1. Схема содержит n-разрядный регистр сдвига (запоминающие ячейки

 

регистра обозначены символами

T1,

T2 , …,

Tn ), сумматоры, обозначенные

 

символом Å, по модулю два в цепи обратной связи и цепи (отводы) с

 

коэффициентами передачи

ai Î{0,1},

i = 1, n . Если

ai =0 , это эквивалентно

 

отсутствию (наличию при

ai =1) связи между выходом i-го разряда регистра

 

и входом i-го сумматора Å. Символ a0

принимает значения 0 или 1. Схему,

 

изображенную на рис. 2.1, обозначим символом ЛРС1.

x1 x2 xn

 

 

T1 T2

. . . Tn

 

 

a1 a2

. . . an

 

a0

 

Рис. 2.1. Схема ЛРС1

 

 

В очередном такте работы регистра двоичные символы

x1 ,

x2 , …,

xn ,

 

содержащиеся в его ячейках, умножаются на соответствующие

 

коэффициенты ai

и суммируются по модулю два, после чего происходит

 

сдвиг (вправо) информации в регистре, а в освободившуюся ячейку T1

 

записывается вычисленное значение суммы. Двоичные наборы

 

< x1, x2 , ..., xn > , снимаемые в каждый такт работы схемы с выходов ячеек регистра, можно рассматривать как двоичные n-разрядные целые числа.

Последовательность двоичных символов, снимаемых с выхода одного

 

(любого) разряда регистра является последовательностью U p

над полем

 

GF (2) . Такие последовательности называют линейными рекуррентными последовательностями (ЛРП).

Устройство, реализованное по рассмотренной схеме, принято называть

 

генератором псевдослучайных чисел или генератором псевдослучайных последовательностей.

Начальное заполнение ячеек регистра двоичными символами является

 

начальным состоянием регистра.

 

Введем следующие обозначения.

X (t0 )

– n-разрядный двоичный вектор,

 

начальное состояние регистра.

 

одних нулей (нулевой вектор).

X 0 – начальное состояние, состоящее из

 

Пусть

a0 =0 , тогда состояние схемы в момент времени

t + 1

 

описывается следующей системой уравнений

 

ìx1 (t +1) =a1x1 (t) +a2 x2 (t) +... +an-1xn-1 (t) +a n xn (t)

x

ï

ï (t + 1) =

x1 (t)

íx3 (t +1) =

ï...

ïîxn (t +1) =

x2 (t)

 

xn-1 (t ).

 

 

Полученную систему уравнений можно записать в матричном виде

 

 

X (t +1) =AT ×X (t) , (2.1)

 

 

æa a

... a a ö

ç

æx1 (t +1) ö

æx1 (t ) ö

ç1 2

n -1 n ÷

 

где

X (t +1) =çx2

(t +1) ÷

X (t ) =çx2

(t ) ÷

A = 0

0 ... 0 0

1 ... 0 0 .

ç

÷,

÷

ç ... ÷

ç ... ÷

T ç...

... ÷

ç

÷,

èxn (t + 1) ø

èxn (t ) ø

ç

è 0 0

÷

... 1 0 ø

 

Квадратную матрицу AT

размера n называют характеристической

 

матрицей ГПСЧ, изображенного на рис. 2.1. Элементы первой строки матрицы определяют структуру обратных связей схемы ГПСЧ.

Последовательности, порождаемые ГПСЧ, являются периодическими, то есть через определенное количество тактов (сдвигов) последовательность

повторится.

 

Опр ед ел ени е. Периодом последовательности U p

называют

 

наименьшее число

L ÎN , для которого существует натуральное число

K >0

 

такое, что для всех

 

i ³ 0

 

справедливо равенство

 

U p (K +i +L) =U p (K +i) .

Максимальный период последовательности U p

для схемы ГПСЧ равен

 

2n - 1. В самом деле, при

a0 =0

начальное состояние регистра

X (0)

 

порождает последовательность U p , состоящую из одних нулей (запрещенное

 

состояние), а число различных заполнений регистра длины n равно

2n .

 

Однако, в зависимости от структуры обратной связи и от начального состояния регистра, период последовательности может быть иным (в

частности, даже единичным (L=1)).

 

Опр ед ел ени е. Последовательность U p

над полем

GF (2) , получаемая

 

по соотношению (2.1) и имеющая максимальный период

2n -1, называется

 

максимальной линейной рекуррентной последовательностью - M -

 

последовательностью.

 

При

a0 =1

состояние регистра

X (0)

не является запрещенным. В этом

 

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

также из одних единиц. При других начальных состояниях

 

последовательность U над полем

GF (2)

также имеет максимальный период

 

2n - 1, но является инверсной по сравнению с M - последовательностью.

 

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

 

GF (2)

матрицы

AT :

 

 

f (x) =xn +a1

 

xn -1 +a

 

x n-2 + ... + a

 

 

n-1

 

 

x +an

 

 

, (2.2)

 

которым является определитель матрицы

(AT +XE) , где Е – единичная

 

матрица размера n. Коэффициенты ai

многочлена

f ( x)

определяют первую

 

строку матрицы AT

 

полинома (2.2)).

(матрицу AT

называют сопровождающей матрицей

 

Если характеристический многочлен

f ( x)

над полем

GF (2)

является

 

неприводимым и примитивным, то период ЛРП равен

2n -1.

 

Замечание . Таблица примитивных многочленов для степени

 

приведена в Приложении 1, в соответствии с [9].

n = 1, 127

 

О п р е д е л е н и е . Наименьший из всех возможных периодов ЛРП

 

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

 

Если характеристический многочлен

f ( x)

является только

 

неприводимым, то максимальный период ЛРП, в этом случае,

 

L =ord

f <2n -1.

 

Начальной информацией для построения ГПСЧ, порождающего ЛПР с

 

заданным периодом L, является характеристический многочлен (2.2) с

 

ord

f = L .

 

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

 

P1 (x) =x4

 

+ x 3

 

+ 1.

 

Соответствующая схема ГПСЧ изображена на рис. 2.2 а.

 

x1 x2 x3 x4

 

 

T1 T2 T3

 

 

Рис. 2.2 а. Схема ГПСЧ, соответствующая

P1 ( x) = x 4

+ x 3 + 1

 

Пусть для этой схемы

X (t0 ) =<1001 >. В табл. 2.1 представлена

 

периодическая последовательность векторов

X (ti ),

i = 0, 14 , снимаемых с

 

выходов

 

x1 ,

 

x2 ,

 

x3 ,

 

x4 (диаграммы работы ГПСЧ), с

 

L = 15 .

 

Таблица 2.1 (начало)

 

	X (t0 )	X (t1)	X (t2 )	X (t3 )	X (t4 )	X (t5 )	X (t6 )
x1
x2
x3
x4

 

При других начальных состояниях

X (t0 ) ¹X 0

получим 15

 

последовательностей векторов

X (ti )

с периодом L = 15, различающихся

 

некоторым сдвигом относительно друг друга.

 

Таблица 2.1 (окончание)

 

	X (t7 )	X (t8 )	X (t9 )	X (t10 )	X (t11)	X (t12 )	X (t13 )	X (t14 )
x1
x2
x3
x4

 

 

Двоичная последовательность, снимаемая с одного выхода

 

является последовательностью U над полем GF (2) .

xi ,

i = 1, 4 ,

 

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

P2 (x) =x4

+ x + 1 .

 

Соответствующая схема ГПСЧ изображена на рис. 2.2 б и диаграмма - в табл.

 

2.2.

 

x1 x2 x3 x4

 

 

T1 T2 T3

 

 

Рис. 2.2 б. Схема ГПСЧ, соответствующая

P2 ( x) = x 4

+ x + 1

 

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

 

g(x) =x4 +x3 +x2 +x +1. Порядок этого многочлена

ord g =5 , так как

g ( x)

 

является делителем многочлена

x5 +1, т.е.

 

x5 + 1 = ( x 4 + x3 + x 2 + x + 1)( x + 1) .

 

Таблица 2.2 (начало)

 

	X (t0 )	X (t1)	X (t2 )	X (t3 )	X (t4 )	X (t5 )	X (t6 )	X (t7 )
x1
x2
x3
x4

 

 

Таблица 2.2 (окончание)

 

	X (t8 )	X (t9 )	X (t10 )	X (t11 )	X (t12 )	X (t13 )	X (t14 )
x1
x2
x3
x4

 

Схема ГПСЧ, соответствующая

g ( x) , представлена на рис. 2.3.

x1 x2

x3 x4

 

 

T1 T2 T3

 

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

g(x) =x4 +x3 +x2 +x +1

 

 

Данная схема в зависимости от

X (t0 ),

X (t0 ) ¹X 0 , порождает три

 

диаграммы состояний, представленных в табл. 2.3, с одним и тем же

 

периодом

 

L =5 .

 

Замечание 2.2. М-последовательности имеют статистическую

 

равномерность на периоде

L = 2n - 1, то есть число единиц

N1 и нулей N2

 

определяется величинами

N1 = 2

n -1 и

N 2 = 2

n -1

- 1.

 

 

x1x2 x3 x 4

 

x1x2 x3 x 4

Таблица 2.3

 

x1x2 x3 x 4

1 11 0 0 11 0 0 01 0 1 1 1 1 0 0 1 1 1 0 0 1

1 1 1 1

0 0 1 1

1 0 0 1