Registro a scorrimento a retroazione lineare

Il registro a scorrimento a retroazione lineare (linear feedback shift register, LFSR) è una tipologia di registri di traslazione i cui dati in ingresso sono prodotti da una funzione lineare dello stato interno.

Le uniche funzioni lineari di singoli bit sono lo XOR e lo XNOR (xor inverso); perciò è un registro di traslazione i cui bit in ingresso sono prodotti dall'or esclusivo (xor) di alcuni bit memorizzati all'interno dei registri.

Il valore iniziale di un LFSR è chiamato seme, e poiché l'operazione del registro è deterministica, la sequenza di valori prodotta dal registro è completamente determinata dal suo stato corrente o precedente. Allo stesso modo, poiché il registro ha un numero finito di stati possibili, prima o poi i valori in uscita si ripetono; ciò nonostante, un LFSR con una funzione di retroazione ben scelta può produrre una sequenza di bit che appare casuale ed ha un periodo molto lungo.

Applicazioni degli LFSR includono la generazione di numeri pseudo-casuali, sequenze pseudo-rumore (approssimazione del rumore bianco) e contatori digitali. Sono comuni implementazioni sia in hardware che in software.

Come funziona modifica

La lista di posizioni dei bit che influenza lo stato successivo è detta sequenza di tap. Nel diagramma sottostante, la sequenza è [16,14,13,11].

Le uscite che influenzano l'ingresso sono dette tap (in blu nel diagramma sottostante).
Un LFSR massimale produce una sequenza-n (cioè passa attraverso tutti i possibili stati del registro di traslazione tranne quello che produce tutti zeri), a meno che il suo stato iniziale non sia composto solo di zeri, nel qual caso l'uscita resta costante.

La sequenza di numeri prodotta da un LFSR può essere considerata un sistema numerico binario valido quanto il codice Gray o il codice binario naturale.

La sequenza di tap di un LFSR può essere rappresentata come un polinomio modulo 2. Questo significa che i coefficienti del polinomio devono essere 1 o 0. Questo è noto come polinomio di retroazione o polinomio caratteristico. Ad esempio, se i tap sono al 16º, 14º, 13º e 11º bit (come sotto), il polinomio LFSR relativo è

x^{11}+x^{13}+x^{14}+x^{16}+1

Il termine noto del polinomio ("l'uno") non corrisponde a un tap; le potenze dei termini rappresentano i bit a tap, contando dalla sinistra.

Se (e solo se) questo polinomio è primitivo, allora l'LFSR è massimale
L'LFSR sarà massimale solo se il numero di tap è pari
I valori dei tap in un LFSR massimale saranno primi tra loro (due numeri si dicono primi tra loro se il loro massimo comun divisore è 1)
Ci può essere più di una sequenza di tap che rende massimale un LFSR di lunghezza fissata
Una volta trovata una sequenza di tap massimale, se ne può trovare un'altra con un procedimento automatico: se la sequenza di tap, in un LFSR a n bit, è [n,A,B,C], la sua sequenza "speculare" è [n,n-A,n-B,n-C] (ad esempio la sequenza [32,3,2,1] ha come controparte [32,31,30,29]). Entrambe producono un LFSR massimale.

Proprietà della sequenza di uscita modifica

Uni e zeri si susseguono in corse (runs). La sequenza di uscita 0110100, ad esempio, è composta da cinque corse di lunghezza 1,2,1,1,2, rispettivamente. In un periodo di un LFSR massimale, appaiono $2^{n-1}$ corse (ad esempio, un LFSR a 6 bit avrà 32 corse); esattamente $1/2$ di queste corse saranno di un bit, $1/4$ di 2 bit, fino ad un'unica corsa di $n-1$ bit a zero, ed un'unica corsa di $n$ bit a uno. Questa stessa proprietà ci si aspetterebbe in una sequenza veramente casuale.
Le sequenze di uscita degli LFSR sono deterministiche: se si conosce lo stato attuale, si può prevedere il prossimo. Questo non è possibile in eventi veramente casuali come il decadimento radioattivo.

Applicazioni modifica

