Generatore di sequenze pseudo-casuali

Generatore di sequenze pseudo-casuali

(Pseudo Noise Sequence Generator)

Giugno 2011

Enrico Molinari

Progetto realizzato per il corso di “Progettazione di Sistemi Microelettronici” (corso di Laurea Magistrale in Ingegneria Elettronica), con il supporto del Prof. Luca Fanucci, Università di Pisa, Facoltà di Ingegneria

Concetti di base ed applicazioni

Un generatore di sequenze pseudo-casuali PNSG (Pseudo Noise Sequence Generator), spesso chiamato anche generatore di numeri pseudo-casuali (PRNG, Pseudo Random Number Generator), è un dispositivo elettronico che, data in ingresso una particolare chiave (“key”, spesso detta anche “seme”, la cui introduzione impone lo stato iniziale del generatore, che è una macchina a stati finiti), fornisce in uscita una sequenza, un flusso, di numeri chiamata “keystream”, ossia una chiave (un codice) di lunghezza arbitraria, generalmente molto più lunga, in termini di cifre, della chiave generatrice (il seme).

I numeri costituenti la keystream, agli occhi di un osservatore esterno, risultano del tutto casuali, specialmente se questo non dispone di avanzate capacità computazionali; l’osservatore non può prevedere l’entità del numero (del simbolo, del bit) n-esimo, in procinto di essere prodotto e fornito in uscita, basandosi sulla semplice osservazione degli n-1 numeri precedentemente prodotti dal dispositivo e sul “trend” che ne ha caratterizzato la generazione.

Generare sequenze di numeri realmente casuali è molto dispendioso da un punto di vista temporale, pertanto solitamente si opta per l’utilizzo di sequenze numeriche che sembrano casuali ma in realtà sono generate in modo deterministico. Le sequenze di numeri pseudo-casuali si avvicinano molto, in termini di caratteristiche e proprietà, a quelle realmente randomiche.

Il seme è l’unico elemento realmente casuale, e la sequenza numerica realizzata dal generatore di numeri pseudo-casuali non è altro che un’espansione del seme in una stringa più lunga, mediante un algoritmo, ossia un processo deterministico, implementato da una particolare topologia circuitale.

L’output è prodotto pertanto da una specifica funzione logica, e da ciò si deduce che l’introduzione dello stesso seme nel PNSG genererà sempre la stessa sequenza di output, e che la stringa pseudo-casuale non potrà essere infinita.

La massima lunghezza della stringa di output, prima che questa cominci a ripetersi, è definita “periodo” della sequenza pseudo-casuale, solitamente si misura in bit oppure in cicli (periodi) di clock e dipende dalla particolare circuiteria implementata nel generatore e dal seme stesso.

Se il seme introdotto ha lunghezza, misurata in bit, pari ad n, allora il periodo massimo della sequenza di output sarà pari a n n (2 – 1)n bit, e tale sequenza si ottiene attendendo un numero di periodi di clock pari a 2 – 1, dato che in un periodo di clock lo PNSG fornisce, in parallelo, una stringa di n bit.

La qualità di un generico PNSG è direttamente proporzionale al grado di pseudo-aleatorietà che caratterizza la generazione dei bit della sequenza di output e può essere rappresentata dal “coefficiente di sbilanciamento statistico” s, definito come:

s = –

dove n rappresenta, come vedremo, il numero di stadi (di “stage”) di cui consta l’architettura elettronica del generatore, ossia il numero di bit del seme con cui dobbiamo caricare lo stato iniziale del dispositivo.

Supponiamo che l’uscita del generatore, ossia la sequenza pseudo-casuale, costituisca il segnale digitale di ingresso di un codificatore 2-PAM che associa al livello logico “0” il simbolo “1” e al livello logico “1” il simbolo “-1”.

La probabilità che il bit m-esimo della sequenza pseudo-casuale, codificata dai simboli appartenenti alla costellazione 2-PAM, risulti codificato dai simboli +1 o -1, ovvero che il bit stesso, prima della codifica, assuma valore 0 o 1, è data dalle seguenti espressioni: Pr{b = +1} = (1 – s) Pr{b = -1} = (1 + s)

m m

Evidentemente maggiore è n, ossia maggiore è la complessità dello PNSG, e minore è il valore di s, che tende a zero per valori di n molto alti, ossia per PNSGs realizzati mediante molti stadi; più s tende a zero e più i due valori di probabilità suddetti risultano pari a ½, ossia più i vari stati nei quali il generatore può trovarsi sono equiprobabili.

