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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм:

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

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

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

${\displaystyle k-p+q\longrightarrow k+q}$

${\displaystyle k-p\longrightarrow k}$

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

${\displaystyle j=k+q\mod p}$

${\displaystyle W_{k}=W_{k}\oplus W_{j}}$

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

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

Пусть дан полином ${\displaystyle x^{5}+x^{3}+1}$, и ${\displaystyle a_{0}=a_{1}=a_{2}=a_{3}=a_{4}=1}$.

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

${\displaystyle a_{5}=a_{2}\oplus a_{0}=0}$

${\displaystyle a_{6}=a_{3}\oplus a_{1}=0}$

${\displaystyle a_{7}=a_{4}\oplus a_{2}=0}$

${\displaystyle a_{8}=a_{5}\oplus a_{3}=1}$

и так далее.

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

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

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

${\displaystyle W_{0}}$ образуется из первых бит последовательностей, ${\displaystyle W_{1}}$ — из вторых, для ${\displaystyle W_{2},W_{3},W_{4}}$ аналогично.

${\displaystyle W_{0}=11010,W_{1}=10001,W_{2}=11011,W_{3}=11100,W_{4}=10011}$

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

${\displaystyle W_{0}:}$	11010	${\displaystyle W_{10}:}$	01001	${\displaystyle W_{20}:}$	00111
${\displaystyle W_{1}:}$	10001	${\displaystyle W_{11}:}$	10000	${\displaystyle W_{21}:}$	01111
${\displaystyle W_{2}:}$	11011	${\displaystyle W_{12}:}$	10110	${\displaystyle W_{22}:}$	10010
${\displaystyle W_{3}:}$	11100	${\displaystyle W_{13}:}$	10100	${\displaystyle W_{23}:}$	01100
${\displaystyle W_{4}:}$	10011	${\displaystyle W_{14}:}$	01110	${\displaystyle W_{24}:}$	00101
${\displaystyle W_{5}:}$	00001	${\displaystyle W_{15}:}$	11111	${\displaystyle W_{25}:}$	10101
${\displaystyle W_{6}:}$	01101	${\displaystyle W_{16}:}$	00100	${\displaystyle W_{26}:}$	00011
${\displaystyle W_{7}:}$	01000	${\displaystyle W_{17}:}$	11000	${\displaystyle W_{27}:}$	10111
${\displaystyle W_{8}:}$	11101	${\displaystyle W_{18}:}$	01011	${\displaystyle W_{28}:}$	11001
${\displaystyle W_{9}:}$	11110	${\displaystyle W_{19}:}$	01010	${\displaystyle W_{29}:}$	00110

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

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

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

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

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

${\displaystyle A={\begin{pmatrix}0&1&0&0&0\\0&0&1&0&0\\...&...&...&...&...\\0&0&0&0&1\\a_{w-1}&a_{w-2}&...&...&a_{0}\end{pmatrix}}}$

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

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

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

• 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 (англ.)
• Проблемы оценки качества работы современныхлинейных генераторовпсевдослучайных последовательностей