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

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



Регистр сдвига с обобщённой обратной связью (англ. Generalized feedback shift register (GFSR)) — вариант генератора псевдослучайных чисел (ГПСЧ) Таусворта, предложенный Теодором Льюисом и Уильямом Пейном в 1973 году.

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

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

W k = W k − p + q ⊕ W k − p {displaystyle W_{k}=W_{k-p+q}oplus W_{k-p}}

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм GFSR

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

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

Алгоритм:

1. Создаем массив битовых векторов W 0 , . . . , W p − 1 {displaystyle W_{0},;...,;W_{p-1}} , по которому будем перемещаться с индексом k {displaystyle k} и вспомогательным индексом j {displaystyle j} . 2. Инициализируем массив, используя начальную битовую последовательность. Устанавливаем k {displaystyle k} равное 0. 3. Вычисляем следующий вектор, но так как массив длины p {displaystyle p} , то индексы вычисляются по модулю p {displaystyle p} , из-за чего k − p + q ⟶ k + q {displaystyle k-p+qlongrightarrow k+q} k − p ⟶ k {displaystyle k-plongrightarrow k} Таким образом j = k + q mod p {displaystyle j=k+qmod p} W k = W k ⊕ W j {displaystyle W_{k}=W_{k}oplus W_{j}} 4. Увеличиваем k {displaystyle k} на единицу и переходим к вычислению следующего вектора, до тех пор пока последовательность не начнет повторяться (длина последовательности 2 p − 1 {displaystyle 2^{p}-1} )

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

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

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

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

    a 5 = a 2 ⊕ a 0 = 0 {displaystyle a_{5}=a_{2}oplus a_{0}=0}

    a 6 = a 3 ⊕ a 1 = 0 {displaystyle a_{6}=a_{3}oplus a_{1}=0}

    a 7 = a 4 ⊕ a 2 = 0 {displaystyle a_{7}=a_{4}oplus a_{2}=0}

    a 8 = a 5 ⊕ a 3 = 1 {displaystyle a_{8}=a_{5}oplus a_{3}=1}

    и так далее.

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

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

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

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

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

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

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

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

    Недостатки

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

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

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

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

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

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

    A = ( 0 1 0 0 0 0 0 1 0 0 . . . . . . . . . . . . . . . 0 0 0 0 1 a w − 1 a w − 2 . . . . . . a 0 ) {displaystyle A={egin{pmatrix}0&1&0&0&0&0&1&0&0...&...&...&...&...&0&0&0&1a_{w-1}&a_{w-2}&...&...&a_{0}end{pmatrix}}}

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

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


    Добавлено Admin 7-08-2022, 12:00 Просмотров: 21
    Добавить комментарий
    Ваше Имя:
    Ваш E-Mail:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent