Регистр сдвига с обобщённой обратной связью
Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Уильямом Пейном[англ.] в 1973 году.
Идея алгоритма GFSR состоит в том, что основная последовательность регистра сдвига с линейной обратной связью [math]\displaystyle{ \{a_k\} }[/math], основанная на примитивном трёхчлене [math]\displaystyle{ x^p+x^{p-q}+1 }[/math], записывается в [math]\displaystyle{ w }[/math] колонок, [math]\displaystyle{ w \lt p }[/math], с разумно выбранными циклическими сдвигами. [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] — произвольные натуральные числа, такие что [math]\displaystyle{ q \lt p }[/math], причём [math]\displaystyle{ q }[/math] примерно равных [math]\displaystyle{ (p+1)/2 }[/math] и [math]\displaystyle{ p }[/math], нужно избегать из-за плохих свойств результирующей последовательности.[1]
Таким образом все слова на выходе GFSR можно рассматривать как вектора длины [math]\displaystyle{ w }[/math], с коэффициентами из множества [math]\displaystyle{ \{0, 1\} }[/math], которые подчиняются рекурсии
[math]\displaystyle{ W_k=W_{k-p+q}\oplus W_{k-p} }[/math]
где [math]\displaystyle{ \oplus }[/math] — XOR, или побитовое сложение по модулю 2, а [math]\displaystyle{ k=p,\;p+1,\;... }[/math][2]
Сравнение с аналогичными алгоритмами
Линейный конгруэнтный генератор показывает плохую n-пространственную однородность. На рисунке предвиден пример результата работы для [math]\displaystyle{ 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]\displaystyle{ X^{31} + X^{13} + 1 }[/math], 9-битным машинным словом и циклическим сдвигом на 93[1]
История исследования GFSR
Льюисом и Пейном были представлены различные типы генераторов называемые регистры сдвига с обобщённой обратной связью. Этот быстрый метод и может генерировать одинаковые последовательности на компьютерах с разной длиной машинного слова, но он имеет недостаток с инициализацией.[3]
Во-первых, невырожденная битовая начальная матрица размером [math]\displaystyle{ p \times w }[/math]должна быть сформирована. Льюис и Пейн показали, что если относительный сдвиг между соседними колонками постоянен, то матрица не вырожденная. Постоянный сдвиг был произвольно выбран равным [math]\displaystyle{ 100p }[/math].[3]
Во-вторых, Льюис и Пейн предложили, с целью подавить эффект неслучайности начальной матрицы, отбрасывать первые [math]\displaystyle{ 5000p }[/math] чисел перед использованием генератора. Так, если нужна длинная последовательность и [math]\displaystyle{ p }[/math] большое, то процесс инициализации занимает много времени.
Другой недостаток который может быть более существенным, нет теоретического обоснования того, что последовательность будет обладать свойством k-распределения. Термин k-распределение означает, что каждый k-кортеж из [math]\displaystyle{ w }[/math]-бит чисел появляется [math]\displaystyle{ 2^{p-wk} }[/math] раз на полном периоде, за исключением нулевого кортежа. Они показали что последовательность может быть k-распределённая, для [math]\displaystyle{ 1 \leq k \leq \lfloor p/w \rfloor }[/math], но это необходимое, а не достаточное условие.[3]
Брайт (Bright) и Энисон (Enison) провели тесты на равнораспределение в пространствах большой размерности небольшой части последовательности с большим периодом. Оказалось что в тестах статистические свойства не повторяют свойства всей последовательности.[3]
Арвилиас (Arvillias) и Маритсас (Maritsas) предложили генератор типа GFSR, в которых [math]\displaystyle{ p-q }[/math] есть степень 2. Они показали что [math]\displaystyle{ p-q }[/math] элементов последовательности, почти равномерно распределённых вдоль периода, можно получить за один такт, используя переключатель и регистры сдвига. При этом относительный сдвиг аналитически определён. Это значит, что процесс инициализации становится столь же быстрым как и генерация случайных чисел. Но снова нет гарантий в k-распределении.[3]
Алгоритм GFSR
Входные значения:
- [math]\displaystyle{ p, q }[/math] — задают характеристический полином регистра сдвига
- [math]\displaystyle{ a_0, ..., a_{p-1} }[/math] — начальная битовая последовательность
Алгоритм:
- 1. Создаем массив битовых векторов [math]\displaystyle{ W_0,\;...,\; W_{p-1} }[/math], по которому будем перемещаться с индексом [math]\displaystyle{ k }[/math] и вспомогательным индексом [math]\displaystyle{ j }[/math].
- 2. Инициализируем массив, используя начальную битовую последовательность. Устанавливаем [math]\displaystyle{ k }[/math] равное 0.
- 3. Вычисляем следующий вектор, но так как массив длины [math]\displaystyle{ p }[/math], то индексы вычисляются по модулю [math]\displaystyle{ p }[/math], из-за чего
- [math]\displaystyle{ k-p+q \longrightarrow k+q }[/math]
- [math]\displaystyle{ k-p\longrightarrow k }[/math]
- Таким образом
- [math]\displaystyle{ j = k+q\mod p }[/math]
- [math]\displaystyle{ W_k = W_k \oplus W_j }[/math]
- 4. Увеличиваем [math]\displaystyle{ k }[/math] на единицу и переходим к вычислению следующего вектора, до тех пор пока последовательность не начнет повторяться (длина последовательности [math]\displaystyle{ 2^p-1 }[/math])[1]
Алгоритм инициализации
- Сначала генерируется последовательность согласно алгоритму регистра сдвига с линейной обратной связью.
- После чего полученная последовательность циклически сдвигается. Величина сдвига должна быть меньше периода [math]\displaystyle{ 2^p-1 }[/math], тогда гарантируется что стартовые вектора будут линейно независимы (если величина сдвига взаимно просто с [math]\displaystyle{ 2^p-1 }[/math], то сдвиг может превышать полный период).
- Используя эту процедуру, получаем [math]\displaystyle{ j }[/math] последовательностей, которые можно записать друг под другом. Первые [math]\displaystyle{ p }[/math] бит последовательностей образуют матрицу, столбцы которой являются векторами [math]\displaystyle{ W_0,\;...,\; W_{p-1} }[/math][1]
Пример
Пусть дан полином [math]\displaystyle{ x^5+x^3+1 }[/math], и [math]\displaystyle{ a_0 = a_1 = a_2 = a_3 = a_4 = 1 }[/math].
Элементы последовательности удовлетворяют равенству [math]\displaystyle{ a_k=a_{k-p+q}\oplus a_{k-p} }[/math] при [math]\displaystyle{ k = p, p+1, ... }[/math]. Согласно полиному [math]\displaystyle{ p = 5, q = 2 }[/math], так мы можем узнать элементы последовательности
[math]\displaystyle{ a_5=a_{2}\oplus a_{0} = 0 }[/math]
[math]\displaystyle{ a_6=a_{3}\oplus a_{1} = 0 }[/math]
[math]\displaystyle{ a_7=a_{4}\oplus a_{2} = 0 }[/math]
[math]\displaystyle{ a_8=a_{5}\oplus a_{3} = 1 }[/math]
и так далее.
Таким образом получаем последовательность [math]\displaystyle{ a_0^{30} = 1111100011011101010000100101100 }[/math]
Для того что-бы создать хорошую случайную последовательность воспользуемся алгоритмом Кендола (Kendall). Хотя есть несколько вариантов этого алгоритма мы возьмем тот, который сдвигает начальную последовательность 1111100011011101010000100|101100 вперед на 6 бит. То есть 1011001111100011011101010|000100 и так ещё 3 раза. Таким образом получим
| Номер | последовательность |
|---|---|
| 0 | 1111100011011101010000100[math]\displaystyle{ \mid }[/math]101100 |
| 1 | 1011001111100011011101010[math]\displaystyle{ \mid }[/math]000100 |
| 2 | 0001001011001111100011011[math]\displaystyle{ \mid }[/math]101010 |
| 3 | 1010100001001011001111100[math]\displaystyle{ \mid }[/math]011011 |
| 4 | 0110111010100001001011001[math]\displaystyle{ \mid }[/math]111100 |
[math]\displaystyle{ W_0 }[/math] образуется из первых бит последовательностей, [math]\displaystyle{ W_1 }[/math] — из вторых, для [math]\displaystyle{ W_2, W_3, W_4 }[/math] аналогично.
[math]\displaystyle{ W_0 = 11010, W_1 = 10001, W_2 = 11011, W_3 = 11100, W_4 = 10011 }[/math]
Последующие [math]\displaystyle{ W_k }[/math] вычисляем согласно правилу [math]\displaystyle{ W_k=W_{k-3}\oplus W_{k-5} }[/math].
| [math]\displaystyle{ W_0 : }[/math] | 11010 | [math]\displaystyle{ W_{10} : }[/math] | 01001 | [math]\displaystyle{ W_{20} : }[/math] | 00111 |
| [math]\displaystyle{ W_1 : }[/math] | 10001 | [math]\displaystyle{ W_{11} : }[/math] | 10000 | [math]\displaystyle{ W_{21} : }[/math] | 01111 |
| [math]\displaystyle{ W_2 : }[/math] | 11011 | [math]\displaystyle{ W_{12} : }[/math] | 10110 | [math]\displaystyle{ W_{22} : }[/math] | 10010 |
| [math]\displaystyle{ W_3 : }[/math] | 11100 | [math]\displaystyle{ W_{13} : }[/math] | 10100 | [math]\displaystyle{ W_{23} : }[/math] | 01100 |
| [math]\displaystyle{ W_4 : }[/math] | 10011 | [math]\displaystyle{ W_{14} : }[/math] | 01110 | [math]\displaystyle{ W_{24} : }[/math] | 00101 |
| [math]\displaystyle{ W_5 : }[/math] | 00001 | [math]\displaystyle{ W_{15} : }[/math] | 11111 | [math]\displaystyle{ W_{25} : }[/math] | 10101 |
| [math]\displaystyle{ W_6 : }[/math] | 01101 | [math]\displaystyle{ W_{16} : }[/math] | 00100 | [math]\displaystyle{ W_{26} : }[/math] | 00011 |
| [math]\displaystyle{ W_7 : }[/math] | 01000 | [math]\displaystyle{ W_{17} : }[/math] | 11000 | [math]\displaystyle{ W_{27} : }[/math] | 10111 |
| [math]\displaystyle{ W_8 : }[/math] | 11101 | [math]\displaystyle{ W_{18} : }[/math] | 01011 | [math]\displaystyle{ W_{28} : }[/math] | 11001 |
| [math]\displaystyle{ W_9 : }[/math] | 11110 | [math]\displaystyle{ W_{19} : }[/math] | 01010 | [math]\displaystyle{ W_{29} : }[/math] | 00110 |
Преимущества и недостатки
Преимущества
По словам разработчиков регистр сдвига с обобщённой обратной связью обладает произвольно большим периодом, независимо от длины машинного слова компьютера, который выполняет алгоритм, он быстрее чем другие генераторы псевдослучайных последовательностей, а также алгоритм легок в реализации.[1]
Недостатки
Согласно исследованиям количество 0 и 1 в выходной последовательности заметно разнится, а что противоречит постулатам Голомба. Также, если взять целое N, и разделить последовательность на кортежи по N слов, то для случайной последовательности распределение единиц в этих кортежах должно подчиняться биномиальному распределению Bin(N, 1/2). Но оказалось, что при [math]\displaystyle{ N \leqslant n }[/math] это условие не выполняется. Это из-за того, что каждое слово зависит только от двух предыдущих, и по этому преобладание единиц или нулей не «сглаживается» сумматором по модулю 2.[2]
Вихрь Мерсенна — пример улучшения GFSR
Широко известна модификация регистра сдвига с обобщённой обратной связью под названием «Вихрь Мерсенна», предложенный Макото Мацумото и Такудзи Нисимурой в 1997 году. Период этого генератора огромен, и равен числу Мерсенна [math]\displaystyle{ 2^{19937} - 1 }[/math]. Вихрь Мерсенна относят к классу витковых генераторов на регистрах сдвига с обобщёнными обратными связями. Его упрощённая схема приведена на рисунке
Рассмотрим наиболее распространённый вариант этого алгоритма — MT19937. Он использует 624 ячейки памяти, в каждой из которых содержится целое 32 битное число. При этом рекуррентное правило формирования последовательности выходных слов записывается таким образом:
[math]\displaystyle{ W_k = W_{k-397}\oplus ((W_{k-623} }[/math] & 0x80000000) | [math]\displaystyle{ (W_{k-622} }[/math] & 0x7fffffff))×[math]\displaystyle{ A }[/math], (i = 0, 1 , 2, …)
То есть, на каждом k-том шаге берётся старший бит слова [math]\displaystyle{ W_{k-623} }[/math], и 31 бит из слова [math]\displaystyle{ W_{k-622} }[/math], а затем полученные части конкатенируют с последующим умножением полученного результата на матрицу
[math]\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} }[/math]
где [math]\displaystyle{ a = (a_{w-1} a_{w-2} ... a_0) }[/math] = 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.
Примечания
- ↑ 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 T. G. Lewis, W. H. Payne. Generalized Feedback Shift Register Pseudorandom Number Algorithm // J. ACM. — 1973-07-01. — Т. 20, вып. 3. — С. 456–468. — ISSN 0004-5411. — doi:10.1145/321765.321777.
- ↑ 2,0 2,1 2,2 Н. Ф. Казакова, к.т.н., Ю. В. Щербина, к.т.н. ПРОБЛЕМЫ ОЦЕНКИ КАЧЕСТВА РАБОТЫ СОВРЕМЕННЫХ ЛИНЕЙНЫХ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ (рус.) // Збірник наукових праць ОДАТРЯ No 1(2 )2013. Архивировано 23 марта 2022 года.
- ↑ 3,0 3,1 3,2 3,3 3,4 M. Fushimi, S. Tezuka. The k-distribution of generalized feedback shift register pseudorandom numbers // Communications of the ACM. — 1983-07-01. — Т. 26, вып. 7. — С. 516–523. — ISSN 0001-0782. — doi:10.1145/358150.358159. Архивировано 16 ноября 2016 года.