Pertanto maggiore è il numero n degli stadi di cui il generatore consta e più il funzionamento dello stesso si avvicina a quello di uno PNSG ideale (s = 0, “algoritmo” di produzione dei bit di uscita non più deterministico, più simile al processo stocastico di lancio di una moneta), il quale funzionerebbe, in linea teorica, per mezzo di un processo di generazione privo di memoria, durante il quale l’osservazione del suo stato, in un dato istante, non consente alcuna previsione sul futuro.

I dispositivi PNSG rappresentano una categoria di strumenti che continuano ad acquisire sempre maggiore rilevanza nello sviluppo di nuove tecnologie; la necessità di sfruttare sequenze di numeri pseudo-random si manifesta ormai in molteplici applicazioni, fra le quali:

• Crittografia (generazione di chiavi)
• Geometriche (metodo Monte Carlo)
• Modellazione di andamenti finanziari (azioni in Borsa)
• Informatica (addestramento reti neurali, inizializzazione algoritmi)
• Telecomunicazioni (trasmissione “Spread Spectrum”, di cui parleremo)
• Elettronica (modellazione dispositivi in frequenza)
• Divertimento (videogiochi, giochi d’azzardo)

Possibili architetture di uno PNSG

Una delle architetture maggiormente utilizzate, specialmente nel campo della crittografia, è quella basata sull’implementazione circuitale di un dispositivo noto come “registro a scorrimento lineare retroazionato” (LFSR, “Linear Feedback Shift Register”), di cui riportiamo una rappresentazione schematica di principio:

I bit che costituiscono il seme (C₁, …, C_n) vengono inseriti parallelamente al fine di settare lo stato iniziale del dispositivo; l’inserimento della key deve essere effettuato prima dell’avvio del segnale di clock, il quale è comune a tutti i registri (cioè gli stadi) disposti in cascata.

Prima dell’avvio del clock, ossia prima che si verifichi il primo fronte di salita del clock (assumiamo di avere registri flip-flop positive edge triggered), l’uscita di ciascun registro seriale deve aver assunto stabilmente il valore logico “1”.

A partire dal primo fronte di salita del clock in poi, cioè dall’istante in cui, per la prima volta, ciascun registro aggiorna il valore della propria uscita con quello del proprio ingresso, lo stato del dispositivo evolve nel tempo: il LFSR transita, periodo di clock dopo periodo di clock, da uno stato all’altro, fino a tornare, dopo un certo periodo, che dipende dal seme inserito (cioè da come abbiamo settato i terminali di “tap” mediante i coefficienti binari C_i), allo stato iniziale caricato tramite le terminazioni C_i delle n porte AND.

Nel settore delle telecomunicazioni da terminale mobile (“wire-less communications”) si utilizza spesso una particolare versione del LFSR, nota come PNSG, la quale costituisce la nostra scelta architetturale per la realizzazione del generatore di sequenze pseudo-casuali per trasmissioni CDMA IS-95.

Qui di seguito riportiamo una rappresentazione astratta di un generico PNSG realizzato mediante l’architettura da noi scelta e descritta, mentre a pagina seguente abbiamo a destra la “schematic view”, ossia lo schema circuitale dettagliato (da noi descritto in linguaggio VHDL), di uno PNSG a 15 stadi (15 registri flip-flop D) compattamente rappresentato dal polinomio caratteristico a coefficienti binari G(x) = x¹⁵ + x¹³ + x⁹ + x⁸ + x⁷ + x⁵ + 1, e a sinistra la “simbolic view” dello stesso PNSG, ossia la relativa black box, con le sole porte di ingresso e uscita, utilizzata nel test bench.

Funzionamento dell’architettura scelta per la realizzazione dello PNSG per trasmissioni CDMA IS-95

Di fondamentale importanza è assicurarsi che il segnale di reset, da noi preso attivo basso, comune ai 15 registri seriali realizzati mediante flip-flop D, abbia assunto stabilmente valore logico “1” nell’istante in cui, per la prima volta, il segnale di clock (comune anch’esso ai 15 registri in cascata) subisce una variazione di tipo positive edge, mentre il valore di “sel” ha già stabilmente assunto valore “0”, ossia il loop di feedback è chiuso.

Se nell’istante del primo fronte di salita del clock il reset fosse basso tutti i 15 flip-flop D aggiornerebbero le rispettive uscite Q, ciascuna di esse costituita da un singolo bit, con il valore logico “0”, pertanto lo stato iniziale dello PNSG risulterebbe una stringa di 15 zeri e sarebbe impossibile per il dispositivo evolvere, nel tempo, in uno stato diverso, ossia uscire dallo stato iniziale caricato.

