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

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

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

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

Означення[ред.ред. код]

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

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

Посилання[ред.ред. код]