Русская Википедия:Регистр сдвига с обобщённой обратной связью
Регистр сдвига с обобщённой обратной связью (Шаблон:Lang-en) — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Шаблон:Нп5 в 1973 году.
Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига с линейной обратной связью <math>\{a_k\}</math>, основанная на примитивном трёхчлене <math>x^p+x^{p-q}+1</math>, записывается в <math>w</math> колонок, <math>w < p</math>, с разумно выбранными циклическими сдвигами. <math>p</math> и <math>q</math> — произвольные натуральные числа, такие что <math>q < p</math>, причём <math>q</math> примерно равных <math>(p+1)/2</math> и <math>p</math>, нужно избегать из-за плохих свойств результирующей последовательности.[1]
Таким образом все слова на выходе GFSR можно рассматривать как вектора длины <math>w</math>, с коэффициентами из множества <math>\{0, 1\}</math>, которые подчиняются рекурсии
<math>W_k=W_{k-p+q}\oplus W_{k-p}</math>
где <math>\oplus</math> — XOR, или побитовое сложение по модулю 2, а <math>k=p,\;p+1,\;...</math>[2]
Сравнение с аналогичными алгоритмами
Линейный конгруэнтный генератор показывает плохую n-пространственную однородность. На рисунке предвиден пример результата работы для <math>X_i = 17X_{i-1} - 1 \mod 512</math> для 384 точек (a) и 512 (b).[1]
Как альтернатива, регистр сдвига с линейной обратной связью (FSR) даёт равномерное распределение в n-мерном пространстве, если длина регистра делится на n. Возможно FSR последовательности дают больше возможностей для улучшения n-мерного пространства, но период ограничен машинным словом. Кроме того, прореживание, с целью получить однородность n-мерном пространстве далее сокращает длину цикла.[1]
Из-за этого был создан регистр сдвига с обобщённой обратной связью, способный генерировать сколь угодно большие последовательности, независимо от размера машинного слова, также обладающий хорошим n-мерным распределением и большой скоростью.[1]
На рисунке предвиден пример результата работы GFSR c полиномом <math>X^{31} + X^{13} + 1</math>, 9-битным машинным словом и циклическим сдвигом на 93[1]
История исследования GFSR
Льюисом и Пейном были представлены различные типы генераторов называемые регистры сдвига с обобщённой обратной связью. Этот быстрый метод и может генерировать одинаковые последовательности на компьютерах с разной длиной машинного слова, но он имеет недостаток с инициализацией.[3]
Во-первых, невырожденная битовая начальная матрица размером <math>p \times w</math>должна быть сформирована. Льюис и Пейн показали, что если относительный сдвиг между соседними колонками постоянен, то матрица не вырожденная. Постоянный сдвиг был произвольно выбран равным <math>100p</math>.[3]
Во-вторых, Льюис и Пейн предложили, с целью подавить эффект неслучайности начальной матрицы, отбрасывать первые <math>5000p</math> чисел перед использованием генератора. Так, если нужна длинная последовательность и <math>p</math> большое, то процесс инициализации занимает много времени.
Другой недостаток который может быть более существенным, нет теоретического обоснования того, что последовательность будет обладать свойством k-распределения. Термин k-распределение означает, что каждый k-кортеж из <math>w</math>-бит чисел появляется <math>2^{p-wk}</math> раз на полном периоде, за исключением нулевого кортежа. Они показали что последовательность может быть k-распределённая, для <math>1 \leq k \leq \lfloor p/w \rfloor</math>, но это необходимое, а не достаточное условие.[3]
Брайт (Bright) и Энисон (Enison) провели тесты на равнораспределение в пространствах большой размерности небольшой части последовательности с большим периодом. Оказалось что в тестах статистические свойства не повторяют свойства всей последовательности.[3]
Арвилиас (Arvillias) и Маритсас (Maritsas) предложили генератор типа GFSR, в которых <math>p-q</math> есть степень 2. Они показали что <math>p-q</math> элементов последовательности, почти равномерно распределённых вдоль периода, можно получить за один такт, используя переключатель и регистры сдвига. При этом относительный сдвиг аналитически определён. Это значит, что процесс инициализации становится столь же быстрым как и генерация случайных чисел. Но снова нет гарантий в k-распределении.[3]
Алгоритм GFSR
Входные значения:
- <math> p, q</math> — задают характеристический полином регистра сдвига
- <math>a_0, ..., a_{p-1}</math> — начальная битовая последовательность
Алгоритм:
- 1. Создаем массив битовых векторов <math>W_0,\;...,\; W_{p-1}</math>, по которому будем перемещаться с индексом <math>k</math> и вспомогательным индексом <math>j</math>.
- 2. Инициализируем массив, используя начальную битовую последовательность. Устанавливаем <math>k</math> равное 0.
- 3. Вычисляем следующий вектор, но так как массив длины <math>p</math>, то индексы вычисляются по модулю <math>p</math>, из-за чего
- <math> k-p+q \longrightarrow k+q </math>
- <math> k-p\longrightarrow k </math>
- Таким образом
- <math> j = k+q\mod p </math>
- <math>W_k = W_k \oplus W_j</math>
- 4. Увеличиваем <math> k </math> на единицу и переходим к вычислению следующего вектора, до тех пор пока последовательность не начнет повторяться (длина последовательности <math>2^p-1</math>)[1]
Алгоритм инициализации
- Сначала генерируется последовательность согласно алгоритму регистра сдвига с линейной обратной связью.
- После чего полученная последовательность циклически сдвигается. Величина сдвига должна быть меньше периода <math>2^p-1</math>, тогда гарантируется что стартовые вектора будут линейно независимы (если величина сдвига взаимно просто с <math>2^p-1</math>, то сдвиг может превышать полный период).
- Используя эту процедуру, получаем <math>j</math> последовательностей, которые можно записать друг под другом. Первые <math>p</math> бит последовательностей образуют матрицу, столбцы которой являются векторами <math>W_0,\;...,\; W_{p-1}</math>[1]
Пример
Пусть дан полином <math>x^5+x^3+1</math>, и <math>a_0 = a_1 = a_2 = a_3 = a_4 = 1</math>.
Элементы последовательности удовлетворяют равенству <math>a_k=a_{k-p+q}\oplus a_{k-p}</math> при <math>k = p, p+1, ...</math>. Согласно полиному <math>p = 5, q = 2</math>, так мы можем узнать элементы последовательности
<math>a_5=a_{2}\oplus a_{0} = 0</math>
<math>a_6=a_{3}\oplus a_{1} = 0</math>
<math>a_7=a_{4}\oplus a_{2} = 0</math>
<math>a_8=a_{5}\oplus a_{3} = 1</math>
и так далее.
Таким образом получаем последовательность <math>a_0^{30} = 1111100011011101010000100101100</math>
Для того чтобы создать хорошую случайную последовательность воспользуемся алгоритмом Кендола (Kendall). Хотя есть несколько вариантов этого алгоритма мы возьмем тот, который сдвигает начальную последовательность 1111100011011101010000100|101100 вперед на 6 бит. То есть 1011001111100011011101010|000100 и так ещё 3 раза. Таким образом получим
| Номер | последовательность |
|---|---|
| 0 | 1111100011011101010000100<math>\mid</math>101100 |
| 1 | 1011001111100011011101010<math>\mid</math>000100 |
| 2 | 0001001011001111100011011<math>\mid</math>101010 |
| 3 | 1010100001001011001111100<math>\mid</math>011011 |
| 4 | 0110111010100001001011001<math>\mid</math>111100 |
<math>W_0</math> образуется из первых бит последовательностей, <math>W_1</math> — из вторых, для <math>W_2, W_3, W_4</math> аналогично.
<math>W_0 = 11010, W_1 = 10001, W_2 = 11011, W_3 = 11100, W_4 = 10011</math>
Последующие <math>W_k</math> вычисляем согласно правилу <math>W_k=W_{k-3}\oplus W_{k-5}</math>.
| <math>W_0 :</math> | 11010 | <math>W_{10} :</math> | 01001 | <math>W_{20} :</math> | 00111 |
| <math>W_1 :</math> | 10001 | <math>W_{11} :</math> | 10000 | <math>W_{21} :</math> | 01111 |
| <math>W_2 :</math> | 11011 | <math>W_{12} :</math> | 10110 | <math>W_{22} :</math> | 10010 |
| <math>W_3 :</math> | 11100 | <math>W_{13} :</math> | 10100 | <math>W_{23} :</math> | 01100 |
| <math>W_4 :</math> | 10011 | <math>W_{14} :</math> | 01110 | <math>W_{24} :</math> | 00101 |
| <math>W_5 :</math> | 00001 | <math>W_{15} :</math> | 11111 | <math>W_{25} :</math> | 10101 |
| <math>W_6 :</math> | 01101 | <math>W_{16} :</math> | 00100 | <math>W_{26} :</math> | 00011 |
| <math>W_7 :</math> | 01000 | <math>W_{17} :</math> | 11000 | <math>W_{27} :</math> | 10111 |
| <math>W_8 :</math> | 11101 | <math>W_{18} :</math> | 01011 | <math>W_{28} :</math> | 11001 |
| <math>W_9 :</math> | 11110 | <math>W_{19} :</math> | 01010 | <math>W_{29} :</math> | 00110 |
Преимущества и недостатки
Преимущества
По словам разработчиков регистр сдвига с обобщённой обратной связью обладает произвольно большим периодом, независимо от длины машинного слова компьютера, который выполняет алгоритм, он быстрее чем другие генераторы псевдослучайных последовательностей, а также алгоритм легок в реализации.[1]
Недостатки
Согласно исследованиям количество 0 и 1 в выходной последовательности заметно разнится, а что противоречит постулатам Голомба. Также, если взять целое N, и разделить последовательность на кортежи по N слов, то для случайной последовательности распределение единиц в этих кортежах должно подчиняться биномиальному распределению Bin(N, 1/2). Но оказалось, что при <math>N \leqslant n</math> это условие не выполняется. Это из-за того, что каждое слово зависит только от двух предыдущих, и по этому преобладание единиц или нулей не «сглаживается» сумматором по модулю 2.[2]
Вихрь Мерсенна — пример улучшения GFSR
Широко известна модификация регистра сдвига с обобщённой обратной связью под названием «Вихрь Мерсенна», предложенный Макото Мацумото и Такудзи Нисимурой в 1997 году. Период этого генератора огромен, и равен числу Мерсенна <math>2^{19937} - 1</math>. Вихрь Мерсенна относят к классу витковых генераторов на регистрах сдвига с обобщёнными обратными связями. Его упрощённая схема приведена на рисунке
Рассмотрим наиболее распространённый вариант этого алгоритма — MT19937. Он использует 624 ячейки памяти, в каждой из которых содержится целое 32 битное число. При этом рекуррентное правило формирования последовательности выходных слов записывается таким образом:
<math>W_k = W_{k-397}\oplus ((W_{k-623}</math> & 0x80000000) | <math>(W_{k-622} </math> & 0x7fffffff))×<math>A</math>, (i = 0, 1 , 2, …)
То есть, на каждом k-том шаге берётся старший бит слова <math>W_{k-623}</math>, и 31 бит из слова <math>W_{k-622}</math>, а затем полученные части конкатенируют с последующим умножением полученного результата на матрицу
<math>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}</math>
где <math>a = (a_{w-1} a_{w-2} ... a_0)</math> = 0x9908B0DF в шестнадцатеричном исчислении.
После этого, результат складывается по модулю 2 со словом, вычисленного на предыдущем 397-ом шаге. Затем делается сдвиг содержимого всех ячеек на шаг влево, и полученный результат записывается в освободившуюся ячейку.[2]
См. также
Литература
Примечания
Ссылки
- 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
- Проблемы оценки качества работы современныхлинейных генераторовпсевдослучайных последовательностей
