Метод регістру зсуву із лінійним зворотнім звязком

Стандартний спосіб генерування потоку бітів оснований на використанні регістру зсуву зі зворотним зв’язком. Регістр може бути реалізований апаратно або програмно. В першому випадку це мікросхема з комірками пам’яті, в кожній з яких записаний один біт інформації. В другому – масив булевих елементів, які називають комірками або розрядами регістру.

Генерація потоку бітів відбувається наступним чином. На кожному кроці (такті) вміст декількох заздалегідь визначених комірок, які називаються відводами, подається на вхід функції зворотного зв’язку. Значення цієї функції заноситься у ліву комірку регістру після зсуву праворуч вмісту усіх комірок. Вміст крайньої правої комірки виштовхується з регістру і дорівнює значенню генерованого біту (рис. 3.2).

У якості функції зворотного зв’язку бажано брати нелінійну функцію. Але це складно здійснити, і тому використовуються регістри зсуву з лінійним зворотним зв’язком (РЗЛЗЗ). В таких регістрах функція зворотного зв’язку – XOR.

Роботу РЗЛЗЗ

Роботу РЗЛЗЗ можна описати наступним чином. Кожній комірці s_r-i поставимо у відповідність булеву змінну c_i, яка дорівнює 1, якщо комірка s_r-i є відводом, і - 0 у іншому разі. Припустимо, у початковому стані кожна комірка s_r-i містить значення a_r-i. В кожному такті значення комірок можуть змінюватися. Позначимо значення комірки s_r-i у t-у такті a_r-i^t. Будемо вважати a_r-i = a_r-i⁰. Тоді у перших r тактах на виході регістру отримуємо послідовність a₀⁰, a₁⁰, …, a_r-1⁰. У кожному наступному такті j ³ r значення на виході регістру дорівнює

c₁ a_r-1^j-r Å c₂ a_r-2^j-r Å … Å c_r a₀^j-r.

Зауважимо, що коли у початковому стані всі комірки мають нульове значення, то на виході утворюються тільки нулі. Якщо ж стартова послідовність нетривіальна (хоча б один елемент дорівнює одиниці), то на виході утворюється нетривіальна періодична послідовність.

Чому періодична? Дійсно, кількість можливих послідовностей довжини r скінчена, і змінюючи ці послідовності довільним чином, обов’язково отримаємо послідовність, що виникала раніше. Внаслідок детермінованості процесу отримаємо періодичну послідовність. Нагадаємо, що періодом послідовності називається найменше натуральне число N таке, що для будь-якого i більше деякого фіксованого числа виконується

a_N+i = a_i.

Існує 2^r – 1 різних ненульових початкових станів регістру. Тому значення періоду, що генерується регістром з лінійним зворотним зв’язком не більше 2^r – 1.

Властивості послідовності, що видається РЗЛЗЗ тісно пов’язані з властивостями двійкового характеристичного поліному

c(x) = 1 + c₁ x + c₂ x² + … + c_r x^r,

асоційованого з цим регістром. Його ненульові коефіцієнти називають відводами за аналогією з відповідними комірками регістру, що доставляють значення аргументів функції зворотного зв’язку. В полі GF(2^r) множення виконується за модулем c(x). На рис. 3.3 зображений РЗЛЗЗ, асоційований з поліномом x³ + x + 1.

Означення 3.1. Елемент a групи G називається утворюючим, якщо кожний елемент G дорівнює цілому степеню a.

Означення 3.2. Двійковий поліном c(x) степеню r називається примітивним, якщо він простий (ділиться тільки на 1 та на самого себе), і найменше значення числа n такого, що c(x) ділить xⁿ + 1, дорівнює 2^r – 1.

Означення 3.3. Елемент e мультиплікативної групи G називається примітивним (утворюючим), якщо кожний ненульовий елемент групи G дорівнює цілому степеню e..

Властивості послідовності бітів на виході РЗЛЗЗ залежать від характеристичного поліному наступним чином.

1. Якщо старший коефіцієнт характеристичного поліному c_r = 0, періодичність може виявитися не з першого такту.

2. Якщо c_r = 1, відповідна послідовність називається неособливою (несингулярною). Вона періодична з самого початку, тобто рівняння a_N+i = a_i виконується для усіх i, а не тільки для достатньо великих. Особливо цікаві неособливі послідовності, що відповідають поліномам з наступними додатковими властивостями.

А. Коли c(x) простий, при будь-якому ненульовому початковому стані регістру період послідовності дорівнює найменшому числу N, при якому поліном c(x) ділить 1 + x^N. Як наслідок, період послідовності ділить число 2^r -1.

B. Якщо c(x) примітивний, будь-який ненульовий початковий стан регістру дає послідовність з максимально можливим періодом 2^r -1.