Регістр зсуву з лінійним зворотним зв'язком () — поширений спосіб отримання псевдовипадкових послідовностей, наприклад ключ-потоків. Це зумовлене такими причинами: LFSR добре втілюються на апаратному рівні; вони можуть утворювати послідовності із великими періодами; вони можуть утворювати послідовності з хорошими статистичними властивостями; і завдяки своїй будові, вони легко піддаються аналізу за допомогою алгебраїчних технік.
Означення Регістр зсуву з лінійним зворотним зв'язком містить комірок () пронумерованих кожна з яких може зберігати 1 біт інформації і має один вихід і один вхід, а також таймер, який керує рухом даних. Впродовж кожного такту виконуються такі операції: вміст комірки подається на вихід і стає частиною виходової послідовності; вміст комірки пересувається в комірку для і новим значенням комірки стає біт зворотного зв'язку який обчислюється додаванням за модулем попередніх значень певної підмножини з LFSR Фібоначчі Найправіший біт LFSR називається вихідним бітом, який завжди є також відгалуженням. Щоб отримати наступний стан, біти відгалуження послідовно об'єднуються за допомогою операції XOR; потім всі біти зсуваються на одне місце вправо, при цьому крайній правий біт відкидається, а результат об'єднання бітів відгалуження за допомогою операції XOR повертається в тепер порожній крайній лівий біт. Щоб отримати псевдовипадковий вихідний потік, використовують крайній правий біт після кожного переходу стану. LFSR має максимальну довжину тоді і тільки тоді, коли відповідний поліном зворотного зв'язку є примітивним над полем Галуа GF(2). Це означає, що необхідні (але не достатні) умови:
Кількість відгалужень є парною. Множина відгалужень є взаємно простими; тобто не повинно бути жодного спільного для всіх відгалужень дільника, крім 1.
Приклади многочленів для максимальних LFSR У наступній таблиці наведені приклади поліномів зворотного зв'язку максимальних довжин (примітивних поліномів) з регістром зсуву до 24. Кількість поліномів зростає експоненційно з довжиною зсувного регістру і може бути порахований за допомогою функції Ейлера Біти (n)Примітивний поліномПеріод () 2 3 3 7 4 15 5 31 6 63 7 127 8 255 9 511 10 1,023 11 2,047 12 4,095 13 8,191 14 16,383 15 32,767 16 65,535 17 131,071 18 262,143 19 524,287 20 1,048,575 21 2,097,151 22 4,194,303 23 8,388,607 24 16,777,215 LFSR Галуа Названий на честь французького математика Евариста Галуа, LFSR у конфігурації Галуа, яку також називають модульною, з внутрішніми XOR-ами або “one-to-many” LFSR, є альтернативною структурою, що може генерувати той самий вихідний потік, що й звичайний LFSR (але зі зсувом у часі). У конфігурації Галуа, коли система має тактування, біти, що не є відводами, зсуваються вправо на одну позицію без змін. Відгалуження, з іншого боку, піддаються операції XOR з вихідним бітом, перш ніж вони зберігаються в наступній позиції. Новий вихідний біт є наступним вхідним бітом. В результаті, коли вихідний біт дорівнює нулю, всі біти в регістрі зміщуються вправо без змін, а вхідний біт стає нульовим. Коли вихідний біт дорівнює одиниці, біти в позиціях відгалужень міняють своє значення на протилежне (якщо вони дорівнюють 0, то стають 1, а якщо вони дорівнюють 1, то стають 0), а потім весь регістр зміщується вправо і вхідний біт стає 1. LFSR Галуа не з’єднують відводи послідовно (XOR виконуються паралельно всередині регістру), тому затримка дорівнює часу одного XOR, а не ланцюжка. Це дозволяє обчислювати всі відводи одночасно й суттєво підвищує швидкість. Форма Галуа буде ефективнішою так як тільки вихідний біт обробляється окремо. Матриці Бінарні LFSR як конфігурації Фібоначчі, так і Галуа можуть бути виражені як лінійні функції за допомогою матриць. Використовуючи супутню матрицю характеристичного многочлена LFSR і позначаючи початкове значення як вектор стовпець , стан регістра в конфігурації Фібоначчі після крока дає:
Матриця для відповідної форми Галуа:
Для відповідної ініціалізації,
верхній коефіцієнт вектора стовпця:
дає термін вихідної послідовності. Ці форми узагальнюються на довільні поля.
Посилання Теорія і втілення, максимальна довжина послідовності і таблиці зворотнього зв'язку
Див. також Вихор Мерсенна