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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Регістр зсуву з лінійним зворотним зв'язком містить L комірок (англ. stages, delay elements) пронумерованих 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.