Gli LFSR possono essere implementati in hardware, e ciò li rende utili in applicazioni che richiedono la generazione molto rapida di numeri pseudo-casuali, come nella tecnica radio Direct Sequence Spread Spectrum, usata ad esempio nell'UMTS.

Il Global Positioning System (GPS) usa gli LFSR per trasmettere rapidamente una sequenza che indica degli istanti relativi ad alta precisione, sfruttandone il determinismo: basta infatti trasmettere il seme utilizzato nel trasmettitore e la sequenza generata sarà identica anche sul ricevitore.

Possibile sostituto dei codici Gray modifica

Alcune applicazioni hanno bisogno di marchiare delle singole posizioni ad una certa distanza con valori unici. Ad esempio, molti metri segnano ogni centimetro con un numero unico usando il sistema metrico decimale. Quando gli indici e le posizioni devono essere comprensibili ad una macchina, sono spesso marchiate usando sequenze LFSR, in quanto i contatori LFSR sono i più semplici e veloci tra i contatori binari, anche più dei contatori basati su codice Gray. Data una sequenza di output è possibile costruire un LFSR di dimensione minima usando l'algoritmo Berlekamp-Massey.

LFSR di Galois modifica

Un LFSR di Galois, o un LFSR in configurazione di Galois, è una variante dello schema classico degli LFSR.

Nella configurazione di Galois, quando il sistema è soggetto a clock, i bit che non sono tap sono traslati come di consueto; dei tap, invece, si fa lo XOR con la nuova uscita, e il risultato poi diventa il nuovo ingresso.

Gli LFSR di Galois non concatenano ogni tap per produrre il nuovo ingresso, perciò è possibile calcolare i tap in parallelo, aumentando così la velocità di esecuzione: l'operazione di XOR è realizzata nell'LFSR e non ci sono XOR in serie, perciò i tempi di propagazione si riducono a quelli di uno XOR invece di quelli di una catena degli stessi.

Utilizzo in crittografia modifica

Gli LFSR sono componenti molto utilizzati nei cifrari a flusso come generatori di numeri pseudo-casuali, perché possono essere facilmente ed economicamente implementati in hardware e possono all'occorrenza essere analizzati matematicamente. L'uso degli LFSR da soli, però, è insufficiente a fornire una buona sicurezza. Molti schemi sono stati proposti per incrementare la sicurezza degli LFSR.

Funzioni combinatorie non lineari modifica

Poiché gli LFSR sono intrinsecamente lineari, una tecnica per rimuovere la linearità consiste nell'applicare ai risultati di più LFSR in parallelo una funzione booleana non lineare e formare un generatore di combinazioni. Diverse proprietà di queste funzioni combinatorie sono critiche per assicurare la sicurezza dello schema risultante, ad esempio, in modo da evitare attacchi basati sulla correlazione.

Generatori controllati dal clock modifica

Normalmente gli LFSR eseguono passi regolari. Un approccio per introdurre delle non-linearità consiste nell'usare per lo LFSR un clock irregolare, controllato dall'uscita di un secondo LFSR. Tali generatori comprendono il generatore stop-and-go, il generatore a passo alternato e il generatore a rimpicciolimento.

Il generatore stop-and-go (Beth and Piper, 1984) è composto da due LFSR. Un LFSR ha un colpo di clock se l'uscita del secondo è un "1", altrimenti ripete la sua uscita precedente. Questa uscita è poi (in alcune versioni) combinata con l'uscita di un terzo LFSR con clock regolare.

Il generatore a rimpicciolimento ha un approccio differente. Usa due LFSR, entrambi con clock regolare. Se l'uscita del primo LFSR è "1", l'uscita del secondo LFSR è l'output del generatore. Se il primo LFSR produce uno "0", però, l'uscita del secondo è scartata, e il generatore non produce bit. Questo meccanismo è vulnerabile agli attacchi temporizzati sul secondo generatore, poiché la velocità dell'output è variabile in dipendenza dello stato del secondo generatore. Questo problema può essere alleviato mantenendo una porzione dell'uscita in un buffer.