numere aleatoare Arduino. Generarea de numere aleatorii pe microcontrolere. Metoda liniară congruentă

Timpul și aleatorietatea. Reacţie

De data aceasta vom învăța ce sunt valorile „aleatorie” și, de asemenea, vom învăța cum să lucrăm cu timpul.

Noi vom avea nevoie:

  • Butonul tact
  • Scârţâit
  • Cabluri de conectare „MALE-MALE”

Reacţie

Sarcina noastră pentru astăzi este să asamblam o diagramă care să ne permită să aflăm viteza reacției noastre.

Când apăsați butonul din stânga, un semnal se aude după un timp „aleatoriu”. Și când apăsați butonul din dreapta, se notează cât timp a trecut de la scârțâit până la apăsarea butonului din dreapta.

Cei pricepuți îl încearcă ei înșiși și ne uităm la diagramă.

#define BUZ 8 #define START 9 #define STOP 7 int timp; //Variabilă pentru sincronizare void setup() (Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START)) == 0) // Când apăsați butonul START.. ( int start_time = millis(); // Amintiți-vă momentul apăsării time = start_time; // Scrieți-l într-o variabilă globală. int Rand = random(0, 4000) ); // Să generăm un timp de întârziere "aleatoriu" = timp + Rand //Adăugați tonul de întârziere (BUZ, 3000, 500) == 0 &&; digitalRead( START) == 1) // Când apăsați butonul STOP... ( int stop_time = millis(); // Amintiți-vă ora de oprire. time = stop_time - time; // Calculați diferența de timp. Serial.println ("Timp: "); // Apăsați din nou butonul START.

Explicații

int timp; Variabilele (nu toate), atunci când le denotă, nu trebuie să li se dea nicio valoare. Am folosit această variabilă pentru a lega două instrucțiuni if.

În C++, variabilele declarate în interiorul unei bucle nu vor fi accesibile în alte bucle, deoarece au efect numai în cadrul acelei bucle. Acest lucru se face pentru a preveni erorile de programare. Când codul programului crește, veți înțelege despre ce vorbesc.

Pentru a face o variabilă disponibilă pentru mai multe instrucțiuni, trebuie să o faceți globală. Acestea. declara o variabilă în afara funcțiilor.

milis(); Returnează numărul de milisecunde care au trecut de la pornirea programului.

Avem nevoie de el pentru a măsura timpul care a trecut de la semnalul dat până la apăsarea butonului.

Aleatoriu(min,max); Acesta este un generator de numere aleatorii. Ia două valori. Acesta generează un număr în intervalul de la min la max.

Numerele „aleatoare” deoarece sunt o secvență specifică de valori. Foarte lung, dar la fel. Pentru a obține secvențe diferite, ar trebui să utilizați AleatoriuSămânță();

Această funcție inițializează generatorul. Și dacă setăm parametrul la aleator, atunci vom obține secvențele de care avem nevoie. Secvența va fi aceeași dacă parametrul este fix.

Concluzie

Acum vă puteți antrena reacția folosind un dispozitiv pe care l-ați creat singur. Sau poți continua să studiezi mai departe.

Lista radioelementelor

Desemnare Tip Denumire Cantitate NotăMagazinBlocnotesul meu
Placa Arduino

Arduino Uno

1 La blocnotes
Tabla de paineBreadboard-jumătate1 La blocnotes
Emițător piezoPasiv1 La blocnotes
Butonul de tactFara incuietoare2 La blocnotes
Fire de conectare"Tata-Papa"1

S-au scris multe despre generatoarele de numere aleatoare, dar aproape întotdeauna, când vine vorba de implementare, este subînțeles (sau explicit) că vorbim despre x86/x64 și alte arhitecturi „adulte”. În același timp, forumurile dedicate dezvoltării dispozitivelor pe microcontrolere sunt pline de întrebări „cum pot genera un număr aleator la %controllername%?” În plus, gama de răspunsuri se extinde de la „uitați-vă pe Google/Wikipedia” la „utilizați funcția standard”. Această „funcție standard” nu există întotdeauna și se potrivește dezvoltatorului în toate privințele mai des, este invers: uneori numerele sunt departe de a fi aleatorii, alteori viteza de funcționare este prea mică sau, uneori, codul rezultat nu; se încadrează deloc în memoria liberă.
Să încercăm să ne dăm seama care sunt algoritmii de generare a numerelor aleatoare, cum să-l alegem pe cel potrivit și, cel mai important, care sunt caracteristicile implementării acestor algoritmi pe controlere.

