Регистр сдвига с обобщённой обратной связью

Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) - вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Льюисом и Пейном в 1973 году.

Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига , основанная на примитивном трёхчлене , где и - произвольные натуральные числа, причём , выстроена в столбцов, , с правильно подобранной задержкой между столбцами.

Каждый столбец последовательности подчиняется рекурсии

где - XOR, или аналог сложения по модулю 2, а , каждое слово также должно подчиняться рекурсии

Содержание

1 Алгоритм GFSR
2 Пример
3 Среднее значение, дисперсия и корреляция
4 См. также
5 Литература
6 Ссылки

Алгоритм GFSR

Если , переходите к пункту 2 ( изначально ноль).
Изначально используют задержанную базовую последовательность , для получения каждого столбца .
.
Если , установить .
.
Если , установить .
EXCLUSIVE-OR, ,
Запомнить, .

Пример

Выберем примитивный трехчлен . Базовая последовательность . Для этого конкретного многочлена второй столбец формируется путем задержки первого столбца на 25 (, в зависимости от ориентации "круга" бит) битовых позиций, третий столбец получается путем задержки второго столбца на другие - 6 битовых позиций, и так далее, пока все пять столбцов не будут заполнены.

Каждое , появляется только один раз в течение всего периода из числа.

Сопровождающая матрица для полинома :

$C=\begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix}$

Составим матрицу, столбцами которой являются слова , обозначим её и перемножим на матрицу :

$\begin{bmatrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 \end{bmatrix}$

Мы получили матрицу, столбцами которой являются слова . В матричном виде . После применения этой матрицы .

Среднее значение, дисперсия и корреляция

Теоретическое среднее значение и дисперсия алгоритма гарантируются его периодичностью.

В общем случае:

, где

Для L-битной машины:

На нормализованном (0, 1) интервале: .

Дисперсия:

и на нормализованном интервале (0, 1): .

Корреляция получается усреднением по всему периоду:

См. также

Литература

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 (англ.)

Random number generation and Monte carlo methods

Payne Generalized Feedback Shift Register Pseudorandom Number Algorithm in ACM digital library (англ.)

Регистр сдвига с обобщённой обратной связью.

Lt304888.ru

Туристические услуги

Рекомендуем