• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

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

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

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

, .

Читайте також:

1. Багатомірна лінійна модель регресії.
2. Завдання, послідовність, джерела інформації для ревізії операцій з запасами
3. Завдання, послідовність, джерела інформації для ревізії операцій з необоротними активами
4. Завдання, послідовність, джерела інформації і методичні прийоми контролю доходів і фінансових результатів діяльності підприємницьких структур
5. Загальна лінійна оптимізаційна модель Канторовича
6. Засобами композиції є лінії, штриховка (штрих), тонові й кольорові плями, світлотінь, лінійна і повітряна перспективи [5].
7. Лінійна і квадратична локальні інтерполяції
8. Лінійна модель міжнародної торгівлі
9. Лінійна модель трансферу технологій
10. Лінійна регресія за допомогою функцій, лінійного тренду та пакета аналізу
11. Лінійна структура управління

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