Implementarea FPGA a 4 generatoare de numere aleatoare automate învecinate.

 



1.Introducere

Încă de la începuturile erei calculatoarelor, numerele aleatoare au jucat un rol important în domenii ca simulările Monte Carlo, jocurile pe calculator, testele cipurilor VLSI şi în metodele de calcul probabilistic cum ar fi algoritmii genetici şi reţelele neurale. Deoarece calculatoarele au devenit mai puternice şi simulările mai complicate, cererea de generatoare de numere aleatoare (RNG-uri) a crescut. Totuşi, nu există un singur test ce poate determina calitatea unui RNG, pentru aceasta sunt necesare o serie de teste diferite. Vom folosi seria de teste acreditată, a lui George Marsaglia numită DIEHARD.

 

Constructorii de echipamente hardware digitale s-au bazat mult timp pe metodele de mutare a regiştrilor, pentru generarea numerelor aleatoare. În 1986, Wolfram a sugerat ca automatul celular (CA) care se baza pe calcule pe biţi şi interconectare locală, să fie folosit pentru o implementare eficientă a generatoarelor de numere aleatorii datorită simplitudinii lor şi designului regulat.

 

Odată cu apariţia designului VLSI, a devenit rentabilă încorporarea unei parţi a sistemului de testare a cipului chiar pe cip. Iniţial, registrele liniare au fost folosite pentru a implementa partea care generează modelul aleator al testului. Hortensius a demonstrat că automatul celular neînrudit compus din două funcţii lineare poate genera numere aleatorii superioare celor generate de regiştrii liniari sau celor generate de automatul înrudit neliniar propus de Wolfram.

 

FPGA-urile fac posibilă construirea unor întregi sisteme pe un singur cip FPGA.Celula de bază a multor arhitecturi FPGA este tabela reprogramabilă electric (LUT) şi registrul pe un singur bit asociat pentru păstrarea datelor. Deschiderea tipică a unei tabele reprogramabile este de 4 şi duce la o tabelă de adevăr pe 16 rânduri, în timp ce un CA cu o rază de 4 (de exemplu cu o celulă la stânga şi una la dreapta centrului) are în vecinatate 3, ceeea ce necesită o tabelă de adevăr care iroseşte jumătate din capacitatea tabelei reprogramabile. O reţea bidimensională de automate celulare sau alternativ, o retea bidimensională cu o rază de 2, necesită o tabelă de adevar de 32 de biţi implicând două tabele reprogramabile pentru o poziţie a automatului celular.

 

Scopul nostru a fost acela de a cerceta implementarea generatoarele de numere aleatorii ce au o intrare pe 4 căi (de exemplu o vecinătate de 4) automate celulare cu conexiuni asimetrice şi non-locale. Folosirea unei vecinătăţi de 4 permite unui singur automat celular să fie implementat eficient într-o tabelă programabilă cu patru intrări, acest lucru permiţând ca generatoarele de calitate sî fie implementate în PFGA-uri drept componente de sistem. în această lucrare a fost descoperit un număr de automate celulare care au trecut setul de teste DIEHARD.

 

În capitolul următor, vom descrie câteva lucrări anterioare în domeniul automatelor celulare. Mai apoi în capitolul 3 vom face o prezentare a convenţiilor automatelor celulare. Capitolul 4 va descrie procedurile experimentale iar partea a 5-a va prezenta rezultatele în mod detaliat.

 

 

2. Lucrări anterioare

În 1986 Wolfram a descris generarea numerelor aleatoare folosind un singur automat celular cu o vecinătate de 3. Lucrarea sa se baza pe proprietăţile CA30 (denumit asa după valoarea zecimală a tabelei de adevăr cu 8 rânduri). Au fost efectuate 7 teste statistice iar CA30 s-a dovedit a fi superior regiştrilor liniari în cazul generării unei secvenţe de numere aleatoare. Wolfram a aratat că CA30 poate avea implementări hardware foarte eficiente. El a aratat ca pentru anumite aplicaţii critice, permiterea uror stadii aditionale între citiri ar îmbunătăţi calitatea statistică a secvenţelor.

 