Evaluarea „aleatoriei”

Aplicațiile pentru RNG pot fi foarte diferite, de la jucării la criptografie serioasă. În consecință, cerințele pentru generator variază foarte mult. Există teste speciale pentru a evalua calitatea (nivelul de „aleatorie”) a generatorului. Iată cele mai elementare dintre ele:
  • Test de frecventa. Constă în numărarea numărului de zerouri și unu dintr-o succesiune de biți. Ar trebui să existe un număr aproximativ egal de unu și zero.
  • Testați o secvență de biți identici. Sunt căutați rânduri de biți identici, cum ar fi 000...0 sau 111...1. Distribuția de frecvențe cu care apar seria, în funcție de lungimea lor, ar trebui să corespundă acestei distribuții pentru un semnal cu adevărat aleatoriu.
  • Test spectral. O transformată Fourier discretă este aplicată secvenței inițiale. Spectrul rezultat nu ar trebui să aibă vârfuri semnificative care să indice prezența proprietăților periodice ale secvenței.
  • Test de autocorelare. Se calculează valoarea corelației dintre copiile de secvență deplasate unul față de celălalt. Testul vă permite să găsiți regiuni care se repetă într-o secvență.
Există kituri speciale care includ zeci de teste similare:
NIST - folosit în competiția AES pentru evaluarea algoritmilor de criptare.
DIEHARD este unul dintre cele mai riguroase seturi existente.

Algoritmi PRNG

Orice secvență generată conform unui algoritm strict definit nu poate fi considerată cu adevărat aleatorie, prin urmare, atunci când se vorbește despre generatori algoritmici, se folosește termenul pseudoaleatoare ulterior. Orice generator de numere pseudo-aleatorie (PRNG) va intra în buclă mai devreme sau mai târziu, celălalt lucru este că acest „târziere” poate veni în câteva milisecunde, sau poate în câțiva ani. Lungimea ciclului depinde de dimensiunea stării interne a generatorului N (de fapt, aceasta este cantitatea de memorie necesară generatorului) și variază de la 2 (N/2) la 2 N biți.
Au fost inventate o mare varietate de algoritmi PRNG, dar nu toți sunt convenabil pentru implementare pe microcontrolere. Suntem sever limitați în viteză și memoria disponibilă multe controlere nu acceptă instrucțiuni de aritmetică reală sau chiar de înmulțire. Ținând cont de aceste limitări, să ne uităm la câțiva algoritmi cunoscuți.
Metoda liniară congruentă
Următorul membru al secvenței este calculat folosind formula
X i+1 = (aX i + c) mod m
Număr m definește perioada maximă a secvenței, numere întregi AȘi c- coeficienți „magici”. Număr m Este rezonabil să alegeți o putere egală cu doi în acest caz, operația de conversie modulo este redusă la eliminarea celor mai semnificativi biți. Pentru a obține perioada maximă, trebuie îndeplinite următoarele condiții:
- c iar m trebuie să fie relativ prim,
- a-1 trebuie să fie multiplu p pentru toți factorii primi p numere m,
- Dacă m este multiplu de 4 (și în cazul nostru va fi un multiplu), atunci a-1 trebuie să fie multiplu de 4.
Mai există o subtilitate: doar biții cei mai semnificativi ai variabilei de stare X ar trebui luați ca rezultat, deoarece pentru cei mai mici biți parametrii statistici de aleatorie sunt mult mai răi. Algoritmul liniar congruent este implementat în mod obișnuit ca rand() standard în multe biblioteci.

Pro:

  • perioada maximă posibilă pentru o dimensiune dată a variabilei de stare;
  • destul de repede;
  • adesea deja implementat în biblioteca compilatorului.
Minusuri:
  • este necesară o operație de înmulțire;
  • nu toți biții sunt la fel de aleatori.
