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

Регистр сдвига с обобщённой обратной связью (Шаблон:Lang-en) — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Шаблон:Нп5 в 1973 году.

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

Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига с линейной обратной связью $\{a_k\}$, основанная на примитивном трёхчлене $x^p+x^{p-q}+1$, записывается в $w$ колонок, $w<p$, с разумно выбранными циклическими сдвигами. $p$ и $q$ — произвольные натуральные числа, такие что $q<p$, причём $q$ примерно равных $(p+1)/2$ и $p$, нужно избегать из-за плохих свойств результирующей последовательности.

Таким образом все слова на выходе GFSR можно рассматривать как вектора длины $w$, с коэффициентами из множества $\{0,1\}$, которые подчиняются рекурсии

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

где $\oplus$ — XOR, или побитовое сложение по модулю 2, а $k=p,p+1,...$

Сравнение с аналогичными алгоритмами

Результат работы линейного конгруэнтного генератора

Линейный конгруэнтный генератор показывает плохую n-пространственную однородность. На рисунке предвиден пример результата работы для $X_i=17X_{i-1}-1mod512$ для 384 точек (a) и 512 (b).

Результат работы GFSR

Как альтернатива, регистр сдвига с линейной обратной связью (FSR) даёт равномерное распределение в n-мерном пространстве, если длина регистра делится на n. Возможно FSR последовательности дают больше возможностей для улучшения n-мерного пространства, но период ограничен машинным словом. Кроме того, прореживание, с целью получить однородность n-мерном пространстве далее сокращает длину цикла.

Из-за этого был создан регистр сдвига с обобщённой обратной связью, способный генерировать сколь угодно большие последовательности, независимо от размера машинного слова, также обладающий хорошим n-мерным распределением и большой скоростью.

На рисунке предвиден пример результата работы GFSR c полиномом $X^{31}+X^{13}+1$, 9-битным машинным словом и циклическим сдвигом на 93

История исследования GFSR

Льюисом и Пейном были представлены различные типы генераторов называемые регистры сдвига с обобщённой обратной связью. Этот быстрый метод и может генерировать одинаковые последовательности на компьютерах с разной длиной машинного слова, но он имеет недостаток с инициализацией.

Во-первых, невырожденная битовая начальная матрица размером $p\times w$должна быть сформирована. Льюис и Пейн показали, что если относительный сдвиг между соседними колонками постоянен, то матрица не вырожденная. Постоянный сдвиг был произвольно выбран равным $100p$.

Во-вторых, Льюис и Пейн предложили, с целью подавить эффект неслучайности начальной матрицы, отбрасывать первые $5000p$ чисел перед использованием генератора. Так, если нужна длинная последовательность и $p$ большое, то процесс инициализации занимает много времени.

Другой недостаток который может быть более существенным, нет теоретического обоснования того, что последовательность будет обладать свойством k-распределения. Термин k-распределение означает, что каждый k-кортеж из $w$-бит чисел появляется $2^{p-wk}$ раз на полном периоде, за исключением нулевого кортежа. Они показали что последовательность может быть k-распределённая, для $1\le k\le \lfloor p/w\rfloor$, но это необходимое, а не достаточное условие.

Брайт (Bright) и Энисон (Enison) провели тесты на равнораспределение в пространствах большой размерности небольшой части последовательности с большим периодом. Оказалось что в тестах статистические свойства не повторяют свойства всей последовательности.

Арвилиас (Arvillias) и Маритсас (Maritsas) предложили генератор типа GFSR, в которых $p-q$ есть степень 2. Они показали что $p-q$ элементов последовательности, почти равномерно распределённых вдоль периода, можно получить за один такт, используя переключатель и регистры сдвига. При этом относительный сдвиг аналитически определён. Это значит, что процесс инициализации становится столь же быстрым как и генерация случайных чисел. Но снова нет гарантий в k-распределении.

Алгоритм GFSR

Входные значения:

• $p,q$ — задают характеристический полином регистра сдвига
• $a_0,...,a_{p-1}$ — начальная битовая последовательность

Алгоритм:

1. Создаем массив битовых векторов $W_0,...,W_{p-1}$, по которому будем перемещаться с индексом $k$ и вспомогательным индексом $j$.

2. Инициализируем массив, используя начальную битовую последовательность. Устанавливаем $k$ равное 0.

3. Вычисляем следующий вектор, но так как массив длины $p$, то индексы вычисляются по модулю $p$, из-за чего

$k-p+q⟶k+q$

$k-p⟶k$

Таким образом

$j=k+qmodp$

$W_k=W_k\oplus W_j$

4. Увеличиваем $k$ на единицу и переходим к вычислению следующего вектора, до тех пор пока последовательность не начнет повторяться (длина последовательности $2^p-1$)

Алгоритм инициализации

1. Сначала генерируется последовательность согласно алгоритму регистра сдвига с линейной обратной связью.
2. После чего полученная последовательность циклически сдвигается. Величина сдвига должна быть меньше периода $2^p-1$, тогда гарантируется что стартовые вектора будут линейно независимы (если величина сдвига взаимно просто с $2^p-1$, то сдвиг может превышать полный период).
3. Используя эту процедуру, получаем $j$ последовательностей, которые можно записать друг под другом. Первые $p$ бит последовательностей образуют матрицу, столбцы которой являются векторами $W_0,...,W_{p-1}$

Пример