În 1989, Hortensius a descris folosirea CA30 pentru generarea numerelor aleatorii într-o implementare VLSI într-un computer bidimensional Ising. Ceva timp mai târziu, în acelaşi an, Hortensius a descris aplicarea RNG-urilor bazate pe automate celulare la testele din interiorul cipurilor VLSI. Folosind o combinaţie de CA90 (XOR sau vecini stânga-dreapta) şi CA 150 (XOR sau stânga, dreapta şi celule centrale) în locuri diferite, s-au obţinut rezultate superioare CA30-ului. Acest lucru indică faptul că atât distanţierea în timp cât şi distanţierea ân spaţiu ar imbunătăţi calitatea statistică a numerelor aleatorii. Mai târziu în 1991 respectiv 1994 Taslides şi Nandi au lucarat în continuare cu CA90/CA150 automatul celular hibrid, concentrându-se asupra generării şirurilor de numere aleatorii pentru testele din interiorul cipului.

 

În 1994 Chowdhury a descris o clasă de automate celulare bidimensionale, cu o învecinare de 5 (N=5) alcatuite din celule liniare (functia XOR). Scopul a fost generarea numerelor aleatoare pentru testele din interiorul VLSI. S-a descoperit că în timp ce calitatea numerelor aleatorii era mai bună pentru automatul celular 2-d, marja de eroare nu era întotdeauna mai bună.

 

Deoarece numărul automatului celular hibrid (tabele de adevăr diferite pentru fiecare poziţie a celulei) este foarte mare (256n pentru o vecinatate de 3 cu interconectări uniforme unde n este numărul de celule), Sipper şi Tomassini în 1996 au descris procesul evoluării tabelelor de adevăr “in situ” (un proces co-evolutiv). Lungimea automatului celular era 50 şi 150 de celule cu o calitate a numerelor aleatorii generate comparabilă cu cea a automatelor celulare deja existente bazate pe RNG-uri.

 

În 1999, Tomassini a propus folosirea testelor DIEHARD ale lui Marsaglia pentru a oferi o metodă standardizată de a compara calitatea numerelor aleatorii generate de automatele celulare bazate pe RNG-uri. Folosind seria de teste DIEHARD au arătat că lucrările lor anterioare au căzut 5 din cele 18 teste. Cu toate acestea folosind o spaţiere temporară de 2 (de exemplu citirea datelor în cicluri i, i+3, i+6, …) RNG-ul uni-dimensional a trecut toate testele.

 

În 2000 Tomassini a folosit din nou programarea celulară pentru a dezvolta un automat celular bi-dimensional 8 x 8 bazat pe RNG cu o vecinătate de 5 la care specificaţiile pentru celule indicau o funcţionalitate XOR sau XNOR. Cu toate că valorile p ale testelor DIEHARD nu au fost publicate, acestea indicau că 14 teste au fost trecute fară a apela la distanţiere în spaţiu sau timp. Testele au descris de asemenea generarea unei matrici 8 x 8 folosind aceleaţi reguli pe 6 biţi ca şi RNG-ul cu restricţia că măcar 5 din 6 biţi să fie 1. Acest lucru a indicat ca 4 teste adiţionale DIEHARD au fost trecute. Totuşi nici valorile p nici configuraţia exactă nu a fost publicată.



3.Automatele celulare

Automatele celulare pot fi considerate drept sisteme dinamice, discrete în timp şi spaţiu. În mod curent ele sunt implementate drept o matrice de celule cu funcţionalitate similară alcatuind o structură regulată de o anumită dimensiune. Cel mai des aceste structuri sunt fie şiruri/inele uni-dimensionale sau suprafeţe plane sau curbate bi-dimensionale. Şirurile sau formele plane rezultă din condiţii ce limitează marginile, iar inelele sau formele curbate rezultă din condiţii de limita periodice. Pentru automatele celulare cu două stadii cu o vecinătate de N sunt implementări posibile. Automatele celulare au luat naştere în urma unei conversaţii dintre Stanislaw Ulam şi John von Neumann în anii 1940. Von Neumann a folosit termenul de automat celulatr în lucrările sale despre autoreproducerea automată. Lucrările sale continua şi în prezent.




Fig.1

(a) Funcţionarea celulelor rezultă din tabela de adevar LUT

(b) Semnificaţia celulelor: fiecare celulă conţine o tabelă cu 4 intrări care defineşte funcţionarea celulei şi un bit care păstrează starea celulei.

