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

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

Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига $\mathcal {f}a_i \mathcal {g}$, основанная на примитивном трёхчлене $x^p+x^q+1$, где $p$ и $q$ - произвольные натуральные числа, причём $q\leqslant(p-1)/2$, выстроена в $j$ столбцов, $j\leqslant p$, с правильно подобранной задержкой между столбцами.

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

$a_k=a_{k-p+q}\oplus a_{k-p}$,

где $\oplus$ - XOR, или аналог сложения по модулю 2, а $k=p,\;p+1,\;...$, каждое слово также должно подчиняться рекурсии

$W_k=W_{k-p+q}\oplus W_{k-p}$.

Алгоритм GFSR

1. Если $k \ne 0$, переходите к пункту 2 ($k$ изначально ноль).
2. Изначально $W_1,\;...,\; W_{p-1}$ используют задержанную базовую последовательность $\mathcal {f} a_1 \mathcal {g}$, для получения каждого столбца $W_1,\;...,\; W_{p-1}$.
3. $k\leftarrow k+1$.
4. Если $k > p$, установить $k\leftarrow 1$.
5. $j\leftarrow k+q$.
6. Если $j > p$, установить $j \leftarrow j-p$.
7. EXCLUSIVE-OR, $W_k\oplus W_j$,
8. Запомнить, $W_k\leftarrow W_k\oplus W_j$.

Пример

Выберем примитивный трехчлен $x^5+x^2+1$. Базовая последовательность $\mathcal {f} a_1 \mathcal {g} = \mathcal {f} 0101110001110110011111001 \mathcal {g}$. Для этого конкретного многочлена второй столбец формируется путем задержки первого столбца на 25 ($25-31=-6$, в зависимости от ориентации "круга" бит) битовых позиций, третий столбец получается путем задержки второго столбца на другие - 6 битовых позиций, и так далее, пока все пять столбцов не будут заполнены.

Каждое $W$, появляется только один раз в течение всего периода из $2^5-1=31$ числа.

Сопровождающая матрица для полинома $x^5+x^2+1$:

$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}$

Составим матрицу, столбцами которой являются слова $W_0,\;W_1,\;W_2,\;W_3,\;W_4$, обозначим её $\mathbf W_0$ и перемножим на матрицу $\mathbf C$:

$\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}$

Мы получили матрицу, столбцами которой являются слова $W_1,\;W_2,\;W_3,\;W_4,\;W_5$. В матричном виде $\mathbf W_0 C=W_1$. После $2^5-1=31$ применения этой матрицы $\mathbf W_0 C^{31}=W_0$.

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

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

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

$\mu =\frac{1}{m} \sum^{m-1}_{i=0} {W_i}$, где $m=2^p-1$

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

$\mu =\frac{2^{p-L}}{m} \sum^{2^L-1}_{i=1} {i} +\frac{2^{p-L}-1}{m} \sum^{2^L-1}_{i=1} {0}=\frac{2^{p-L}}{m}\left [\frac{(2^L-1)(2^L)}{2} -1\right]\approx \frac{1}{2} \left (\frac{2^{p+L}}{m}\right )$.

На нормализованном (0, 1) интервале: $\mu_0\approx\frac{1}{2}$.

Дисперсия:

$\sigma^2=\frac{1}{m} \sum^{m-1}_{i=0} {W^2_i} -\mu^2=\frac{2^{p-L}}{m} \sum^{2^L-1}_{i=1} {i^2} -\mu^2\approx\frac{1}{3}\left (\frac{2^{p+L}}{m}\right )-\mu^2$,

и на нормализованном интервале (0, 1): $\sigma^2_0\approx\frac{1}{3} -\frac{1}{4} =\frac{1}{12}$.

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

$E[R(t)]=\frac{1}{m} \sum^{m-1}_{j=0} {\frac{1}{N}}\sum^{N-1}_{i=0} {W_iW_{i+t}}$.

Плюсы и минусы

Так как многие программные среды содержат битовые операции, такие как 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 (англ.)

• Random number generation and Monte carlo methods

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