- Регистр сдвига с обобщённой обратной связью
-
Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) - вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Льюисом и Пейном в 1973 году.
Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига
, основанная на примитивном трёхчлене
, где
и
- произвольные натуральные числа, причём
, выстроена в
столбцов,
, с правильно подобранной задержкой между столбцами.
Каждый столбец последовательности подчиняется рекурсии
,
где
- XOR, или аналог сложения по модулю 2, а
, каждое слово также должно подчиняться рекурсии
.
Содержание
Алгоритм GFSR
- Если
, переходите к пункту 2 (
изначально ноль).
- Изначально
используют задержанную базовую последовательность
, для получения каждого столбца
.
.
- Если
, установить
.
.
- Если
, установить
.
- EXCLUSIVE-OR,
,
- Запомнить,
.
Пример
Выберем примитивный трехчлен
. Базовая последовательность
. Для этого конкретного многочлена второй столбец формируется путем задержки первого столбца на 25 (
, в зависимости от ориентации "круга" бит) битовых позиций, третий столбец получается путем задержки второго столбца на другие - 6 битовых позиций, и так далее, пока все пять столбцов не будут заполнены.
Каждое
, появляется только один раз в течение всего периода из
числа.
Сопровождающая матрица для полинома
:
Составим матрицу, столбцами которой являются слова
, обозначим её
и перемножим на матрицу
:
Мы получили матрицу, столбцами которой являются слова
. В матричном виде
. После
применения этой матрицы
.
Среднее значение, дисперсия и корреляция
Теоретическое среднее значение и дисперсия алгоритма гарантируются его периодичностью.
В общем случае:
, где
Для L-битной машины:
.
На нормализованном (0, 1) интервале:
.
Дисперсия:
,
и на нормализованном интервале (0, 1):
.
Корреляция получается усреднением по всему периоду:
.
Плюсы и минусы
Так как многие программные среды содержат битовые операции, такие как XOR по умолчанию, то алгоритм РСсООС является достаточно быстрым. Также он прост в реализации, этот алгоритм можно реализовать при помощи только лишь стандартных функций Excel. Также по сравнению с линейным конгруэнтным методом, РСсООС генерирует последовательности псевдослучайных чисел с большим периодом.
Минусом алгоритма является то, что во многих областях требуется значительно больший период генерируемой последовательности, чем может дать алгоритм РСсООС.
См. также
Литература
- T. G. Lewis, W. H. Payne Journal of the ACM (JACM) Volume 20 Issue 3. — NY: ACM, July 1973.
- James E. Gentle Random number generation and Monte carlo methods. — 2nd edition. — NY: Springer, 2003. — XV + 381 с. — ISBN 0-387-00178-6
Ссылки
- Logical Intuitions (англ.)
Категории:- Генераторы псевдослучайных чисел
- Криптография
- Если
Wikimedia Foundation. 2010.