(c) Notaţia rezultă direct din valorile zecimale ale tabelei de adevăr pe 16 biţi a funcţiei. Zerourle de la început au fost adăugate pentru diferenţiere.

(d) Legăturile către celula i sunt exprimate ca un set de abateri de la valorile lui i.

 
 












Funcţionarea unei celule CA poate fi descrisă ca tabela de adevăr din figura 1(a). După cum este arătat în figura 1(b), fiecărei celule îi este asociat implicit un registru de 1 bit. De vreme ce folosim tabele cu 4 intrări (ce implică o vecinătate de 4) la baza experimentelor, există 16 condiţii posibile la care o celulă trebuie sa raspundă. Numărul de răspunsuri unice poate fi considerat un numar binar pe 16 biţi. Wolfram a introdus o notaţie ce include acest numar care denumeşte în mod unic o celulă cu un nume ce descrie funcţionalitatea celulei după cum se vede în figura 1(c). De vreme ce dorim să extindem zona conectivităţii în afara vacinătăţii locale numele funcţional nu mai descrie adecvat automatul celular. După cum se observă în figura 1(d), am introdus o notaţie care indica în funcţie de celula i cat de departate sunt celulele interconectate.

 

Vom folosi figura 2 pentru a ilustra efectul condiţiilor de mărginire periodică în cazul reţelelor de 1, 2 şi 3 dimensiuni. Toate reţelele din studiul nostru contin 64 de celule care permit formarea unor reţele de 64 celule liniare, 8 x 8 plane, sau 4 x 4 x 4 retele cubice.

 

Figura 2(a) arată o reţea uni-dimensională în formă de inele cu o conectivitate relativă de

{-1,0,2,3} din perspectiva celulei 0. Datorită condiţiilor mărginirii periodice celulele 0 şi 63 sunt adiacente astfel încat o modificare unitară în direcţia negativă de la celula 0 va ajunge la celula 63.

 

Figura 2(b) ilustrează o reţea bi-dimensională cu condiţiile mărginirii periodice care transformă un plan într-o suprafaţă curbată la care fiecare rând şi fiecare coloană formează un inel. Vom folosi notaţiile compasului n, s, e, v pentru a indica deplasarea relativă pe coloane şi rânduri relative la centrul celulei c. Mai mulţi paşi într-o anumită direcţie vor fi indicaţi de un număr ce precede acea direcţie. Exemplul ilustrează conectivitatea implicată de {2n2v,c,ne,s} în funcţie de centrul celulei 7.

Fig.2

(a) Conexiuni periodice între reţele 1-d dintr-un inel. În acest exemplu, interconectarea reţelelor este definită de {-1,0,1,2} si ilustrată pentru celula 0

(b) conexiuni periodice pe reţeaua 2-d formează o suprafaţă curbată. Pentru reţeaua 2-d deplasările relative sunt indicate de n,s,e,v c fiind celula principală.

(c) Conexiuni periodice pentru reţeaua 3-d. Deplasările unitare pe axa z sunt notate cu u şi d după cum se poate observa în exemplu.

 
Celula 7 este atât la sfârşitul unei coloane cât şi al unui rând ceea ce o face un caz interesant de studiat. Considerând deplasarea 2n2v de la celula 7: mergând înspre nord doi paşi vom ajunge la celula 55, apoi înspre vest doi paşi la celula 53. C-ul din lista relativă implică o conexiune proprie datorită numărului 7. Deplasarea se termină la celula 56 mai întai mergând spre nord ajungând la celula 63, apoi spre est la celula 56. La sud de celula 7 este celula 15.











 

 



Aplicând condiţii de mărginire periodică structurii cubice, ca în figura 2(c) am creat o reţea care este compusă din 12 suprafeţe curbate care se intersectează. Acest lucru rezultă din faptul că fiecare plan devine o suprafaţă curbată ca în exemplul precedent şi de vreme ce acum sunt 3 axe, fiecare cu 4 planuri, numărul total de suprafeţe plane este de 12. Deplasările relative sus şi jos în lungul axei z sunt indicate de u şi d după cum ni se arată în exemplu.

 

 

4. Metodologie

 

