Doporučujeme














Naše Bannery








Toplist




Náhodné generátory Random()
Napísal Diallix   
Utorok, 05 August 2014 10:40

Generátory náhodných čísel sú v počítačových systémoch riadené časom - hodinami. To zaručuje, že čisla sú generované náhodne, prípadne náhodnosť môže byť reprezentovaná postúpnosťou čisel, ktoré sa nikdy nebudú opakovať.  

Funkcie takéhoto generovania sa nazývajú pseudo-náhodné generátory čísel. Nadstavbou týchto funkcií sú funkcie, ktoré náhodne vyberajú prvky neakej množiny s možnosťou opakovania sa, napríklad, náhodný výber z množiny čísel od 10 - 99.

Pri mikrokontroléroch je však generovanie komplikovanejšie. Počítač, či iné podobné zariadenie obsahuje integrovaný zdroj, prípadne je v sieti zapojené nonstop. Vnútorné obvody sú neustále napájané a príjímajú hodinové impulzy. 
Preto pri náhodnom generovaní na základe času je výsledok vždy iný.

Mikrokontroléry samé o sebe síce obsahujú vnútorné generátory hodinových impulzov a taktiež podporujú externé, ale pri vypnutí MCU sa obsah SRAM zmaže.
Mohlo by byť niekoľko spôsobov implementácie.

Prostredníctvom USB - rozhrania: ak by sme mali kontrolér použitý v zapojení, ktoré by bolo pripojené alebo jeho hlavnou prácou by bola komunikácia so softwarom v počítači, pri každom spustení MCU by software počítača odoslal prostredníctvom USB, ako sériového rozhrania, aktualizovaný hodinový impulz, prípadne čas z ktorého by čítač mcu vychádzal. MCU by tento počiatočný stav spracoval a od neho by spúšťal Random Generátor.

Druhou možnosťou by bol externý generátor hodinového impulzu. MCU by hodinový signál nepretržite čítal a na základe meho by menil jadro Random Generátoru čísel.

Treťou možnosťou by bolo univerzálne riešenie generátora, s počiatočným bodom.
Generátor má nastavené hodnoty - polynómy, na základe ktorých sa generujú impulzy.
Výhodou je, že generovanie je efektívne, nevýhodou, že pri resete či pri každom zapnutí zariadenie, bude generovanie prebiehať rovnako.


Na prvé dve možnosti sa pozrieme inokedy. Skúsime sa zamerať na tretiu možnosť, generovania hodnôt a dostávame sa k pojmu :


LFSR Random Generátor

Ide o Linear Feedback Shift Register Random Generátor. Základom je LFSR - lineárny spätnoväzobný posuvný register. Ide o register, ktorého vstupná hodnota je funkciou predošlého stavu.

Keďže ide o deterministický konečný automat, jeho celková množina všetkých možných stavov je konečná a ostatné stavy sú riešené v ďalšej slučke. Efektívnosť randomizu spočíva v návrhu spätnoväzbovej funkcie. Množina konečných stavov, ktoré sa nebudú opakovať, môže mať tak veľmi dlhý priebeh trvania.

Počiatočnou hodnotou je polynóm. Generovanie novej hodnoty z pôvodného stavu je prevádzané zvyčajne
prostredníctvom XOR.


Návrhov tochto typu generovania je na netu mnoho.
Rozhodol som sa, že upravím stávajúci návrh kódu (Open Source) a integrujem ho do konfiguračého
prostredia config_diall.h

Funkcie:

funkcie
Random();
Randoming(x,y);



Prvá funkcia generuje - vracia náhodnú, číselnú hodnotu.

Druhá funkcia generuje čísla v rozmedzí x --> y:

funkcie
int i = Randoming(0,100);


















 
Joomla ACL by AceACL