Generátor (pseudo)náhodných čísel

Využijete nejen v hrách, ale i v dalších aplikacích.

Náhoda

Elektronické obvody jsou, pokud jsou navrženy správně, deterministické. Nebo by měly být. To znamená, že pokud je v čase Tn na vstupech určitá kombinace dat a zároveň známe vnitřní stav obvodu (což zde, na rozdíl od světa elementárních částic, dokážeme), tak můžeme přesně říct, jaký stav bude v čase Tn+1. Díky tomu elektronické obvody fungují tak, jak mají – pokud jsou tedy správně navržené, správně zapojené, správně provozované, správně odstíněné od vnějších vlivů…

Přesto ale někdy potřebujeme něco „znáhodnit“. V té úplně nejjednodušší variantě je to třeba vytvoření elektronické hrací kostky. A tady narazíme na to, že to není úplně taková legrace. Pokud je totiž elektronické zapojení deterministické, lze vždycky zcela přesně říct, jaký bude následující stav, a tedy i jaké číslo „padne“.

Představme si právě tu hrací kostku. Nejjednodušší implementace je pomocí čítače, který čítá hodnoty 1 až 6 (resp. 0 až 5) stále dokola velkou rychlostí, a ve chvíli, kdy hráč zmáčkne tlačítko, tak se čítání zastaví a zobrazí se aktuální stav.

Vidíme, že je tu nějaký generátor sekvence, a pak vnější „znáhodnění“. Kdybychom zůstali jen u toho generátoru a zobrazovali hodnoty v určitých pevně daných intervalech (např. 10 sekund), tak bychom zjistili, že padají stále stejné hodnoty ve stále stejném pořadí. Co s tím?

Jedna možnost je použít opravdový generátor náhodných čísel, což je většinou nějaké hardwarové zařízení, které generuje náhodný signál na základě nějakého fyzikálního jevu. Například rozpad radioaktivní látky, měření šumu nebo vstupu od uživatele. Rozpad radioaktivních látek nebývá pro elektroamatéra naprosto běžně dostupný. S šumem je to lepší. Principiálně vezmeme nějakou součástku, která generuje šum, například polovodičovou diodu, výstupní šum řádně zesílíme, vzorkujeme, převádíme do digitální podoby a podle nejméně významného bitu určujeme aktuální hodnotu náhodného signálu. Nevýhoda je, že šum je ovlivnitelný zvnějšku, například se nám může v obvodu indukovat nějaký radiový signál. Na druhou stranu můžeme takovéto ovlivnění považovat za „chaos zvyšující faktor…“

Pokud to zapojení umožňuje, je dobré použít vstup od uživatele, například stisk tlačítek nebo pohyby myši, a využít toho, že intervaly stisknutí jsou řádově nižší než rychlost běhu čítače a přicházejí, z hlediska systému, opravdu v náhodné okamžiky. Problém nastane, když potřebujeme náhodná čísla „neustále“, zatímco vstup od uživatele přijde z hlediska systému „za extrémně dlouhou dobu“.

Využívá se techniky, kdy se sice čítají impulsy, ale hodnoty nejdou po sobě v očekávaném pořadí 1, 2, 3, 4, 5, 6…, ale např. u tříbitového čítače jako 1, 4, 6, 7, 3, 5, 2 (hodnota 0 se nevyskytuje). Takovou posloupnost odhalíme hladce, ale představte si, že použijeme čítač šestnáctibitový, který má na výstupu čísla 1 až 65535 v pseudonáhodném pořadí. I tady se posloupnost objeví znovu, ale později. Ale nic nám nebrání použít čítače vícebitového. 32 bitů… 60 bitů… 128 bitů… Klidně i 168 bitů. V takovém případě se posloupnost opakuje po cca 1050 hodnotách. Pokud použijeme náš 50MHz hodinový signál, objeví se stejná posloupnost po 7,4×1042 sekundách, cože je 2.37×1035 let. Chcete li to převést na biliony, je to 2.37×1023 bilionů let. Vesmír má zatím za sebou 14 bilionů let… To by asi šlo. Teď jen správně nastavit tu hodnotu, od které to spustíme. Ideálně nějakým generátorem náhodných čísel… 🙂

Ne, dělám si legraci: do obvodu můžeme zařadit „znáhodňovač“, který v závislosti na nějakém vnějším impulsu změní hodnotu. S následující technikou je to jednodušší než si myslíte.

LFSR

Posuvným registrům jsme se ještě nevěnovali nijak důkladně. Přitom jsme je už použili, stačí vzpomenout na serializaci a deserializaci dat. Posuvný registr si představme jako sadu registrů, zapojených za sebou tak, že s každým pulsem hodin se informace z registru N posune do registru N+1. Při převodu paralelních dat na sériová nahrajeme do všech registrů naráz požadovaná data, a pak na výstupu z posledního registru čteme bit po bitu. Při opačném převodu posíláme sériová data na vstup posuvného registru, s každým hodinovým pulsem se posunou o jednu pozici, a jakmile máme načtený kompletní bajt, přečteme si ho z jednotlivých registrů.

Kruhový posuvný registr vznikne tím, že výstup zavedeme zpátky na vstup. Speciálním případem kruhového registru je kruhový posuvný registr s lineární zpětnou vazbou, neboli LFSR (Linear feedback shift register).