Pentru o topologie de conectare dată, în locul testării tuturor candidaţilor CA folodind testele DIEHARD vom efectua un test al entropiei. Cei mai buni candidaţi ai acestui test au fost supuşi testelor DIEHARD. În urmatoarele două subcapitole vom descrie automatele celulare cu o entropie ridicată şi vom sublinia pe scurt rezultatele testului DIEHARD.

Fig.3

Entropiile a 1000 de automate celulare cu conectivitate

{-7,0,11,17}. Cele 167 automate celulare care au trecut testele DIEHARD sunt marcate cu punct. Frecvenţa de distribuţie este aratată în partea de jos a imaginii.

 
 









Găsirea candidaţilor CA pentru testarea RNG

 

Deoarece problema impune o vecinătate de 4 (datorită intrării de 4 a tabelei majorităţii FPGA-urilor) sunt posibile doar 216 CA pentru o topologie a conexiunilor dată. Acestea pot fi studiate pentru găsirea candidaţilor cu o entropie ridicată. Calculul entropiei pe 16 biţi S16 se face după următoarea sumă:

 



unde valoarea binară pe 16 biţi a lui i reprezintă subsecvenţa ce este testată iar pi este probabilitatea apariţiei la ieşirea RNG-ului. Pentru calcularea entropiei pe biţi, log2 din 0 este definit ca 0. S16 are o valoare maximă de 16 (indicând entropia maximă) care este obţinută atunci când toate secvenţele de 16 biţi de la 0 la 1 vor avea probabilitate egală.

 

Pentru o topologie a interconectivităţii dată, candidaţii cu cea mai mare entropie au fost căutaţi incepând de la CA00000, furnizând un stadiu iniţial ce constă într-un singur 1 în clula 0 cu toate celelalte celule setate la 0. CA-ul este iniţializat către stadiul cu o entropie ridicată avansând 80 de cicli (de exemplu lungimea sa plus 16 cicli pentru a umple regiştrii binari seriali folosiţi ca parte pentru calculul entropiei).

 

Pentru un stadiu al CA dat, subsecvenţele pe 16 biţi sunt căutate din perspectiva tuturor celor 64 de biţi din CA.CA-ul poate fi vizualizat drept un inel, iar primul test include biţii 0-15, al doilea biţii 1-16, iar al 64-lea include biţii 63-14. Apoi toţi regiştrii pe 16 biţi conectaţi la fiecare din cei 61 de biţi sunt verificaţi. Acest lucru implică 128 teste pentru fiecare stadiu al CA.

 

Stadiul CA este verificat apoi pentru un total de 213 cicli înainte de a trece la urmatoarea tabelă de adevăr a CA. Pentru aceţti paramentri valoarea de aşteptat (valoarea unui RNG bun) pentru oricare din cele 216 subsecvenţe este 16. Căutarea este grabită în mod considerabil prin respingerea oricărui candidat al cărui sub secvenţă depaşeşte de 4 ori valoarea presupusă.

 

După ce au fost testate toate tabelele de adevăr Ca-urile cu entropia cea mai mare sunt testate cu setul de teste aleatorii DIEHARD. Figura 3 aratî distribuţia entropiei pe 16 biţi pentru cele mai bune 1000 CA-uri cu conectivitatea {-7, 0, 11, 17}. Dintre aceste 1000 de CA-uri 167 au trecut întreaga serie de teste DIEHARD (marcate cu puncte îngroşate).


Testarea RNG-urilor

 

Setul de teste DIEHARD oferă o modalitate de evaluare a şirurilor de numere aleatorii şi poate fi descarcat de pe siteul de Internet al lui Marsaglia.

 

Datele pentru fiecare testare DIEHARD au fost culese în felul următor. CA-ul ce a fost testat a fost iniţializat la început la un stadiu înalt al entropiei. Apoi colectarea datelor a început la ciclul 65 şi a continuat pentru 3 milioane de cicli colectând în total 3 milioane de cuvinte pe 332 de biţi compuse din biţi pari şi 3 milioane de cuvinte pe 32 de biţi alcatuite din biţi impari. Ambele seturi de date au fost nevoite să treacă setul de teste DIEHARD, pentru a declara că CA-ul a trecut testul.

 