Rezumat: un algoritm rapid și simplu pentru aplicații nu foarte solicitante.
Metoda Fibonacci cu întârzieri
Acest algoritm folosește relația
X i = X i-a - X i-b ,
unde este variabila de stare X- întreg fără semn. Valori de întârziere AȘi b se iau nu oricare, ci cele strict definite pentru a atinge calitatea maximă, se recomandă perechi (17,5), (55,24) sau (97,33). Cu cât întârzierea este mai mare, cu atât perioada este mai lungă și proprietățile spectrale ale secvenței sunt mai bune. Pe de altă parte, pentru ca generatorul să funcționeze, este necesar să stocați max(a,b) numerelor anterioare, ceea ce nu este întotdeauna acceptabil. De asemenea, pentru a rula generatorul aveți nevoie de numere max(a,b), care sunt de obicei obținute folosind un PRNG mai simplu.

Pro:

  • nu necesită operații de înmulțire;
  • toți biții unui număr aleatoriu sunt echivalenti în proprietăți statistice.
Minusuri:
  • necesită o cantitate mare de memorie;
  • necesită o gamă largă de numere pentru a rula.
Rezumat: algoritm de foarte înaltă calitate, dar consumatoare de resurse.
Registru de schimbare linear cu feedback


Variabila de stare este stocată într-un registru de lungime N. Generarea stării următoare implică doi pași:
  1. Se calculează valoarea bitului C = X i1 xor X i2 xor… X ik, unde i1, i2...ik- înregistrează numere de biți, apelate curbe.
  2. Registrul este deplasat cu 1 bit la dreapta, bitul din stânga preia valoarea CU.
Ieșirea generatorului este bitul din dreapta (sau din stânga, sau orice altceva) al registrului, adică secvența pseudoaleatorie este generată cu un bit pe iterație. Cu numerele selectate corect, perioada generatorului va fi 2 N - 1. „Minus unu”, deoarece există o stare zero interzisă a registrului. Numerele filialelor pentru N de la 3 la 168 pot fi găsite în acest document.
Pe lângă configurația descrisă mai sus, care, apropo, se numește configurația Fibonacci (a nu se confunda cu metoda PRNG cu același nume!), există așa-numita. Configurația Galois.


În loc să folosească suma biților din secvența de atingere pentru a genera un nou bit din stânga, XOR face fiecare bit din secvența de atingere cu bitul din dreapta, apoi rotește întregul registru la dreapta. Această schemă este mai greu de înțeles, dar mai ușor de implementat, deoarece toate operațiunile XOR pot fi efectuate simultan. În ceea ce privește durata perioadei și calitatea numerelor pseudoaleatoare, schemele Fibonacci și Galois sunt echivalente.

Pro:

  • implementare foarte simplă, nici măcar nu necesită aritmetică, doar operații pe biți și deplasări;
  • algoritm foarte rapid (în special schema Galois);
  • proprietăți statistice bune.
Minusuri:
  • trebuie să verificați valoarea inițială pentru inegalitatea la zero.
Rezumat: algoritm foarte rapid și destul de de înaltă calitate.
Algoritmi de criptare
Pentru utilizarea în criptografie, PRNG-urile au încă o cerință esențială: ireversibilitate. Toți algoritmii enumerați mai sus nu au această proprietate: cunoscând mai multe valori de ieșire ale PRNG, puteți, prin rezolvarea unui sistem simplu de ecuații, să găsiți parametrii algoritmului (aceleași constante „magice” a, b, c etc). Și cunoscând parametrii, puteți reproduce întreaga secvență pseudo-aleatorie.
Orice cifru bloc suficient de puternic poate fi folosit ca algoritm PRNG criptografic puternic. Alegând o cheie secretă, puteți obține blocuri de numere pseudoaleatoare aplicând algoritmul numerelor naturale secvențiale. Pentru un cifru bloc de N biți, perioada nu va fi mai mare de 2 N. Securitatea unei astfel de scheme depinde în întregime de secretul cheii.
Toți algoritmii criptografici moderni sunt testați pentru a fi utilizați ca PRNG, adică folosind un algoritm certificat, nu este nevoie să vă pese în mod special de proprietățile statistice și spectrale ale fluxului de ieșire. Trebuie doar să vă faceți griji pentru „lacomia” computațională a algoritmilor cripto. Dacă trebuie să efectuați un număr mare de operațiuni de criptare, este logic să alegeți un controler cu blocuri criptografice hardware. Adesea, astfel de controlere au și un PRNG hardware foarte bun, rezistent la criptografie.

