Sequenza binaria pseudo-casuale

Una sequenza binaria pseudo-casuale o pseudo-aleatoria (in inglese pseudo-random binary sequence, PRBS) è una sequenza di cifre binarie che, pur essendo generata tramite algoritmi deterministici, è difficile da prevedere e presenta un comportamento statistico simile a una sequenza casuale vera e propria.

Nelle telecomunicazioni, le sequenze binarie pseudo-casuali sono note anche come codici di rumore pseudo-casuale (Pseudo-Random Noise Code, PRN) dato che generano un segnale dalle caratteristiche simili a quelle del rumore bianco.

Definizione

Una sequenza binaria $a_{0},\ldots ,a_{N-1}$ è definita formalmente come una successione di $N$ bit:

$a_{j}\in \{0,1\}{\mbox{ per }}j=0,1,...,N-1$.

Una sequenza binaria è composta da $m=\sum a_{j}$ elementi di valore "1" e $N-m$ elementi di valore "0".

Una sequenza binaria è pseudo-casuale se la sua funzione di autocorrelazione, espressa da

$C(v)=\sum _{j=0}^{N-1}a_{j}a_{j+v}$

assume solo due valori:

$C(v)={\begin{cases}m,{\mbox{ per }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ altrove }}\end{cases}}$

dove

$c={\frac {m-1}{N-1}}$

è definito come duty cycle del PRSB, in analogia al duty cycle di un segnale continuo nel tempo. Nel caso di una sequenza di lunghezza massima, in cui $N=2^{k}-1$, il duty cycle è pari a 1/2.

Una PRBS si considera pseudo-casuale perché, nonostante sia in realtà deterministica, il valore di ogni suo singolo elemento $a_{j}$ è statisticamente indipendente dal valore di qualsiasi altro elemento e la distribuzione dei valori tende a essere uniforme, come avviene nelle sequenze casuali reali.

Una sequenza binaria pseudo-casuale ha una lunghezza finita $N$, che può essere estesa all'infinito ripetendola dopo $N$ bit. La sequenza complessiva assume però in questo modo anche un aspetto periodico, a differenza delle sorgenti naturali di sequenze davvero casuali, come quelle generate dal decadimento radioattivo o dal rumore bianco, che sono infinite e non presentano caratteristiche di ripetizione periodica. Tuttavia, proprio per la loro predicibilità, replicabilità e ripetitività i segnali PRBS sono impiegati nelle misure e nei test degli apparati e dei circuiti di telecomunicazione.

Notazione

Per indicare la lunghezza di una sequenza binaria pseudo-casuale si usano le notazioni PRBSk o PRBS-k (come ad esempio "PRBS7" or "PRBS-7") dove il numero massimo di bit della sequenza è dato da $N=2^{k}-1$ e k indica la dimensione della parola binaria in cui si possono suddividere i dati della sequenza. Data una sequenza di lunghezza N, considerando ogni sequenza di k bit si possono ottenere tutti i valori binari di una parola di lunghezza k (tutte le combinazioni di k bit a 0 e 1), ad esclusione della parola composta da tutti zero.

Ad esempio, nel caso $k=3$, usando come generatore il polinomio $x^{3}+x^{2}+1$ si ottiene una sequenza PRBS3 lunga $2^{3}-1=7$ bit il cui valore è "1011100". Isolando all'interno di questa sequenza tutte le parole di 3 bit si ottiene:

 "1011100" → 101
 "1011100" → 011
 "1011100" → 111
 "1011100" → 110
 "1011100" → 100
 "1011100" → 001 (si considera la sequenza come circolare)
 "1011100" → 010 (si considera la sequenza come circolare)

Le sette parole così individuate rappresentano tutti i valori binari distinti (non ordinati) ottenibili usando tre bit, senza ripetizioni ed escludendo la parola "000". Questo vale per tutte le sequenza PRBSk, qualunque sia il valore di $k$.

Generatori

Le sequenze binarie pseudo-casuali si possono generare usando i registri a scorrimento a retroazione lineare (Linear-feedback shift register, LFSR).

Per generare le sequenze, si usano polinomi monici; i più comuni sono:

PRBS7 = $x^{7}+x^{6}+1$

PRBS9 = $x^{9}+x^{5}+1$

PRBS11 = $x^{11}+x^{9}+1$

PRBS13 = $x^{13}+x^{12}+x^{2}+x+1$

PRBS15 = $x^{15}+x^{14}+1$

PRBS20 = $x^{20}+x^{3}+1$

PRBS23 = $x^{23}+x^{18}+1$

PRBS31 = $x^{31}+x^{28}+1$

Applicazioni

I generatori di PRBS trovano impiego nelle telecomunicazioni per il test di collegamenti sia a commutazione di circuito che a commutazione di pacchetto, nella conversione di grandezze analogiche in contenuti informativo, nelle prove di circuiti elettronici, ma anche nella crittografia,, nella simulazione, e nella spettrometria di massa a tempo di volo.

Altri esempi comuni sono la generazione di una sequenza di lunghezza massima tramite un registro a scorrimento a retroazione lineare (LFSR), le sequenze di Gold, impiegate nel CDMA e nel GPS), le sequenza di Kasami e le sequenza JPL, tutte basate su LFSR.

Bibliografia

• Alberto Rotondi, Paolo Pedroni e Antonio Pievatolo, 1. Generazione di numeri casuali (PDF), in Probabilità, statistica e simulazione, contenuto didattico a complemento del testo, terza edizione, Springer-Verlag, 2011.
• (EN) ITU-T Recommendation O.150 (10/1992) – Digital test patterns for performance measurements on digital transmission equipment, International Telecommunication Union.

Voci correlate

• Numeri pseudo-casuali
• Registro a scorrimento a retroazione lineare
• Rumore bianco

Collegamenti esterni

• (EN) A binary m-sequence: expansion of reciprocal of x^7 + x^6 + 1, su oeis.org.