Generalized Feedback Shift Register

Generalized feedback shift register ( GFSR) är en variant av Towsworths pseudo-slumptalsgenerator (PRNG) föreslogs av Theodore Lewis och William Payne 1973.

Tanken bakom GFSR- algoritmen är att den grundläggande linjära återkopplingsskiftregistersekvensen , baserad på ett primitivt trinomial , skrivs i kolumner, , med förnuftigt valda cykliska skift. och är godtyckliga naturliga tal sådana att , och ungefär lika med och , bör undvikas på grund av de dåliga egenskaperna hos den resulterande sekvensen. [ett] $\{a_{k}\}$ $x^{p}+x^{pq}+1$ $w$ $w<p$ $sid$ $q$ $q<p$ $q$ $(p+1)/2$ $sid$

Således kan alla ord i GFSR-utmatningen ses som vektorer av längd , med koefficienter från mängden som lyder rekursionen $w$ $\{0,1\}$

${\displaystyle W_{k}=W_{k-p+q}\oplus W_{kp))$

där är XOR , eller bitvis addition modulo 2 , och [2] $\ plus$ $k=p,\;p+1,\;...$

Jämförelse med liknande algoritmer

Den linjära kongruentialgeneratorn visar dålig enhetlighet i n-rymden. Figuren ger ett exempel på resultatet av arbetet för 384 poäng (a) och 512 (b). [ett] $X_{i}=17X_{i-1}-1\mod 512$

Alternativt ger ett linjärt återkopplingsskiftregister (FSR) en enhetlig fördelning i n-dimensionell rymd om registrets längd är delbar med n. Kanske ger FSR-sekvenser fler möjligheter att förbättra det n-dimensionella rummet, men perioden begränsas av maskinordet . Dessutom minskar decimering, för att erhålla enhetlighet i n-dimensionellt utrymme, cykelns längd ytterligare. [ett]

På grund av detta skapades ett generaliserat återkopplingsskiftregister, kapabelt att generera godtyckligt stora sekvenser, oavsett storleken på maskinordet, även med en god n-dimensionell fördelning och hög hastighet. [ett]

Figuren förutser ett exempel på resultatet av GFSR-operationen med ett polynom , ett 9-bitars maskinord och ett cykliskt skifte med 93 [1] $X^{31}+X^{13}+1$

Historia om GFSR-studien

Lewis och Payne introducerade olika typer av generatorer som kallas generaliserade återkopplingsskiftregister. Denna metod är snabb och kan generera samma sekvenser på datorer med olika maskinordslängder , men den har en nackdel med initialisering. [3]

Först måste en initial matris med icke- degenererad bitstorlek bildas. Lewis och Payne visade att om den relativa förskjutningen mellan intilliggande kolumner är konstant, så är matrisen inte degenererad. Det konstanta skiftet valdes godtyckligt till . [3] $p\times w$ $100p$

För det andra föreslog Lewis och Payne, för att undertrycka effekten av icke-slumpmässighet i den initiala matrisen, att kassera de första siffrorna innan generatorn användes. Så om du behöver en lång sekvens och en stor, tar initieringsprocessen mycket tid. $5000p$ $sid$

En annan nackdel, som kan vara mer betydande, är att det inte finns någon teoretisk motivering för att sekvensen kommer att ha k-fördelningsegenskapen. Termen k-fördelning betyder att varje k-tuppel av -bittal förekommer en gång i en hel period, förutom nolltupeln. De visade att sekvensen kan vara k-fördelad, för , men detta är ett nödvändigt, inte ett tillräckligt villkor. [3] $w$ ${\displaystyle 2^{p-wk))$ $1\leq k\leq \lfloor p/w\rfloor$

Bright (Bright) och Enison (Enison) utförde tester för equipartition i utrymmen med hög dimension av en liten del av sekvensen med en stor period. Det visade sig att de statistiska egenskaperna i testerna inte upprepar egenskaperna för hela sekvensen. [3]

Arvillias och Maritsas föreslog en generator av GFSR-typ, som har en effekt av 2. De visade att sekvenselement, nästan jämnt fördelade över perioden, kan erhållas i en cykel med hjälp av en switch och skiftregister . I detta fall bestäms den relativa förskjutningen analytiskt. Detta innebär att initieringsprocessen blir lika snabb som genereringen av slumptal. Men återigen finns det inga garantier i k-fördelningen. [3] $pq$ $pq$

GFSR-algoritm

Ingångsvärden:

$p,q$ — ställ in det karakteristiska polynomet för skiftregistret
$a_{0},...,a_{p-1}$ - initial bitsekvens

Algoritm:

1. Vi skapar en array av bitvektorer , längs vilka vi kommer att röra oss med ett index och ett hjälpindex .

{\displaystyle W_{0},\;...,\;W_{p-1))

k

j

2. Initiera arrayen med den initiala bitsekvensen. Sätt lika med 0.

k

3. Vi beräknar nästa vektor, men eftersom matrisen av längd , då beräknas indexen modulo , på grund av vilket

sid

sid

k-p+q\longrightarrow k+q

kp\longrightarrow k

På det här sättet

j=k+q\mod p

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

4. Öka med en och fortsätt till beräkningen av nästa vektor, tills sekvensen börjar upprepas (sekvenslängd ) [1]

k

2^{p}-1

Initialiseringsalgoritm

Först genereras en sekvens enligt den linjära återkopplings- skiftregisteralgoritmen .
Därefter förskjuts den resulterande sekvensen cykliskt . Skiftvärdet måste vara mindre än perioden , då är det garanterat att startvektorerna kommer att vara linjärt oberoende (om skiftvärdet är coprime med , då kan skiftet överskrida hela perioden). $2^{p}-1$ $2^{p}-1$
Med denna procedur får vi sekvenser som kan skrivas under varandra. De första bitarna i sekvenserna bildar en matris vars kolumner är vektorer [1] $j$ $sid$ ${\displaystyle W_{0},\;...,\;W_{p-1))$

Exempel

Låt ett polynom ges , och . $x^{5}+x^{3}+1$ $a_{0}=a_{1}=a_{2}=a_{3}=a_{4}=1$

Elementen i sekvensen uppfyller likheten för . Enligt polynomet , så vi kan ta reda på elementen i sekvensen ${\displaystyle a_{k}=a_{k-p+q}\oplus a_{kp))$ $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$

och så vidare.

Därmed får vi sekvensen $a_{0}^{30}=1111100011011101010000100101100$

För att skapa en bra slumpmässig sekvens använder vi Kendall-algoritmen (Kendall). Även om det finns flera varianter av denna algoritm kommer vi att ta den som flyttar den initiala sekvensen 1111100011011101010000100|101100 framåt med 6 bitar. Det vill säga 1011001111100011011101010|000100 och så vidare 3 gånger till. Så får vi

siffra	efterföljande
0	1111100011011101010000100 101100 $\mitten$
ett	1011001111100011011101010 000100 $\mitten$
2	0001001011001111100011011 101010 $\mitten$
3	1010100001001011001111100 011011 $\mitten$
fyra	0110111010100001001011001 111100 $\mitten$

$W_0$ bildas från de första bitarna av sekvenserna, - från den andra, för liknande. $W_{1}$ ${\displaystyle W_{2},W_{3},W_{4))$

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

De efterföljande beräknas enligt regeln . $W_{k}$ ${\displaystyle W_{k}=W_{k-3}\oplus W_{k-5))$

$W_{0}:$	11010	$W_{10}:$	01001	$W_{20}:$	00111
$W_{1}:$	10001	$W_{11}:$	10 000	$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}:$	11 000	$W_{27}:$	10111
$W_{8}:$	11101	$W_{18}:$	01011	$W_{28}:$	11001
$W_{9}:$	11110	$W_{19}:$	01010	$W_{29}:$	00110