Qualche istante prima del primo fronte di salita del clock è altresì necessario aver inserito il seme di 15 bit per mezzo degli appositi piedini e aver settato a “0” il bit di controllo “sel” (identificato come “init”, nel codice VHDL) dei 15 multiplexer al fine di istruire gli stessi a fornire in uscita i bit costituenti la key appena inserita mediante i rispettivi canali di ingresso x₁.

In tal modo al primo fronte di salita del clock il k-esimo flip-flop D (k: 1 ≤ k ≤ 15) aggiorna la propria uscita Q_k con il valore del bit b_k imposto in ingresso dall’utente, dopodiché il bit “sel” deve essere reimpostato in modo da imporre ai multiplexer di fornire in uscita il valore del secondo ingresso x₀, ovvero l’uscita Q del registro precedente.

Quindi dal secondo fronte di salita del clock in poi il generatore non risente più della word-line b₁…b₁₅ con la quale abbiamo inserito il seme (il disaccoppiamento fra la word-line di ingresso ed il circuito sottostante è garantito dallo stato x₀D in cui si trovano i 15 multiplexer) ed evolve, periodo di clock dopo periodo di clock, in funzione della logica implementata a livello circuitale, rappresentata compattamente dal polinomio caratteristico G(x).

A livello architetturale la struttura dello PNSG è molto simile a quella del LFSR: la differenza infatti consiste nelle modalità di inserimento del seme, effettuato appunto mediante i multiplexer e non attraverso le porte AND, e nel fatto che i bit C_i del LFSR sono realizzati rigidamente, cablati, mediante opportuni collegamenti circuitali statici, al fine di implementare la forma algebrica di G(x).

Per esempio anziché imporre al bit C₁₄ il valore logico “0” è sufficiente, per realizzare il coefficiente nullo che moltiplica il monomio x¹⁴ di G(x), evitare il collegamento fra Q₁₄ e la porta XOR più vicina: infatti il risultato della AND sarebbe sempre 0, essendo C₁₄ = 0, e di conseguenza l’uscita della XOR sarebbe 0 nel caso in cui l’uscita della XOR sia 0 ed 1 nel caso in cui l’uscita della XOR sia 1.

Tale trasparenza della porta XOR₁₄ nei confronti dell’output della porta XOR₁₅, ossia nei confronti del bit Q₁₅ (poiché nella struttura equivalente del LFSR avremmo imposto C₁₅ = 1), suggerisce la semplificazione circuitale che differenzia lo PNSG dal LFSR. Il risparmio in termini di numero di porte logiche AND e XOR è evidente.

Consideriamo adesso, in linea del tutto generale, uno PNSG nella sua forma “general purpose”, vale a dire uno PNSG “LFSR – like”, ossia completo di porte AND “tap” con le quali, mediante i bit C_i, è possibile settare il polinomio caratteristico G(x) che si desidera implementare:

Come già detto se C_i = 1 la porta AND – tap i-esima si comporta, di fatto, come un cortocircuito proveniente dal terminale Q_i, mentre se C_i = 0 la porta AND – tap i-esima si comporta come un circuito aperto (il terminale Q_i non comunica con il piano circuitale delle porte XOR).

Lo PNSR, formato da n registri, espande un seme lungo n bit, ossia una key di n bit da noi inserita, in una keystream di periodo massimo L = ( – 1)n bit, in – 1 cicli di clock (n = numero dei registri seriali, cioè degli stadi), soltanto se sono verificate le seguenti due condizioni necessarie e sufficienti:

• Il polinomio caratteristico G(x) implementato dallo PNSG deve essere “primo”, ovvero non fattorizzabile.
• Il seme inserito b₁…b_n deve corrispondere alla stringa 0…01.

Ad esempio se lo PNSG consta di n = 15 stadi potremmo eseguire il seguente esperimento: inserire il seme 000000000000001 e permutare, di volta in volta, il valore 0/1 dei coefficienti binari di tap C_i, ovvero modificare la topologia circuitale equivalente del dispositivo, ossia modificare di volta in volta il polinomio caratteristico G(x) in modo tale che questo risulti primo, così da soddisfare le due condizioni di cui sopra.

Ci accorgeremmo che per ciascuno dei 1800 G(x) primi implementabili mediante l’opportuno settaggio dei tap (settaggio opportuno dei bit C_i, 1800 combinazioni dei 15 bit C_i, ciascuna delle quali determina un particolare G(x) non fattorizzabile) avremmo, in uscita, una sequenza pseudo-casuale lunga L = ( – 1)n = ( – 1)15 = 491505 bit, ossia L = – 1 = 32767 colpi di clock.

