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

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

. (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

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

10001

00011

00110

01101

11010…

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

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

. (3)

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

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

, .

Читайте також:
Багатомірна лінійна модель регресії.
Завдання, послідовність, джерела інформації для ревізії операцій з запасами
Завдання, послідовність, джерела інформації для ревізії операцій з необоротними активами
Завдання, послідовність, джерела інформації і методичні прийоми контролю доходів і фінансових результатів діяльності підприємницьких структур
Загальна лінійна оптимізаційна модель Канторовича
Засобами композиції є лінії, штриховка (штрих), тонові й кольорові плями, світлотінь, лінійна і повітряна перспективи [5].
Лінійна і квадратична локальні інтерполяції
Лінійна модель міжнародної торгівлі
Лінійна модель трансферу технологій
Лінійна регресія за допомогою функцій, лінійного тренду та пакета аналізу
Лінійна структура управління

Переглядів: 1192

<== попередня сторінка | наступна сторінка ==>

Теорема про лінійну складність комбінуючого генератора. | Вираз елементів рекуренти через початковий стан

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.006 сек.