Surse de entropie

După cum sa menționat deja, folosind doar algoritmi determiniști, este imposibil să generați un număr cu adevărat aleatoriu. Prin urmare, se folosește de obicei o combinație de PRNG + extern sursa de entropie. Sursa de entropie este utilizată pentru a seta valoarea inițială pentru PRNG, iar sarcina acestuia din urmă este de a asigura puritatea spectrală și statistică a secvenței. Ce poate fi folosit ca sursă de entropie? Da, aproape orice.
Activitatea utilizatorului
Dacă dispozitivul interacționează cu utilizatorul în vreun fel, o soluție destul de bună ar fi folosirea utilizatorului în sine ca sursă de entropie. De exemplu, timpul de apăsare a unui buton, măsurat cu o precizie de microsecundă (sau mai degrabă, cifrele sale cele mai puțin semnificative), este complet imprevizibil. Cu toate acestea, adesea dispozitivul trebuie să funcționeze autonom, ceea ce înseamnă că suntem lipsiți de acest minunat canal de informare.
Convertor analog-digital
Multe controlere au ADC-uri încorporate. Și în multe controlere sunt de o calitate foarte mediocră, făcute doar „a fi”. Biții de ordin scăzut ai rezultatului ADC conțin aproape întotdeauna zgomot semnificativ, chiar și atunci când se măsoară tensiunea DC. Acest lucru poate fi folosit: conectați intrarea ADC la tensiunea de alimentare printr-un divizor, luați câteva zeci de măsurători, luați biții mai puțin semnificativi - aici aveți un număr mare aleatoriu. Dacă ADC-ul conține un preamplificator încorporat, porniți-l, este și zgomotos.
Generatoare asincrone
Puteți utiliza diferența de perioade a două generatoare de ceas nesincronizate. Majoritatea controlerelor conțin, de exemplu, un timer watchdog. Pentru a crește fiabilitatea, este tactat de la un generator separat, care nu este în niciun fel conectat cu semnalul de ceas principal. Este suficient să numărați numărul de cicluri ale semnalului de ceas principal în timpul unei perioade a temporizatorului watchdog. Dacă alegeți perioade astfel încât contorul să depășească de multe ori în timpul măsurării, puteți obține un număr destul de aleatoriu. Dezavantajul acestei metode este că durează mult, până la câteva secunde.
Ceas în timp real
Dacă diagrama are ceas în timp real, puteți utiliza citirile lor curente pentru a inițializa PRNG. De exemplu, transformând data/ora curentă în formatul de oră Unix, obținem imediat 32 de biți, care nu nu se va întâmpla din nou decât dacă luați citiri de mai multe ori pe secundă. Utilizarea timpului real oferă valori unice, dar nu oferă nicio imprevizibilitate, așa că este mai bine să combinați această metodă cu altele.
Circuit RC
Dacă controlerul nu are alte dispozitive periferice în afară de porturile I/O, puteți proceda după cum urmează: unul dintre picioare este conectat printr-un condensator la masă și printr-un rezistor la tensiunea de alimentare. Dacă intrările controlerului au rezistențe interne pull-up, nu este necesară o rezistență externă.

Emitem un semnal „0” către acest port - condensatorul este descărcat. Comutăm portul în modul de intrare - condensatorul începe să se încarce. Când tensiunea pe ea atinge pragul, intrarea va comuta de la starea „0” la „1”. Timpul de încărcare depinde puternic de mulți factori: tensiunea de alimentare, variația parametrilor circuitului RC, instabilitatea pragului, temperatură, scurgeri, interferențe. Măsurând-o cu suficientă acuratețe și luând cei mai puțin semnificativi biți, puteți obține o aleatorie bună.
Generator hardware de zgomot
Pentru multe aplicații serioase (în special criptografia), este necesară o sursă de entropie mai fiabilă decât cele enumerate mai sus. În astfel de cazuri, ei folosesc digitizarea semnalului de la un generator de zgomot bazat pe efecte termice, împușcate sau chiar cuantice. Elementul de zgomot este de obicei o diodă specială sau o diodă zener, semnalul de la care este amplificat și alimentat la un comparator care generează un flux binar de biți.