Pertanto uno PNSG di 15 stadi ha la possibilità di generare, a partire dall’opportuno seme di cui sopra, ben 1800 keystream, 1800 chiavi, ovvero 1800 codici C (tutti diversi fra loro) di lunghezza pari al periodo L = 32767 T_clock = 491505 bit.

Per calcolare il numero di codici C “massimamente lunghi” (cioè di lunghezza pari al periodo L = – 1), dato uno PNSG ad n stadi, è sufficiente applicare la seguente formula:

numero dei codici C = = numero dei G(x) primi

dove i P_j costituiscono i numeri primi (3, 5, 7, 11 ecc…) che scompongono il numero che rappresenta, in periodi di clock, il periodo L = – 1, mentre gli α_i sono gli esponenti di tali fattori primi.

Per esempio se considerassimo uno PNSG di n = 6 stadi, avremmo periodo L = – 1 = – 1 = 63 T_clock, pertanto settando tale dispositivo con gli opportuni coefficienti binari di tap avremmo che, in risposta al seme 000001, la sequenza pseudo-casuale di uscita sarebbe costituita da 378 bit.

63 = 3x3x7 = 3²x7 = = 3, = 2, = 7, = 1

Quindi:

numero dei codici C = = = 6

Pertanto il numero di G(x) primi, settabili mediante opportune combinazioni dei bit C_i di tap, sono 6 (ci sono 6 combinazioni dei valori 0/1 assegnabili alla word-line C₁…C₆ che realizzano uno G(x) primo).

In altri termini lo PNSG a 6 stadi può fornire, in risposta al seme 000001, 6 sequenze pseudo-casuali C(t) massimamente lunghe, ovvero 6 codici lunghi 378 bit.

Qui di seguito riportiamo una tabella riassuntiva dei risultati finora visti:

Il generatore da noi descritto in VHDL implementa un polinomio caratteristico G(x) non scomponibile, ed inserendo nel test bench il particolare seme sopra riportato abbiamo constatato che la periodicità della sequenza pseudo-casuale in uscita è proprio quella massima prevista, ovvero L = – 1 = – 1 = 32767 T_clock.

Delle 1800 sequenze pseudo-casuali, lunghe 32767 T_clock, che il nostro PNSG a 15 stadi può erogare, in risposta al seme 000000000000001, una per ciascuno dei 1800 G(x) primi settabili, 512 hanno una particolare proprietà: sono ortogonali nel tempo.

Ciò significa che la funzione di correlazione R_xy fra due qualsiasi di quelle 512 sequenze, per esempio fra il codice x(k) ed il codice y(k) (k = indice di bit = (1, 2, 3, …, L – 1 = 491505) ), è nulla, se x è diverso da y, cioè se la correlazione è fra due codici diversi (si parla di “cross-correlazione” minima, cioè nulla), mentre la funzione di correlazione fra un codice qualunque x(k), uno qualunque di quei 512, con se stesso, è unitaria (si parla di “auto-correlazione” massima, cioè unitaria).

Quei 512 codici formano un set di sequenze perfettamente orto-normali e si usano largamente, come vedremo, nelle comunicazioni

CDMA

Formalmente la funzione di correlazione (cross se x ≠ y, auto se x = y) R_xy(D), in funzione cioè del ritardo relativo D (= delay) fra il codice binario x(k) e quello y(k) è definita come:

R_xy(D) = = XNOR (x,y) =

bit_wise

La funzione di correlazione fra due stringhe di bit, fra due codici pseudo-casuali C ortogonali, che può essere associata ad un integrale di overlap (di sovrapposizione), ossia ad un prodotto scalare fra segnali rappresentabili come funzioni del tempo appartenenti allo spazio vettoriale di Hilbert, non è altro che una sequenza di bit data dalla somma modulo-2, eseguita bit a bit (“bit-wise”), fra la sequenza x(k) e quella y(k), con k = 1, 2, 3, …, L = – 1 = – 1 = 491505 bit.

La somma modulo-2 corrisponde, nel caso appunto di cifre binarie, all’operazione di OR esclusiva negata (NXOR = ) bit a bit, che ritorna 1 se i due bit k-esimi, uno del codice x, l’altro di quello y, sono uguali, 0 se sono diversi, come mostrato nella seguente illustrazione:

Applicazione dello PNSG progettato alle telecomunicazioni cellulari CDMA: concetti di base