V\u011bci se ned\u011bj\u00ed n\u00e1hodn\u011b. V\u017edy se d\u011bj\u00ed c\u00edlen\u011b, n\u011bkdy v\u0161ak\u00a0pod rou\u0161kou pseudon\u00e1hodn\u00e9ho v\u00fdb\u011brov\u00e9ho mechanismu. Ono se hod\u00ed, kdy\u017e se n\u00e1hoda opakuje st\u00e1le ve stejn\u00e9m rytmu. Minim\u00e1ln\u011b program\u00e1to\u0159i to ocen\u00ed p\u0159i lad\u011bn\u00ed sv\u00fdch v\u00fdtvor\u016f.<\/p>\n
Tak\u017ee co budeme \u0159e\u0161it. M\u011bjme registr d\u00e9lky N bit\u016f, ve kter\u00e9m lze zak\u00f3dovat 2^N r\u016fzn\u00fdch stav\u016f, interpretovan\u00fdch \u010d\u00edsly 0 a\u017e (2^N)-1. A my chceme vygenerovat v\u0161echna tato \u010d\u00edsla pr\u00e1v\u011b jednou, ov\u0161em v n\u00e1hodn\u00e9m po\u0159ad\u00ed.<\/p>\n
Na konkr\u00e9tn\u00ed po\u010d\u00edta\u010dov\u00e9 platform\u011b si m\u016f\u017eeme pom\u00e1hat \u010dten\u00edm n\u011bjak\u00e9ho rychl\u00e9ho hardwarov\u00e9ho \u010d\u00edta\u010de, registru rozkladu obrazu, stavov\u00e9ho registru r\u016fzn\u00fdch perifern\u00edch obvod\u016f ale vystavujeme se riziku, \u017ee rychlost zm\u011bn v t\u011bchto registrech bude synchronn\u00ed s b\u011bhem na\u0161eho programu a budeme dost\u00e1vat (v lep\u0161\u00edm p\u0159\u00edpad\u011b) omezen\u00fd po\u010det hodnot z cel\u00e9ho dostupn\u00e9ho rozsahu.<\/p>\n
A t\u00edm se dost\u00e1v\u00e1me i k dal\u0161\u00ed vlastnosti gener\u00e1toru pseudon\u00e1hodn\u00fdch \u010d\u00edsel. Nem\u011bl by v libovoln\u011b vybran\u00e9m \u00faseku zv\u00fdhod\u0148ovat ur\u010dit\u00fd typ hodnot. Nem\u011bl by generovat p\u0159\u00edli\u0161 dlouh\u00e9 \u00faseky sud\u00fdch \u010di lich\u00fdch \u010d\u00edsel, \u010d\u00edsel v\u011bt\u0161\u00edch \u010di men\u0161\u00edch ne\u017e 32768, atp. Ka\u017edou matematickou podm\u00ednku, kterou si dovedete u dan\u00e9ho\u00a0\u010d\u00edsla p\u0159edstavit, by m\u011bl n\u00e1\u0161 algoritmus (ne<\/strong>)pravideln\u011b st\u0159\u00eddat ve stylu spl\u0148uje – nespl\u0148uje.<\/p>\n V\u011bt\u0161inou asi v praxi vysta\u010d\u00edme se z\u00e1kladn\u00edm osmibitov\u00fdm gener\u00e1torem pseudon\u00e1hodn\u00e9 posloupnosti. Ten kter\u00fd uv\u00e1d\u00edm, funguje na b\u00e1zi LFSR s extern\u00ed zp\u011btnou vazbou. LFSR je line\u00e1rn\u00ed zp\u011btnovazebn\u00ed s\u00e9riov\u00fd registr, kter\u00fd nahrad\u00edme registrem A u osmibitov\u00e9ho gener\u00e1toru a registrov\u00fdm p\u00e1rem H:L u \u0161estn\u00e1ctibitov\u00e9ho gener\u00e1toru. Ta pozn\u00e1mka o extern\u00ed zp\u011btn\u00e9 vazb\u011b je velmi d\u016fle\u017eit\u00e1. Znamen\u00e1 to, \u017ee jednotliv\u00e9 bity v posuvn\u00e9m registru jsou na sebe nav\u00e1z\u00e1ny p\u0159\u00edmo a nejsou mezi nimi \u017e\u00e1dn\u00e9 bloky, generuj\u00edc\u00ed n\u011bjakou funkci. Ta zp\u011btnovazebn\u00ed funkce se generuje „extern\u011b“ z jednotliv\u00fdch bit\u016f a v\u00fdsledek t\u00e9to funkce se nasouv\u00e1 v na\u0161em p\u0159\u00edpad\u011b zprava do posuvn\u00e9ho registru na jeho nejni\u017e\u0161\u00ed pozici. Proto\u017ee ta zp\u011btnovazebn\u00ed funkce m\u00e1 na vstupu bity (dvoustavov\u00e9 logick\u00e9 hodnoty), a s\u010d\u00edt\u00e1n\u00ed bit\u016f modulo 2 (tedy s od\u0159ez\u00e1n\u00edm v\u0161ech \u0159\u00e1d\u016f mimo jednotek) nen\u00ed nic jin\u00e9ho ne\u017e v\u00fdpo\u010det parity, transformuje se v\u00fdpo\u010det zp\u011btnovazebn\u00ed funkce na v\u00fdpo\u010det parity nad vybran\u00fdmi bity p\u0159edchoz\u00ed hodnoty generovan\u00e9ho \u010d\u00edsla. Co jsem asi je\u0161t\u011b ne\u0159ekl, \u017ee nov\u011b vygenerovan\u00e9 \u010d\u00edslo vznikne ze star\u00e9ho t\u00edm, \u017ee posunu registr s t\u00edmto \u010d\u00edslem doleva (n\u00e1sob\u00edm jeho hodnotu dv\u011bma) a zprava nasunu bit s hodnotou zp\u011btnovazebn\u00ed funkce. Dost bylo \u0159e\u010d\u00ed, tady je p\u0159\u00edklad:<\/p>\n Procedura random8<\/a><\/p>\n Pseudon\u00e1hodn\u00e9 gener\u00e1tory tohoto typu maj\u00ed jednu nectnost. Generovan\u00e1 \u010d\u00edseln\u00e1 \u0159ada neobsahuje prvek se sam\u00fdmi jedni\u010dkami. Nap\u0159\u00edklad osmibitov\u00fd gener\u00e1tor nevygeneruje \u010d\u00edslo 255 (11111111 bin\u00e1rn\u011b). Sice m\u016f\u017eeme negovat zp\u011btnovazebn\u00ed funkci a pak dostaneme i tento posledn\u00ed prvek ale zase se n\u00e1m ztrat\u00ed prvek nulov\u00fd. M\u00e1me na v\u00fdb\u011br. V na\u0161em p\u0159\u00edkladu tak sta\u010d\u00ed zam\u011bnit instrukci JPO za instrukci JPE. Ale i to m\u00e1 \u0159e\u0161en\u00ed. U gener\u00e1toru, kter\u00fd „neum\u00ed“ nulu si na za\u010d\u00e1tku\u00a0nastav\u00edme explicitn\u011b jako prvn\u00ed generovan\u00e9 \u010d\u00edslo pr\u00e1v\u011b tuto nulu a p\u0159i prvn\u00edm pr\u016fchodu gener\u00e1torem podvrhneme „fale\u0161nou“ hodnotu zp\u011btnovazebn\u00ed funkce, kter\u00e1 u\u017e algoritmus navede do spr\u00e1vn\u00fdch kolej\u00ed a on n\u00e1m vygeneruje zbyl\u00e1 \u010d\u00edsla, nap\u0159\u00edklad 1..255. Tak jsem to \u0159e\u0161il u sv\u00e9ho simul\u00e1toru EPROM, tak\u017ee to jde a je to odzkou\u0161en\u00e9.<\/p>\n Pro p\u0159\u00edpad, \u017ee n\u00e1m je 8 bit\u016f m\u00e1lo, m\u016f\u017eeme pou\u017e\u00edt i pseudon\u00e1hodn\u00fd gener\u00e1tor d\u00e9lky 16 bit\u016f:<\/p>\n Procedura random16<\/a><\/p>\n Op\u011bt plat\u00ed, \u017ee v z\u00e1kladn\u00ed variant\u011b negeneruje prvek 65535 (1111 1111 1111 1111 bin\u00e1rn\u011b). Tato \u0161estn\u00e1ctibitov\u00e1 varianta je v d\u00e1le uveden\u00e9m p\u0159\u00edkladu rozpracov\u00e1na do d\u00edl\u010d\u00edch podvariant d\u00e9lky 9 a\u017e 15 bit\u016f, proto\u017ee mus\u00edme v\u017edy o\u0159ezat nevyu\u017e\u00edvan\u00e9 bity registru shora.<\/p>\n N\u00e1sleduj\u00edc\u00ed program obsahuje testovac\u00ed demo smy\u010dku, kter\u00e1 postupn\u011b spou\u0161t\u00ed gener\u00e1tory pseudon\u00e1hodn\u00fdch \u010d\u00edsel d\u00e9lky 8 a\u017e 16 bit\u016f. Pro ka\u017edou generovanou posloupnost se zobrazuje pixelov\u00e9 pole. Z \u010dasoprostorov\u00e9 distribuce pixel\u016f si m\u016f\u017eete ud\u011blat obr\u00e1zek, jak dalece jsou ty gener\u00e1tory n\u00e1hodn\u00e9. T\u0159eba u d\u00e9lky 15 bit\u016f je p\u011bkn\u011b vid\u011bt zv\u00fdrazn\u011bn\u00e9 „osy“, generovan\u00e9 v \u00favodn\u00ed f\u00e1zi posloupnosti. Ale m\u016f\u017eete si zvolit i jin\u00e9 zp\u011btnovazebn\u00ed funkce, ne\u017e ty uveden\u00e9 v p\u0159\u00edkladu. Zkou\u0161el jsem i jin\u00e9 a tak\u00e9 funguj\u00ed. Sada pou\u017eit\u00fdch generuj\u00edc\u00edch polynom\u016f byla tu\u0161\u00edm n\u011bkde ze str\u00e1nek Xilinxu.<\/p>\n