Линейный рекуррентный регистр, статистические свойства линейной рекуррентной последовательности.

ЛРР - это схема (или алгоритм) формирования двоичных ПСП, котораязадается следующим рекуррентным уравнением:

где aj - двоичное начальное заполнение ЛРР; bj – бесконечнаядвоичная выходная последовательность ЛРР; hiдвоичные коэффициенты,определяющие структуру ЛРР; n - длина ЛРР.

В ячейкипамяти вводится двоичное начальное заполнение, затем подвоздействием каждого из тактовых импульсов содержимое этих ячеек памятисдвигается на одну ячейку вправо; одновременно с выходов ячеек их содержимое(0 или 1) поступает на входы сумматоров по mod 2 через «коммутаторобратных связей», который пропускает к сумматорам содержимое ячеек, еслисоответствующий им коэффициент hi, = 1, и не пропускает, если hi,- = 0; содержимоекрайней правой ячейки при этом всегда поступает на выход схемыи на вход первого сумматора, а выход последнего сумматора соединен совходом первой ячейки памяти.

Определение 3.2.1. Полиномом обратных связей h(x) двоичного ЛРРназывается полином следующего вида:

2) Свойство «окна» для выходной последовательности ЛРР

Пусть b - выходная послед. и пусть b’ подпоследовательность b длины 2ⁿ + k - 2, k < п Тогда каждая ненулевая подпоследовательность b’’ длины k будет присутствоватьв точности 2^п-к раз в подпоследовательности b’.

Это свойство называется свойством «окна», поскольку подпоследовательности b’’ получаются как бы при перемещении «окна» шириной k вдольпоследовательности b’. Если k = п, то все ненулевые подпоследовательности b’’ будут появляться в «окне» точно по одному разу.

3) Свойство баланса для выходной последовательности ЛРР

Число нулей на периоде выходной послед. равно вточности 2^п-1 -1, а число единиц 2^n-1. Если состоянияячеек памяти ЛРР представить десятичными числами, то легко заметить,что нечетным числам будет соответствовать появление единиц в выходнойпоследовательности, а четным - появление нулей, но, поскольку, числонечетных чисел на множестве 1, 2,..., 2^n-1-1 равно в точности 2^n-1, ачисло четных чисел 2^n-1-1, то отсюда и следует доказательство данногоутверждения.

Это свойство называется свойством баланса, поскольку при больших nоно означает, что число нулей на периоде выходной последовательности ЛРРбудет практически равно числу единиц на этом периоде.

 

4) Свойство серий для выходной последовательности ЛРР

Различают серии блоков длиной k и серии пробелов длиной k.

Свойство серий состоит в том, что половина всех серий на периодевыходной последовательности имеет длину 1, одна четверть серий - длину 2,1/8 серий - длину 3, и т. д., причем половина серий любой длины - это блоки, а половина - это пробелы.