Пусть дан полином $x^5+x^3+1$, и $a_0=a_1=a_2=a_3=a_4=1$.

Элементы последовательности удовлетворяют равенству $a_k=a_{k-p+q}\oplus a_{k-p}$ при $k=p,p+1,...$. Согласно полиному $p=5,q=2$, так мы можем узнать элементы последовательности

$a_5=a_2\oplus a_0=0$

$a_6=a_3\oplus a_1=0$

$a_7=a_4\oplus a_2=0$

$a_8=a_5\oplus a_3=1$

и так далее.

Таким образом получаем последовательность $a_0^{30}=1111100011011101010000100101100$

Для того чтобы создать хорошую случайную последовательность воспользуемся алгоритмом Кендола (Kendall). Хотя есть несколько вариантов этого алгоритма мы возьмем тот, который сдвигает начальную последовательность 1111100011011101010000100|101100 вперед на 6 бит. То есть 1011001111100011011101010|000100 и так ещё 3 раза. Таким образом получим

Номер	последовательность
0	1111100011011101010000100$\mid$101100
1	1011001111100011011101010$\mid$000100
2	0001001011001111100011011$\mid$101010
3	1010100001001011001111100$\mid$011011
4	0110111010100001001011001$\mid$111100

$W_0$ образуется из первых бит последовательностей, $W_1$ — из вторых, для $W_2,W_3,W_4$ аналогично.

$W_0=11010,W_1=10001,W_2=11011,W_3=11100,W_4=10011$

Последующие $W_k$ вычисляем согласно правилу $W_k=W_{k-3}\oplus W_{k-5}$.

$W_0:$	11010	$W_{10}:$	01001	$W_{20}:$	00111
$W_1:$	10001	$W_{11}:$	10000	$W_{21}:$	01111
$W_2:$	11011	$W_{12}:$	10110	$W_{22}:$	10010
$W_3:$	11100	$W_{13}:$	10100	$W_{23}:$	01100
$W_4:$	10011	$W_{14}:$	01110	$W_{24}:$	00101
$W_5:$	00001	$W_{15}:$	11111	$W_{25}:$	10101
$W_6:$	01101	$W_{16}:$	00100	$W_{26}:$	00011
$W_7:$	01000	$W_{17}:$	11000	$W_{27}:$	10111
$W_8:$	11101	$W_{18}:$	01011	$W_{28}:$	11001
$W_9:$	11110	$W_{19}:$	01010	$W_{29}:$	00110

Преимущества и недостатки

Преимущества

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

Недостатки

Согласно исследованиям количество 0 и 1 в выходной последовательности заметно разнится, а что противоречит постулатам Голомба. Также, если взять целое N, и разделить последовательность на кортежи по N слов, то для случайной последовательности распределение единиц в этих кортежах должно подчиняться биномиальному распределению Bin(N, 1/2). Но оказалось, что при $N⩽n$ это условие не выполняется. Это из-за того, что каждое слово зависит только от двух предыдущих, и по этому преобладание единиц или нулей не «сглаживается» сумматором по модулю 2.

Вихрь Мерсенна — пример улучшения GFSR

Широко известна модификация регистра сдвига с обобщённой обратной связью под названием «Вихрь Мерсенна», предложенный Макото Мацумото и Такудзи Нисимурой в 1997 году. Период этого генератора огромен, и равен числу Мерсенна $2^{19937}-1$. Вихрь Мерсенна относят к классу витковых генераторов на регистрах сдвига с обобщёнными обратными связями. Его упрощённая схема приведена на рисунке

Упрощённая схема вихря Мерсенна

Рассмотрим наиболее распространённый вариант этого алгоритма — MT19937. Он использует 624 ячейки памяти, в каждой из которых содержится целое 32 битное число. При этом рекуррентное правило формирования последовательности выходных слов записывается таким образом:

$W_k=W_{k-397}\oplus ((W_{k-623}$ & 0x80000000) | $(W_{k-622}$ & 0x7fffffff))×$A$, (i = 0, 1 , 2, …)

То есть, на каждом k-том шаге берётся старший бит слова $W_{k-623}$, и 31 бит из слова $W_{k-622}$, а затем полученные части конкатенируют с последующим умножением полученного результата на матрицу

$A=\left(\begin{array}{ccccc}0& 1& 0& 0& 0\\ 0& 0& 1& 0& 0\\ ...& ...& ...& ...& ...\\ 0& 0& 0& 0& 1\\ a_{w-1}& a_{w-2}& ...& ...& a_0\end{array}\right)$

где $a=(a_{w-1}{a}_{w-2}...a_0)$ = 0x9908B0DF в шестнадцатеричном исчислении.

После этого, результат складывается по модулю 2 со словом, вычисленного на предыдущем 397-м шаге. Затем делается сдвиг содержимого всех ячеек на шаг влево, и полученный результат записывается в освободившуюся ячейку.

См. также

• Регистр сдвига с обратной связью по переносу
• Регистр сдвига с линейной обратной связью

Литература

• Шаблон:Статья
• Шаблон:Книга

Ссылки

• Logical IntuitionsШаблон:Ref-en
• Random number generation and Monte carlo methodsШаблон:Ref-en
• Payne Generalized Feedback Shift Register Pseudorandom Number Algorithm in ACM digital libraryШаблон:Ref-en
• Проблемы оценки качества работы современныхлинейных генераторовпсевдослучайных последовательностей