Pentru a se asigura că pragul de răspuns al comparatorului nu afectează proprietățile statistice ale semnalului primit, se folosesc două generatoare de zgomot, care funcționează pe un comparator:

Concluzie

În sfârșit, vă voi spune o poveste din viața mea. A început cu o altă întrebare pusă pe forum: „cum pot genera un număr aleator pe controler?” Autorul întrebării a explicat că, ca proiect de curs, realizează un dispozitiv care emulează aruncarea zarurilor. După mai multe încercări nereușite de a înțelege algoritmii, topicstarter și-a împărtășit soluția: pur și simplu a aruncat un zar real de 1000 de ori și a umplut toată memoria liberă a controlerului cu numerele rezultate. Generatorul a trecut cu brio toate testele de „aleatorie”, dat fiind că în timpul demonstrației a consumat mai puțin de o treime din „rezerva”.
Prin urmare, o astfel de soluție are și dreptul la viață, mai ales dacă se impun cerințe foarte stricte asupra aleatoriei numerelor, dar nu sunt cerute prea des. Odată cu scăderea vertiginoasă a prețurilor la memorie, ar putea fi înțelept să echipezați un dispozitiv cu o „rezervă de haos” care va dura întreaga viață a dispozitivului.
Vă mulțumesc pentru atenție!

UPD1: După cum s-a menționat pe bună dreptate în comentarii, dacă este planificat un atac asupra RNG, iar atacatorul are acces hardware la dispozitiv, sursele externe de entropie trebuie utilizate cu mare precauție, deoarece nu este foarte dificil să înlocuiți semnalul de la un sursă externă. Trebuie folosite surse interne, pe lângă cele externe.
De asemenea, este o idee bună să acumulați entropia în tot timpul liber și să o folosiți atunci când trebuie să generați următorul număr aleatoriu. De obicei, în astfel de cazuri așa-numitul Bazin de entropie- o matrice peste care se execută periodic una dintre funcțiile PRNG și în care datele din sursele de entropie sunt amestecate constant.

UPD2:În multe cazuri, este util să salvați conținutul pool-ului Entropy (îmi pare rău, nu cunosc traducerea normală în limba rusă) în EEPROM, astfel încât, după oprirea și pornirea dispozitivului, să nu-l acumuleze din nou. Aceasta se referă, în primul rând, la obținerea entropiei prin metoda generatoarelor asincrone: în condiții suficient de stabile, aceeași secvență poate fi generată după fiecare pornire.
Dacă este de așteptat un atac, luați măsuri de precauție împotriva falsificării EEPROM. Dacă controlerul permite acest lucru, blocați citirea/ștergerea/scrierea folosind biți de blocare, iar atunci când îl porniți, monitorizați integritatea EEPROM-ului, cel puțin folosind sume de control simple.

Etichete:

  • RNG
  • gpsch
  • microcontrolere
  • algoritmi
Adaugă etichete

Când programați Arduino, există momente în care trebuie să obțineți un număr care nu va fi cunoscut în prealabil nici programatorului care scrie schița, nici utilizatorului care va folosi Arduino cu un astfel de program. În acest caz, un generator de numere aleatoare (sau mai degrabă pseudo-aleatoare) vine în ajutor.



Pentru a activa acest generator, trebuie doar să utilizați funcțiile random() sau randomSeed(). Acest material vă va arăta cum să lucrați cu aceste funcții, precum și cum să scăpați de pseudoaleatoria atunci când generați numere.


În general, un generator de numere pseudoaleatoare simulează apariția haotică sau aleatorie a numerelor, dar, de fapt, dacă analizezi o serie a acestor numere pe o perioadă suficient de lungă, poți observa un anumit model.


Deci, funcția aleatoare pentru generarea numerelor pseudoaleatoare poate avea până la doi parametri și este scrisă ca aleatoriu (max) sau aleatoriu (min, max). Aici, parametrul max, care este obligatoriu, stabilește limita superioară a intervalului pentru generarea numerelor pseudoaleatoare. Folosind parametrul min suplimentar, puteți seta limita inferioară a intervalului. Ca rezultat, funcția va returna un număr pseudo-aleatoriu în intervalul de la min la max-1.


