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^[1] 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.^[2]

Definizione

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

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

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

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

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

assume solo due valori:

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

dove

${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.^[4]

Una sequenza binaria pseudo-casuale ha una lunghezza finita ${\displaystyle N}$ , che può essere estesa all'infinito ripetendola dopo ${\displaystyle N}$  bit. La sequenza complessiva assume però in questo modo anche un aspetto periodico,^[5] 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.^[6] 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.^[7]

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 ${\displaystyle N=2^{k}-1}$ ^[8] 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.^[9]

Ad esempio, nel caso ${\displaystyle k=3}$ , usando come generatore il polinomio ${\displaystyle x^{3}+x^{2}+1}$ ^[10] si ottiene una sequenza PRBS3 lunga ${\displaystyle 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 ${\displaystyle k}$ .

Generatori

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

Per generare le sequenze, si usano polinomi monici; i più comuni sono:^{[7][10][12][13][14]}

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

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

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

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

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

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

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

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

Applicazioni

I generatori di PRBS trovano impiego nelle telecomunicazioni per il test di collegamenti sia a commutazione di circuito^[15] che a commutazione di pacchetto,^[16] nella conversione di grandezze analogiche in contenuti informativo,^[17] nelle prove di circuiti elettronici,^[18][19] ma anche nella crittografia,^[20], nella simulazione,^[21] e nella spettrometria di massa a tempo di volo.^[22]

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.

Note

1. ^ (EN) PRBS Pseudo Random Bit Sequence Generation, su TTi.
2. ^ Codice PRN (Pseudo-Random Noise Code, su sbg-systems.com.
3. ^ (EN) Laszlo Naszodi, Articles on Correlation and Calibration, su scriptwell.net (archiviato dall'url originale l'11 novembre 2013).
4. ^ Fisica dell'informazione, La generazione di numeri casuali (PDF), Università di Perugia, p. 4.
5. ^ Generazione di numeri casuali, p.3
6. ^ Generazione di numeri casuali, p.1
7. ITU-T O.150
8. ^ ITU-T O.150, Sect.3
9. ^ ITU-T O.150, Sect.2
10. (EN) Kurt Tomlinson, PRBS (Pseudo-Random Binary Sequence), su Bloopist, 4 febbraio 2015.
11. ^ (EN) Paul H. Bardell, William H. McAnney e Jacob Savir, Built-In Test for VLSI: Pseudorandom Techniques, New York, John Wiley & Sons, 1987.
12. ^ (EN) Philip Koopman, Maximal Length LFSR Feedback Terms, su users.ece.cmu.edu.
13. ^ (EN) What are the PRBS7, PRBS15, PRBS23, and PRBS31 polynomials used in the Altera Transceiver Toolkit?, su Altera, 14 febbraio 2013.
14. ^ (EN) Daniele Riccardi e Paolo Novellini, An Attribute-Programmable PRBS Generator and Checker (XAP884) (PDF), su Xilinx, Table 3:Configuration for PRBS Polynomials Most Used to Test Serial Lines, 10 gennaio 2011.
15. ^ (EN) Testing the New Generation of SDH Digital Radio Networks, su Tektronix.
16. ^ (EN) Piers Dawe, Test patterns (PDF), New Orleans, IEEE P802.3ba, gennaio 2009.
17. ^ (EN) Pasquale Daponte, Luca De Vito, Grazia Iadarola e Sergio Rapuano, PRBS non-idealities affecting Random Demodulation Analog-to-Information Converters (PDF), su imeko.org.
18. ^ (EN) Umesh e Kotresh E. Marali, Analysis and Detection of various Faults in Combinational Circuits using D-Algorithm and BIST (PDF), in International Journal of Engineering Research and Technology (IJERT), NCRTS`14 Conference Proceedings, ISSN 2278-0181 (WC · ACNP).
19. ^ (EN) Jiegong Guo, Xinhua Cai e He Yigang, PRBS Test Signature Analysis of Switched Current Circuit, 2009 First International Conference on Information Science and Engineering, Nanchino, IEEE, 26-28 dicembre 2009, DOI:10.1109/ICISE.2009.842, ISBN 978-1-4244-5728-1, ISSN 2160-1291 (WC · ACNP).
20. ^ (EN) Shunyao Fan, Ashiq Rahman e Niloy K. Dutta, Encryption Using Optical Pseudo-Random Binary Sequence Based on Optical Logic Gate, in International Journal of High Speed Electronics and Systems, vol. 32, 02n04, 2350007, 2023, DOI:10.1142/S0129156423500076.
21. ^ (EN) Nabil Mohammed, Weihua Zhou, Behrooz Bahrani, David Hill e Frede Blaabjerg, PRBS-Based Impedance Measurement Tool for Stability Analysis of Black-Box EMT Models in PSCAD, 4th International Conference on Emerging Smart Technologies and Applications, eSmarTA 2024, Sana'a, IEEE, 6-7 agosto 2024, DOI:10.1109/eSmarTA62850.2024.10638870, ISBN 979-8-3503-5413-3.
22. ^ (EN) L.J. LeGore et al., Advantages of maximum likelihood methods for PRBS modulated TOF electron spectrometry (abstract), in Surface Science, aprile 2002, DOI:10.1016/S0039-6028(01)01950-1.

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.

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica