Věci se nedějí náhodně. Vždy se dějí cíleně, někdy však pod rouškou pseudonáhodného výběrového mechanismu. Ono se hodí, když se náhoda opakuje stále ve stejném rytmu. Minimálně programátoři to ocení při ladění svých výtvorů.

Takže co budeme řešit. Mějme registr délky N bitů, ve kterém lze zakódovat 2^N různých stavů, interpretovaných čísly 0 až (2^N)-1. A my chceme vygenerovat všechna tato čísla právě jednou, ovšem v náhodném pořadí.

Na konkrétní počítačové platformě si můžeme pomáhat čtením nějakého rychlého hardwarového čítače, registru rozkladu obrazu, stavového registru různých periferních obvodů ale vystavujeme se riziku, že rychlost změn v těchto registrech bude synchronní s během našeho programu a budeme dostávat (v lepším případě) omezený počet hodnot z celého dostupného rozsahu.

A tím se dostáváme i k další vlastnosti generátoru pseudonáhodných čísel. Neměl by v libovolně vybraném úseku zvýhodňovat určitý typ hodnot. Neměl by generovat příliš dlouhé úseky sudých či lichých čísel, čísel větších či menších než 32768, atp. Každou matematickou podmínku, kterou si dovedete u daného čísla představit, by měl náš algoritmus (ne)pravidelně střídat ve stylu splňuje – nesplňuje.

Většinou asi v praxi vystačíme se základním osmibitovým generátorem pseudonáhodné posloupnosti. Ten který uvádím, funguje na bázi LFSR s externí zpětnou vazbou. LFSR je lineární zpětnovazební sériový registr, který nahradíme registrem A u osmibitového generátoru a registrovým párem H:L u šestnáctibitového generátoru. Ta poznámka o externí zpětné vazbě je velmi důležitá. Znamená to, že jednotlivé bity v posuvném registru jsou na sebe navázány přímo a nejsou mezi nimi žádné bloky, generující nějakou funkci. Ta zpětnovazební funkce se generuje „externě“ z jednotlivých bitů a výsledek této funkce se nasouvá v našem případě zprava do posuvného registru na jeho nejnižší pozici. Protože ta zpětnovazební funkce má na vstupu bity (dvoustavové logické hodnoty), a sčítání bitů modulo 2 (tedy s odřezáním všech řádů mimo jednotek) není nic jiného než výpočet parity, transformuje se výpočet zpětnovazební funkce na výpočet parity nad vybranými bity předchozí hodnoty generovaného čísla. Co jsem asi ještě neřekl, že nově vygenerované číslo vznikne ze starého tím, že posunu registr s tímto číslem doleva (násobím jeho hodnotu dvěma) a zprava nasunu bit s hodnotou zpětnovazební funkce. Dost bylo řečí, tady je příklad:

Procedura random8

Pseudonáhodné generátory tohoto typu mají jednu nectnost. Generovaná číselná řada neobsahuje prvek se samými jedničkami. Například osmibitový generátor nevygeneruje číslo 255 (11111111 binárně). Sice můžeme negovat zpětnovazební funkci a pak dostaneme i tento poslední prvek ale zase se nám ztratí prvek nulový. Máme na výběr. V našem příkladu tak stačí zaměnit instrukci JPO za instrukci JPE. Ale i to má řešení. U generátoru, který „neumí“ nulu si na začátku nastavíme explicitně jako první generované číslo právě tuto nulu a při prvním průchodu generátorem podvrhneme „falešnou“ hodnotu zpětnovazební funkce, která už algoritmus navede do správných kolejí a on nám vygeneruje zbylá čísla, například 1..255. Tak jsem to řešil u svého simulátoru EPROM, takže to jde a je to odzkoušené.

Pro případ, že nám je 8 bitů málo, můžeme použít i pseudonáhodný generátor délky 16 bitů:

Procedura random16

Opět platí, že v základní variantě negeneruje prvek 65535 (1111 1111 1111 1111 binárně). Tato šestnáctibitová varianta je v dále uvedeném příkladu rozpracována do dílčích podvariant délky 9 až 15 bitů, protože musíme vždy ořezat nevyužívané bity registru shora.

Následující program obsahuje testovací demo smyčku, která postupně spouští generátory pseudonáhodných čísel délky 8 až 16 bitů. Pro každou generovanou posloupnost se zobrazuje pixelové pole. Z časoprostorové distribuce pixelů si můžete udělat obrázek, jak dalece jsou ty generátory náhodné. Třeba u délky 15 bitů je pěkně vidět zvýrazněné „osy“, generované v úvodní fázi posloupnosti. Ale můžete si zvolit i jiné zpětnovazební funkce, než ty uvedené v příkladu. Zkoušel jsem i jiné a také fungují. Sada použitých generujících polynomů byla tuším někde ze stránek Xilinxu.

Demo se spouštěním několika generátorů pseudonáhodných posloupností čísel

Demo ve formě souboru virtuální MGF pásky pro emulátor PMD 85 od RM Teamu