Fördelar och nackdelar

Fördelar

Enligt utvecklarna har det generaliserade återkopplingsskiftregistret en godtyckligt lång period, oavsett längden på maskinordet på den dator som exekverar algoritmen, det är snabbare än andra pseudoslumpsekvensgeneratorer , och algoritmen är också lätt att genomföra. [ett]

Nackdelar

Enligt forskning varierar antalet 0:or och 1:or i utdatasekvensen markant, vilket motsäger Golombs postulat . Dessutom, om vi tar ett heltal N och delar upp sekvensen i tuplar av N ord, så för en slumpmässig sekvens måste fördelningen av ettor i dessa tuplar följa binomialfördelningen Bin(N, 1/2). Men det visade sig att detta villkor inte är uppfyllt. Detta beror på det faktum att varje ord endast beror på de två föregående, och därför "utjämnas" inte övervikten av ettor eller nollor av modulo 2-adderaren. [2] $N\leqslant n$

Mersenne Vortex är ett exempel på en GFSR-förbättring

En välkänd modifiering av skiftregistret med generaliserad feedback kallad " Mersenne Vortex ", föreslog av Makoto Matsumoto och Takuji Nishimura 1997. Perioden för denna generator är enorm och är lika med Mersenne-talet . Mersenne-virveln tillhör klassen av spolgeneratorer baserade på skiftregister med generaliserad återkoppling. Dess förenklade diagram visas i figuren. $2^{19937}-1$

Tänk på den vanligaste versionen av denna algoritm - MT19937. Den använder 624 minnesceller, som var och en innehåller ett 32-bitars heltal. I det här fallet skrivs den återkommande regeln för bildandet av en sekvens av utgående ord enligt följande:

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

Det vill säga, vid varje k:te steg tas den mest signifikanta biten av ordet , och 31 bitar från ordet , och sedan sammanfogas de resulterande delarna , följt av multiplicering av resultatet med matrisen $W_{k-623}$ $W_{k-622}$

$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}}$

där = 0x9908B0DF i hexadecimal. $a=(a_{w-1}a_{w-2}...a_{0})$

Efter det läggs resultatet till modulo 2 till ordet som beräknades i det föregående 397:e steget. Sedan flyttas innehållet i alla celler ett steg åt vänster, och resultatet skrivs till den lediga cellen. [2]

Se även

Litteratur

T.G. Lewis, W.H. Payne. Journal of the ACM (JACM) Volym 20 Issue 3. - NY: ACM, juli 1973.
James E Gentle. Generering av slumptal och Monte carlo-metoder. — 2:a upplagan. - NY: Springer, 2003. - XV + 381 sid. - ISBN 0-387-00178-6 .

Anteckningar

↑ 1 2 3 4 5 6 7 8 T. G. Lewis, W. H. Payne. Generalized Feedback Shift Register Pseudoslumptalsalgoritm // J. ACM. — 1973-07-01. - T. 20 , nej. 3 . — S. 456–468 . — ISSN 0004-5411 . - doi : 10.1145/321765.321777 .
↑ 1 2 3 N. F. Kazakova, Ph.D., Yu. V. Shcherbina, Ph.D. PROBLEM MED UTVÄRDERING AV KVALITETEN PÅ ARBETET HOS MODERNA LINJÄRA GENERATORER AV PSEUDORANDOMSEKVENS (rys.) // Collection of Scientific Practices ODATR No 1(2)2013. Arkiverad från originalet den 23 mars 2022.
↑ 1 2 3 4 5 M. Fushimi, S. Tezuka. K-fördelningen av generaliserade återkopplingsskiftregister pseudoslumptal // Kommunikation av ACM. — 1983-07-01. - T. 26 , nej. 7 . — S. 516–523 . — ISSN 0001-0782 . - doi : 10.1145/358150.358159 . Arkiverad från originalet den 16 november 2016.