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

4-бітовий РЗЛЗЗ (Шаблон:Lang-en) з його діаграмою станів. XOR вентиль забезпечує для регістра зворотній зв'язок, який зсуває біти праворуч. Найдовша послідовність містить усі стани окрім стану «0000».

Регістр зсуву з лінійним зворотним зв'язком (Шаблон:Lang-en) — поширений спосіб отримання псевдовипадкових послідовностей, наприклад ключ-потоків. Це зумовлене такими причинами:

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

Означення

Регістр зсуву з лінійним зворотним зв'язком містить $L$ комірок (Шаблон:Lang-en) пронумерованих $0,1,\dots ,L-1,$ кожна з яких може зберігати 1 біт інформації і має один вихід і один вхід, а також таймер, який керує рухом даних. Впродовж кожного такту виконуються такі операції:

• вміст комірки $0$ подається на вихід і стає частиною виходової послідовності;
• вміст комірки $i$ пересувається в комірку $i-1$ для $1\le i\le L-1;$ і
• новим значенням комірки $L-1$ стає біт зворотного зв'язку $s_j,$ який обчислюється додаванням за модулем $2$ попередніх значень певної підмножини з $0,1,\dots ,L-1.$

Посилання

• Теорія і втілення, максимальна довжина послідовності і таблиці зворотнього зв'язку Шаблон:Ref-en

Див. також

• Вихор Мерсенна