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

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

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

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

Означення

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

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

Посилання

• Теорія і втілення, максимальна довжина послідовності і таблиці зворотнього зв'язку (англ.)

Див. також

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