Sopul acestei lucrări nu este acela de a explica în detaliu fiecare test DIEHARD. Pentru fiecare test există un rezumat al testului care explică detaliile statistice. Pentru a explica fiecare test il vom cita pe Marsaglia direct din textul care apare la începutul fiecarui raport la fiecare test DIEHARD.

 

NOTĂ: Majoritatea testelor DIEHARD returnează o valoare p care trebuie să fie uniformă în intervalul [0,1) dacă fişierul de intare conţine biţi independenţi aleatorii. Aeste valori p sunt obţinute din P=F(x), unde F este distribuţia presupusă a variabilei x. Însa F este o aproximare asimptotică. De aceea nu trebuie sa ne surprindă valorile ocazionale ale lui p aproape de 0 sau 1, cum ar fi 0,0012 sau 0,9983. Când un şir cade testul vom obţine p-uri de valoare 1 sau 0 în sase sau mai multe locuri. Nu trebuie sa considerăm aşa cum un statistician ar face, că o valoare a lui p<0.025 sau p>0,975 înseamna ca RNG-ul a cazut testul la nivelul 0,05. Asemenea valori ale lui p sunt întâlnite frecvent în testele DIEHARD chiar şi cu RNG-uri bune.

 

Vom enumera pe scurt testele DIEHARD numerotându-le dupa cum apar ăn histograma şi în ordinea în care sunt în sumarul testelor DIEHARD. Unele teste generează valori multiple ale lui p şi apoi furnizează o valoare de test Kolmogorov-Smirnof (KS). În aceste cazuri am marcat valorile p sub linia de mijloc iar valorile KS desupra liniei. Altfel, toate rezultatele testului sunt marcate deasupra liniei de mijloc.

 

1.Testul Birthday Spacings: 9 valori p şi un test KS asupra acelor valori au fost raportate.

2.Testul Overlapping 5-Permutation (OPERM5): Sunt generate 2 valori p de către test.

3.Testul Rangului Binar: O valoare p este generată de test asupra matricilor 31 x 31 şi o valoare generată de testele asupra matricilor 32 x 32.

4.Testul Rangului Binar: 25 de valori p pentru testele pe matrici 6 x 8 şi o valoare KS

5.Testul Bitstream: 20 valori p

6a.Testul Overlapping Pairs Sparse Occupancy Test (OPSO):m23 valori p

6b.Testul Overlapping Quadruples Sparse Occupancy (OQSO): 28 valori p

6c.Testul DNA 31: valori p

7. Testul Count the 1s: Testul este realizat asupra unui şir de biţi. 2 valori p au rezultat.

 

 

Fig.4

Histograma rezultatelor testelor DIEHARD. Testele sunt numerotate de la 1 la 15 în ordinea în care apar în rezumatul testelor DIEHARD şi valorile p raportate sunt marcate. Acest exemplu arată cazul în care sunt trecute toate testele.

 




 

 

 

 

8. Testul Count the 1s: Testul este efectuat pe biţi specifici. Rezultp 25 valori p.

9. testul Parking Lot: Rezultp 10 valori p şi un test KS asupra acelor valori.

10. Testul distanţei minime: rezultă 20 valori p şi un test KS

11. Testul sferelor 3D: rezultă 20 valori p şi un test KS asupra acelor valori.

12. Testul Squeeze: rezultă 1 valoare p

13. Testul Overlapping Sums: 10 valori p şi un test KS asupra acestor valori.

14. Testul Runs: Sunt generate 10 valori p într-o pereche de teste runs-up/runs-down şi 4 teste KS.

15. Rezultatele a 200.000 de jocuri cu zaruri sunt analizate generând o singură valoare p pentru fiecare joc câstigat şi pentru numărul de aruncări.

 

5.Rezultate

 

5.1 Compararea Ca-urilor bazate pe RNG-uri

 

Figura 5 arată diagramele spaţiu-timp şi rezultatele testelor DIEHARD pentru N=3 CA 30 şi 4 de N=4 CA care au fost descoperite în această investigare. Fiecare dintre aceastea va fi descris detaliat mai jos:

 

