2. Лінійна рекурентна послідовність, що генерується рзлзз

Означення. Лінійною рекурентною послідовністю (ЛРП) порядку (або лінійною рекурентною (ЛР)) над полем називається числова послідовність, яка описується лінійним однорідним рекурентним рівнянням

. (1)

де – елементи поля.

Перші елементівне зв’язані ніякими обмеженнями, їх називаютьпочатковим відрізком послідовності. Позначимо початковий відрізок послідовності через. Члени початкового відрізку однозначно визначають всю послідовність.

Над полем лінійна рекурентна послідовність (ЛРП) порядку описується лінійним однорідним рекурентним рівнянням

(2)

де – елементи поля. Оскільки, то залишаючи лише ненульові коефіцієнти, будемо мати рівняння

, (2*)

Точка ,, – «точка прикладання» шаблонудля вибору бітів з послідовних станів для обчислення.

У результаті декількох тактів роботи двійкового РЗЛЗЗ довжини з точками зніманняі початковим заповненнямформуєтьсялінійна рекурентна послідовність над полем , яка описується лінійним однорідним рекурентним рівнянням (2*).

Кажуть, що РЗЛЗЗ реалізує лінійну рекурентну над полем .

Мал. 3. Загальний вид двійкового регістра зсуву з лінійним

зворотним зв’язком довжини , що виробляє гаму.

Комірки – точки знімання зворотного зв’язку.

Приклад. Приклад розгортки РЗЛЗЗ з рекурентним співвідношенням і з початковим станом 11000:

11000 11011 10101 00001 00101 10011 11000 11011 10101 00001 00101

Тут довжина регістра (кількість елементів в початковому заповненні), 0, 2 – параметри рекурентного закону (точки знімання зворотного зв'язку регістра). Подвійним підкресленням виділений біт, що генерується.

На кожному кроці на виході регістру генерується послідовність. Вектор– вектор-го сану регістру. При– вектор початкового стану.

Зміна початкового стану регістру зсуву з лінійним зворотним зв’язком за один крок:

.

Ми переконаємося далі, що задана лінійна рекурентна послідовність може бути згенерована регістрами різної довжини та з іншими точками зворотного зв’язку.

Звичайно вважається, що рекурентний закон відповідає мінімально можливому значенню .

Послідовність, що генерується РЗЛЗЗ, можна розглядати як послідовну зміну станів регістра:

,

,

…………………………..

При цьому ці стани перерізаються по елементах , що дозволяє записати їх компактно:, де.

Приклад. Послідовність початкових станів:

11000 10001 00011 00110 … 11100 11000

Суміщення початкових станів (запис станів у вигляді рекурентної послідовності)

11000

10001

00011

00110

01101

11010…

З іншого боку, можна вважати, що послідовність вже існує і розглядати стани як значення відрізку послідовності зелементів, який просувається вправо на один елемент за крок. В останньому випадку ми можемо розглядати відрізки довільної довжини.

Для відрізків довжини , наприклад,, виконуєтьсяперевірочне співвідношення

. (3)

Тому, просуваючи відрізок вправо і вибираючи з нього на кожному кроці біти з номерами , ми будемо отримувати 0.

Приклад. Перевірочне співвідношення для розгортки РЗЛЗЗ з рекурентним співвідношенням :

, .