Este important să înțelegeți că atunci când utilizați funcția random(), va fi generată de fiecare dată aceeași listă de numere pseudoaleatoare. De exemplu, dacă faceți o mașină de slot și prima dată când apăsați mânerul, aceasta arată o combinație câștigătoare, atunci puteți fi sigur că dacă resetați Arduino și apăsați din nou mânerul, acel slot machine va afișa aceeași combinație câștigătoare . Într-adevăr, nu este ușor să implementezi o mașină de jocuri cu generare de numere complet aleatoare pe Arduino, așa cum este, de exemplu, implementată în mașinile de jocuri www.igrovye-apparati-vulcan.com/, dar poți rezolva parțial problema folosind randomSeed. () funcția.


Această funcție ia o valoare (cum ar fi un întreg) și folosește numărul pentru a modifica lista aleatoare generată de funcția random() Puteți pune randomSeed() în funcția de configurare și utilizați funcția random() într-un infinit buclă. Dar chiar și atunci, problema este că, deși secvența de numere aleatoare va fi diferită atunci când se folosește funcția randomSeed(), va fi în continuare aceeași de fiecare dată când se rulează schița.


Singura soluție în acest caz poate fi utilizarea perifericelor analogice (ADC) și a funcției analogRead() corespunzătoare. Dacă intrarea analogică nu este conectată la nimic, adică lăsată „atârnată” în aer, atunci datorită zgomotului de pe această linie puteți obține numere cu adevărat aleatorii. Apoi, în setarea de configurare, puteți scrie randomSeed(analogRead(A0)). Cu condiția ca portul analogic A0 să nu fie conectat nicăieri.

randomSeed(samanta)

Setează valoarea sau semințele ca punct de plecare pentru funcția random().

randomSeed(valoare); // setează „valoarea” ca valoare aleatorie inițială

Deoarece Arduino nu poate genera numere cu adevărat aleatorii, randomSeed vă permite să introduceți o variabilă, constantă sau altă funcție în funcția aleatoare, ceea ce ajută la generarea mai multor numere aleatoare.

numere „aleatoare”. Există multe semințe sau funcții diferite care pot fi utilizate în această funcție, inclusiv millis(), sau chiar analogRead() pentru a citi zgomotul electric printr-un pin analog.

aleatoriu (max.)

aleatoriu (min,max)

Funcția aleatorie vă permite să returnați un număr pseudo-aleatoriu în intervalul specificat de valorile minime și maxime.

valoare = aleatoriu(100, 200); // setează „valoarea” la aleatoriu

// un număr între 100 și 200

Notă: Utilizați acest lucru după ce ați folosit funcția randomSeed(). Următorul exemplu creează un număr aleator între 0 și 255 și emite PWM

semnal către ieșirea PWM egal cu o valoare aleatorie:

int randNumber; // variabilă pentru a stoca o valoare aleatorie

int led = 10; // LED cu rezistor pe pinul 10

void setup() () // nu este necesară configurarea

randomSeed(millis()); // setează millis() cu numărul inițial

randNumber = random(255); // număr aleator de la 0 – 255 analogWrite (led, randNumber); // iese semnal PWM

întârziere (500); // pauză pentru o jumătate de secundă

Sursa: Gololobov V. – De unde încep roboții. Despre proiectul Arduino pentru școlari (și nu numai) – 2011

postări asemănatoare

Serial.begin (rata) Deschide portul serial și setează viteza pentru transferul de date în serie. Rata baud tipică pentru comunicațiile cu computerul este de 9600, deși sunt acceptate alte viteze. void setup() (Serial.begin…….

Toate variabilele trebuie declarate înainte de a putea fi utilizate. Declararea unei variabile înseamnă definirea tipului valorii acesteia: int, long, float etc., atribuirea unui nume unic variabilei și, în plus…….

Bine, am instalat acest program. Am depanat „mecanismul” de lucru cu modulul. Și ne-am uitat la câteva exemple. Dar mi-aș dori să creez eu ceva util. Sa incercam. Mai întâi, să închidem proiectul anterior. Pentru aceasta…….

Atenţie! Când lucrați cu modulul Arduino în alte medii de dezvoltare, ar trebui să fiți atenți la configurația microcontrolerului (Siguranțe). Până când știi exact la ce ar putea duce schimbarea…….