Pokud například na předchozím obrázku zavedeme negovaný výstup Q4 na vstup „Data In“, získáme čtyřbitový  Johnsonův čítač, který prochází stavy (desítkově): 0, 1, 3, 7, 15, 14, 12, 8.

Cyklus Q4 Q3 Q2 Q1
0 0 0 0 0
1 0 0 0 1
2 0 0 1 1
3 0 1 1 1
4 1 1 1 1
5 1 1 1 0
6 1 1 0 0
7 1 0 0 0

Kruhové posuvné registry (též „kruhové čítače“) můžeme zapojit i složitěji – vstup budíme nikoli samotným výstupem, ale signálem, složeným z více bitů. Představme si, že u výše uvedeného čítače přivedeme na vstup Data In signál, který vznikne jako Q1 xor Q4.

Cyklus Q4 Q3 Q2 Q1
0 0 0 0 1
1 0 0 1 1
2 0 1 1 1
3 1 1 1 1
4 1 1 1 0
5 1 1 0 1
6 1 0 1 0
7 0 1 0 1
8 1 0 1 1
9 0 1 1 0
10 1 1 0 0
11 1 0 0 1
12 0 0 1 0
13 0 1 0 0
14 1 0 0 0
15 0 0 0 1

 

Dekadicky zapsané stavy jsou: 1, 3, 7, 15, 14, 13, 10, 5, 11, 6, 12, 9, 2, 4, 8 – vidíme, že takový obvod projde 15 stavy z 16 možných (stav 0000 je konstantní, nijak se nemění). Za cenu určitých úprav zapojení můžeme cyklus rozšířit o poslední stav. Důležité je, že čísla tvoří sice periodu, ale v jejím rámci jsou dostatečně promíchána.

U čtyřbitového čítače můžeme zvolit s dvouvstupovým XOR hradlem šest kombinací zpětné vazby (1,2);(1,3);(1,4);(2,3);(2,4);(3,4). Některé z nich vedou k velmi krátkým cyklům (třeba 1,2), jiné k nejdelším možným (1,4). Sympatické na LFSR je, že k dosažení nejdelšího možného cyklu (2N-1 stavů) vystačíme s dvou-, či čtyřvstupovými hradly. I LFSR o délce 168 bitů postavíme jednoduše, zavedením zpětné vazby signálem (Q151 xor Q153 xor Q166 xor Q168 – číslujeme od 1). Vhodné koeficienty naleznete např. v tomto obrázku nebo v tomto výpisu kódu – všimněte si, že součástí zpětnovazebního výrazu je vždy nejvyšší bit (pokud by nebyl, degradovali bychom LFSR na menší bitovou šířku).

Pro LFSR existuje poměrně složitý matematický aparát, který dokazuje, že pro libovolnou délku existuje alespoň jedna kombinace vstupů („padů“), která dává nejdelší možný cyklus, a jaká to je, ale její popis je mimo rámec článku. V praxi postačí vědět, že tomu tak je, a kde najdu vhodné kombinace čísel. Pro délky 20-168 je najdete zde, pro čítače dlouhé 2 až 786 bitů zase zde. BTW, pro čítač o délce 4096 bitů použijte pady 4069, 4081, 4095 a 4096.

Pokud budeme z LFSR odebírat jeden bit (např. nejvyšší), získáme na něm pseudonáhodnou posloupnost 1 a 0, u dlouhých registrů s periodou dostatečně dlouhou na to, abychom je prohlásili za náhodné. A do zpětné vazby můžeme přimíchat (přiXORovat) právě to vnější „znáhodnění“. Například změnit bit pokaždé, když uživatel zmáčkne tlačítko, nebo když přijde informace po sériové lince – zkrátka cokoli, co se vyskytuje asynchronně a v náhodných intervalech. Změnou bitu posuneme pozici v posloupnosti na jiné místo (jen musíme dávat pozor na kombinaci „samé nuly“, která by běh generátoru zastavila).

Způsob, jaký jsme si popsali, se nazývá „many-to-one“, neboli „mnoho do jednoho“ – několik výstupů se XORuje do jednoho vstupu. Někdy nemusí být toto uspořádání vhodné, např. v případě velmi rychlých obvodů, kde se může projevit zpoždění při víceúrovňovém XORování. V takovém případě můžeme architekturu „many-to-one“ nahradit architekturou „one-to-many“, kde se výstup (nejvyšší bit) přimíchává do několika míst v řetězu klopných obvodů. Místa, kde má dojít ke XORování, jsou stejná jako u architektury many-to-one, sekvence zůstane stejně dlouhá, ale posloupnost hodnot bude jiná. Více viz LFSR Tutorial.

Vidíme posuvný registr o šířce 31 bitů (čísluju nikoli od nuly, ale od jedničky). Zápis je dostatečně obecný, takže při úpravě na jinou šířku registru stačí změnit pouze zpětnovazební funkci. Pro zajímavost ještě architektura one-to-many:

U osmibitového registru je kombinace vstupů s nejdelším cyklem např. (2, 3, 4, 8) – a vidíte, že osmý výstup se XORuje s výstupem na pozicích 2, 3 a 4. Jiná sestava pinů je např. (4, 5, 6, 8).

Pro zajímavost: LFSR (zvané též „polynomial counters“) se používají v obvodech pro generování zvuku (SID, POKEY a pod.) jako šumové generátory.

Pokud do zpětné vazby u architektury one-to-many přimícháme (XOR) serializovaná data, získáme tak nástroj pro výpočet kontrolního součtu CRC (Cyclic Redundancy Check).