CA30 reprezintă cel mai bun dintre CA-urile unidimensionale, conectate local, cu o vecinătate de 3. La fel ca si cu celelalte CA-uri acesta a fost iniţializat cu un singur 1 în celula 0 (linia de sus). Diagrama spaţiu-timp arată 64 de biţi pe orizontală (de la 0 la 63) şi 200 de paşi în jos. CA30 nu trece testele DIEHARD numărul 2, 4, 6b, 6c, 8, 12, 14 si 15.

 

CA38490, o reţea de inele 1-d, este interesant pentru faptul că este mai încet decât celelalte CA-uri cu o vecinătate de 4 în trecerea către un stadiu cu o entropie ridicată. Acesta trece toate testele DIAHARD şi are o conectivitate relativă de {-3, 0, 4, 9}.

 

CA50745 este o reţea de inele 1-d cu o conectivitate de {-7, 0, 11,17}. A fost ales pentru a contrasta cu reţeaua de CA38490 conectată local . Acesta trece tot setul de teste DIEHARD.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Fig.5

Rândul de sus arată diagramele spaţiu-timp pentru 5 generatoare de numere aleatorii – stadiul CA-ului (biţii 0-63) este afişat pe orizontală (alb=1, negru=0) şi stadiile intermediare sunt afişate mai jos (sunt afişate 200 de stadii). Toate sunt ilustrate începând cu stadiul iniţial de un singur 1 în celula 0 (bitul cel mai din stânga).  Al doilea şi al treilea rând sunt rezumate ale testelor DIEHARD pentru biţii pari şi impari ale generatoarelor de numere aleatorii corespunzatoare. CA30 ilustrat pentru diferenţiere, cade 8 din testele DIEHARD (indicat de un pătrat în partea dreaptă a histogramei).

 
 

 

 

 

 

 

 

 

 

 

 

 


 

Fig.6

Aranjamentul fizic al FPGA şi frecvenţa de operare pentru automatele celulare generatoare de numere aleatoare din figura 5 (bazate pe Xilinx XCV1000-6)

 
 

 

 

 

 

 

 


Fig.7

Puncte de lungime a ciclului C faţă de CA de lungime n pentru CA38490 şi CA50745 din figura 5. Condiţia iniţială pentru teste a fost un stadiu al CA-ului cu un singur 1. Lungimile de ciclu rezultate nu sunt maxime în mod necesar.

 
 

 

 

 

 

 

 


CA27225 este o reţea curbată 2-d(figura 2b) cu o conectivitate relativă de {2n2w, cm n2e, 2se}. Aceasta trece toată seria de teste DIEHARD şi are o avansare foarte rapidă catre un stadiu de înalta entropie.

 

 

5.2 Experimente fizice

 

Datorită contextului unui FPGA convenţional (Xilinx XCV1000-6) şi al sistemul fizic al acestuia (Xilinx Foundation Series ISI 3.3i), s-au realizat 4 experimente pentru a determina dacă există o relaţie între topologia reţelei CA-urilor şi frecvenţa de ceas maximă.

 

După cum este ilustrat în figura 6, locul şi ruta sistemului răspund diferit la fiecare reţea de CA-uri pe 4 biţi. Frecvenţa de ceas maximă variază între 214 MHz pentru topologia 1-d {-7, 0, 11, 17} şi 230 MHz pentru topologia 2-d {2n2w, c, n2e, 2se}.

 

 

5.3 Lungimea ciclului

 

Fiecare automat cu stadii finite care trece printr-o secventa de stadii va întâlni un stadiu anterior. Numărul de stadii în această secvenţă repetitivă il vom nota cu c ; acest lucru reprezintă o măsuratoare importantă pentru orice CA considerat un generator de numere aleatorii.

 

Generatorele bazate pe automate celulare prezentate au cicli multipli. Ciclul particular din final este în functie de stadiul iniţial. Mai mult, funcţia neliniară implementată în fiecare CA permite stadiilor unice să avanseze la acelaţi stadiu al succesorului. Pentru fiecare instanţă cu k stadii unice ce avansează catre acelasi stadiu al succesorului, trebuie să existe k-1 stadii fară predecesor. Prin urmare, ciclii tind să aibă multe stadii neciclice pe care le vom denumi stadii feeder. De exemplu o analiză a tuturor secvenţelor de stadii de lungime n=31 CA50745 {-7, 0, 11, 17} este ilustrată în tabelul 1.

 

