Secvență binară pseudo-random

O secvență binară pseudo-aleatoare este un caz special al unei secvențe pseudo-aleatoare în care elementele iau două valori posibile 0 și 1 (sau -1 și +1 ). Este periodic.

Postulatele lui Golomb

Una dintre primele formulări ale unora dintre regulile fundamentale pentru proprietățile statistice ale secvențelor pseudoaleatoare periodice a fost prezentată de Solomon Golomb . Cele trei reguli de bază au ajuns să fie cunoscute sub numele de postulate Golomb.

  1. Numărul „1” din fiecare perioadă trebuie să difere de numărul „0” cu cel mult unu.
  2. În fiecare perioadă, jumătate din runde (de simboluri identice) trebuie să aibă lungimea unu, un sfert trebuie să aibă lungimea doi, o optime trebuie să aibă lungimea trei și așa mai departe. Mai mult, pentru fiecare dintre aceste lungimi, trebuie să existe același număr de curse de la „1” și „0”.
  3. Să presupunem că avem două copii ale aceleiași secvențe ale perioadei p, deplasate una față de cealaltă cu o valoare d. Apoi, pentru fiecare d, 0 <= d <= pl, putem număra numărul de potriviri dintre aceste două secvențe Ad și numărul de inconsecvențe Dd. Coeficientul de autocorelare pentru fiecare d este dat de (Ad - Dd)/p și această funcție de autocorelare ia valori diferite pe măsură ce d parcurge toate valorile permise. Apoi, pentru orice secvență care îndeplinește regula 3, funcția de autocorelare (ACF) ar trebui să ia doar două valori.

Postulatul 3 este o expresie tehnică a ceea ce Golomb a descris ca noțiune de încercări independente : cunoașterea unei valori anterioare a unei secvențe nu ajută, în principiu, la ghicirile despre valoarea curentă. Un alt punct de vedere asupra ACF este că este o anumită măsură a capacității de a distinge între o secvență și copia ei, dar începând dintr-un alt punct al ciclului.

O secvență care satisface postulatele Golomb este adesea denumită o secvență pseudo-zgomot sau o secvență PN .

O gamă largă de teste statistice diferite sunt aplicate secvenței analizate pentru a examina cât de bine este de acord cu presupunerea că o sursă complet aleatorie a fost utilizată pentru generare.

Soiuri

Vezi și