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

 

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

, (1.6)

где значения как символов последовательности {а_i}, так и коэффициентов с и с_i принадлежат некоторому алфавиту (0,1,..., L –1), а операции сложения и умножения производятся по модулю L, причем L предполагается простым числом.

Соотношение (1.6) называется правилом кодирования, число п – памятью последовательности, а число L – ее основанием. В дальнейшем будем рассматривать только случай L=2.

Рис. 1.8. Схема сдвигающего регистра с обратной связью

Без потери общности в выражении (1.6) коэффициент с можно положить равным нулю. Тогда рекуррентное правило запишется в виде

. (1.7)

Из соотношения (1.7) следует, что для построения ЛРП необходимо в каждый тактовый момент запоминать п последних символов – п последовательности {а_i} и суммировать их по модулю два с весами с₁ с₂,..., с_п. Эти операции осуществляют сдвигающим регистром с обратной связью (рис. 1.8).

Любую ЛРП {а_i} можно задать производящей функцией G(х), под которой понимается формальный степенной ряд:

,

где а_i – i-й символ последовательности {а_i}, а суммирование производится по модулю два.

Пусть , тогда в окончательном виде можно записать:

, (1.8)

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

Из выражения (1.8) с учетом того, что для рассматриваемого случая все операции производятся по модулю два, можно получить:

,

где q(x) и f(х) – многочлены степени r < п и п соответственно. Многочлен f(х) полностью определяется рекуррентным правилом и называется характеристическим многочленом.

Выбирая многочлены q(x) и f(х) и производя их деление, можно получить различные рекуррентные последовательности.

Более детально с вопросом создания последовательностей сигналов с использованием определенных правил мы познакомимся позже.