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,
I: Basics,
Wiley Interscience,
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,
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,
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.