Tabelul 1: proprietăţile CA50745 {-7, 0, 11, 17} cu n=31

Lungimea c a ciclului

Stadiile feeder

Proto-states

182466

2147090938

7568343431

1705

109368

39339

279

98859

35371

31

0

0

1

1

1

 

Adiţional, s-au efectuat experimente asupra lungimii ciclilor pentru cele două CA-uri 1-d din figura 5. Pentru fiecare experiment, lungimea n a CA-ului a variat între 20 şi 64 de biţi iar lungimea c a ciclului a fost determinată pentru un stadiu iniţial constând într-un singur 1. Rezultatele sunt ilustrate în figura 7.

 

Locaţia singurului 1 din stadiul iniţial este imaterială datorită simetriei rotaţiei care rezultă din condiţiile de mărginire periodică. De remarcat faptul ca aceste lungimi ale ciclilor nu sunt în mod necesar lungimile maxime pentru n dat. De asemenea numărul de stadii feeder începând din stadiul iniţial în ciclul final poate fi o parte importantă a lui c sau în cazul în care c are o valoare mică, poate fi mult mai mare ca c.

 

 

6.Concluzii

 

Am descris o clasă de generatoare de numere aleatorii bazate pe automate celulare pe 64 de biţi cu o vecinătate de 4, lucru ce le permite să fie implementate în mod eficient cu tebelele cu 4 intrări din FPGA-urile folosite frecvent. Generatoarele au trecut toate testele din setul DIEHARD al lui Marsaglia.

 

Au fost descrise de asemenea reţelele cu condiţii de mărginire periodică de 1, 2 şi 3 dimensiuni. Experimentele fizice pentru aceste reţele au găsit o frecvenţă de ceas maximă între 214 MHz şi 230 MHz în funcţie de reţea. Toate generatoarele au necesitat o tabelă cu 4 intrări şi un singur registru de un bit pentru fiecare bit.

 

 

Bibliografie

 

1. N. Metropolis and S. Ulam, “The Monte Carlo method,” Journal

of American Statistical Association, vol. 44, pp. 335–341,

1949.

 

2. M. A. Kalos and P. A. Whitlock, Monte Carlo Methods, Volume

I: Basics, Wiley Interscience, New York, 1986.

 

3. S. K. Park and K. W. Miller, “Random number generators: good

ones are hard to find,” Communications of the ACM, vol. 31, no.

10, pp. 1192–1201, October 1988.

 

4. D. E. Knuth, The Art of Computer Programming: Volume 2,

Seminumerical Algorithms, 3rd ed., Addison-Wesley, ch. 3,

1998.

 

5. G. Marsaglia, “Remarks on choosing and implementing random

number generators,” Communications of the ACM, vol. 36, no.

7, pp. 105–110, July 1993.

 

6. G. Marsaglia, “A current view of random numbers,” Computer

Science and Statistics: The Interface, L. Billard, ed., Elsevier

Science Publishers B. V., pp. 3–10, 1985.

 

7. G. Marsaglia, DIEHARD, http://stat.fsu.edu/~geo/diehard.html,

1996.

 

8. VR. C. Tausworthe, “Random numbers generated by linear

recurrence modulo two,” Mathematical Computing, vol. 19, pp.

201–209, 1965.

 

9. S.W. Golomb, Shift Register Sequences, Holden-Day, San Francisco,

1967.

 

10. S. Wolfram, “Random sequence generation by cellular automata,”

Advances in Applied Mathematics, vol. 7, pp. 123–169,

June 1986. (Also available in S. Wolfram, Cellular Automata

and Complexity, Addison-Wesley, 1994.)

 

11. P. D. Hortensius, R. D. McLeod, and H. C. Card, “Parallel number

generation for VLSI systems using cellular automata,” IEEE

Transactions on Computers, vol. 38, no. 10, pp. 1466–1473,

October 1989.

 

12. B. Shackleford, G. Snider, R. J. Carter, E. Okushi, M. Yasuda, K.

Seo, and H. Yasuura, “A high-performance, pipelined, FPGAbased

genetic algorithm machine,” Genetic Programming and

Evolvable Machines, vol. 2, no. 1, pp. 33–60, March 2001.

 

13. P. D. Hortensius, H. C. Card, R. D. McLeod, and W. Pries,

