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

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

Регистр сдвига с обобщённой обратной связью (англ. 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

Ссылки


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "Регистр сдвига с обобщённой обратной связью" в других словарях:

  • Генератор псевдослучайных чисел — (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика… …   Википедия

  • Вихрь Мерсенна — (англ. Mersenne twister, MT) генератор псевдослучайных чисел (ГПСЧ), разработанный в 1997 году японскими учёными Макото Мацумото (яп. 松本 眞) и Такудзи Нисимура (яп. 西村 拓士). Вихрь Мерсенна основывается на свойствах простых чисел Мерсенна… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»