“Importance sampling for Ising Computers using one-dimensional

cellular automata,” IEEE Transactions on Computers,

vol. 38, no. 6, pp. 769–774, June 1989.

 

14. Ph. Tsalides, T. A. York, and A. Thanailakis, “Pseudorandom

number generators for VLSI systems based on linear cellular

automata,” IEE Proceedings-E, vol. 138, no. 4, pp. 241–249,

July 1991.

 

15. S. Nandi, B. Vamsi, S. Chakraborty, and P. P. Chaudhuri, “Cellular

automata as a BIST structure for testing CMOS circuits,”

IEE Proceedings-Computer Digital Technology, vol. 141, no. 1,

pp. 41–47, January 1994.

 

16. D. R. Chowdhury, I. Sengupta, and P. P. Chaudhuri, “A class of

two-dimensional cellular automata and their applications in random

pattern testing,” Journal of Electronic Testing, vol. 5, pp.

67–82, 1994.

 

17. M. Sipper and M. Tomassini, “Generating parallel random number

generators by cellular programming,” International Journal

of Modern Physics C, vol. 7, no. 2, pp. 181–190, 1996.

 

18. M. Tomassini, M. Sipper, M. Zolla, and M. Perrenoud, “Generating

high-quality random numbers in parallel by cellular

automata,” Future Generation Computer Systems, vol. 16, pp.

291–305, 1999.

 

19. M. Tomassini, M. Sipper, and M. Perrenoud, “On the generation

of high-quality random numbers by two-dimensional cellular

automata,” IEEE Transactions on Computers, vol. 49, pp. 1146–

1151, October 2000.

 

20. S. Wolfram, “Statistical mechanics of cellular automata,”

Reviews of Modern Physics, vol. 55, pp. 601–644, July 1983.

(Also available in S. Wolfram, Cellular Automata and Complexity,

Addison-Wesley, 1994.)

 

21. S. Ulam, “Random processes and transformations,” Proceedings

of the International Congress of Mathematics (1950), vol. 2, pp.

264–275, 1952.

 

22. J. von Neumann, Theory of Self-Reproducing Automata, ed.

Authur Burks, University of Illinois Press, 1966.

 

23. S. Wolfram (ed.), Theory and Applications of Cellular Automata,

World Scientific, 1986.

 

24. S. Wolfram, A New kind of Science, Wolfram Media, January

2002.

 

 

Lista celor 167 de CA-uri cu conectivitatea {-7, 0, 11, 17} care au trecut testele de entropie şi testele DIEHARD:

 

25946, 34425, 50745, 38553, 42075, 22117, 13929, 27029,

5865, 50739, 26211, 15045, 27795, 58395, 4845, 49977,

50742, 27027, 38454, 11985, 18870, 51510, 22121, 13005,

38501, 38595, 18615, 38565, 25398, 15513, 27798, 27705,

22933, 26307, 25449, 36210, 14742, 13257, 37692, 26262,

7905, 19125, 26775, 27225, 26313, 15507, 40086, 26006,

38556, 54315, 11220, 30855, 40545, 51555, 39267, 39363,

14025, 27237, 37788, 38547, 50019, 14019, 29835, 49974,

34170, 27702, 37833, 26937, 39318, 11475, 27801, 14649,

25500, 15561, 26969, 49470, 9690, 37737, 25961, 37782,

14652, 39990, 26166, 37731, 22953, 55335, 38457, 13974,

25494, 45645, 19890, 38249, 14745, 21865, 40035, 37485,

7395, 26965, 39273, 26979, 46155, 50793, 14793, 15459,

42329, 27033, 40131, 14646, 26966, 17340, 33660, 14739,

13515, 42345, 26025, 22695, 15411, 21165, 14787, 5355,

14697, 50838, 24990, 31875, 13923, 37689, 23715, 50787,

14748, 27081, 23189, 38601, 13980, 37785, 27843, 41310,

9180, 37995, 39015, 33405, 3315, 38451, 10200, 10455,

53295, 39574, 25443, 27747, 39258, 13161, 16830, 26931,

22181, 38489, 49725, 25545, 26934, 38549, 50235, 35190,

27753, 40041, 3060, 41820, 39510, 50490, 42840.