Sequenza di lunghezza massima

Una sequenza di massima lunghezza (MLS dall'inglese maximum length sequence) è un tipo di sequenza binaria pseudocasuale.

Sono anelli polinomiali generati usando registri a scorrimento a retroazione lineare massimali e sono così chiamate perché sono periodiche e riproducono qualunque sequenza binaria che può essere riprodotta tramite registri di scorrimento (per esempio per registri di lunghezza m esse producono una sequenza di lunghezza $2^{m}-1$). Una sequenza lineare massima (MLS) è chiamata qualche volta una sequenza m o una sequenza n. Le sequenze di massima lunghezza sono spettralmente piatte, con l'eccezione di un termine DC praticamente nullo.

Le applicazioni pratiche delle MLS includono la misura di risposte impulsive (risposte di riverbero nelle sale). Esse anche sono usate come base per derivare sequenze pseudo casuali nei sistemi di comunicazione digitali che impiegano sistemi di trasmissione Direct Sequence Spread Spectrum (DSSS) e Frequency-hopping spread spectrum (FHSS).

Generazione di sequenze di massima lunghezza

Le MLS sono generate usando registri a scorrimento a retroazione lineare massimali. Un sistema di generazione MLS con un registro a scorrimento di 4 bit è mostrato in Fig 1. Può essere espresso usando la seguente relazione ricorsiva:

Figura 1: Il successivo valore di registro a₃ in un registro a scorrimento con retroazione di lunghezza 4 è determinato dalla somma modulo-2 di a₀ e a₁.

$a_{k}[n+1]={\begin{cases}a_{0}[n]+a_{1}[n],&k=3\\a_{k+1}[n],&{\mbox{altrimenti}}\end{cases}}$

dove $n$ è l'indice del tempo, $k$ è la posizione all'interno del registro di bit, e + rappresenta l'addizione modulo-2.

Poiché le MLS sono periodiche e i registri di scorrimento scorrono tra tutti i possibili valori binari (con l'eccezione del vettore zero), i registri possono essere inizializzati in qualunque stato, con l'eccezione del vettore zero.

Interpretazione polinomiale

Una [polinomiale] su un campo di Galois può essere associato con registri a scorrimento a retroazione lineare. Esso ha grado pari a quello del registro di scorrimento meno uno, e ha coefficienti che sono 0 o 1, corrispondenti ai taps del registro che si comportano come una porta xor.Per esempio la polinomiale corrispondente alla figura 1 è: $x^{3}+x^{2}+1$.

Una condizione necessaria e sufficiente perché la sequenza generata dal registro di scorrimento a retroazione sia di lunghezza massimale è che la sua corrispondente polinomiale sia primitiva.

Implementazione

Le MLS sono poco costose da implementare sia in hardware che software, e registri a retroazione di ordine relativamente basso possono generare sequenze lunghe; Una sequenza generata usando un registro di scorrimento di lunghezza 20 dà $2^{20}-1$ campioni, che è approssimativamente pari 23.8 secondi se suonato come audio con tasso di campionamento a 44.1 kHz.

Proprietà delle sequenze di massima lunghezza

Le MLS hanno le seguenti proprietà, come formulate da Solomon Golomb (1967).

Proprietà di bilancio

Il numero di "1" nella sequenza è più grande del numero degli "0".

Proprietà di run

Di tutti i "run" nella sequenza di ciascun tipo (ad esempio run consistenti di "1" e run consistenti di "0")

• metà run sono di lunghezza 1.
• un quarto dei run sono di lunghezza 2.
• Un ottavo dei run sono d lunghezza 3.
• ... ecc. ...

Un "run" è una sotto-sequenza di "1" o "0" all'interno della MLS in questione; il numero di run è il numero di tali sottosequenze.

Proprietà di correlazione

La funzione di autocorrelazione di una MLS è una buona approssimazione di un treno di funzioni delta di Kronecker.

Estrazione di risposte impulsive

Se deve essere misurata la risposta di impulso di un sistema tempo invariante lineare(LTI) usando una MLS la risposta può essere estratta dall'uscita del sistema y[n] prendendo la sua cross-correlazione circolare com la sequenza MLS. Ciò avviene perché l'autocorrelazione di una MLS è 1 per zero lag e vicino a zero (−1/N dove N è la lunghezza della sequenza) per tutti gli altri lag; in altre parole, l'autocorrelazione di una MLS può dirsi avvicinarsi alla funzione impulso unitaria all'aumentare della lunghezza dell'MLS.

Se la risposta impulsiva di un sistema è h[n] e una MLS è s[n], allora

$y[n]=(h*s)[n].$

prendendo la cross correlazione rispetto a s[n] di ambo le parti,

${\phi }_{sy}=h[n]*{\phi }_{ss}$

e assumendo che φ_ss sia un impulso (valido per sequenze lunghe)

$h[n]={\phi }_{sy}.$

Relazione con la trasformata di Hadamard

Cohn and Lempel (1977) hanno mostrato la relazione delle sequenze di massima lunghezza con la trasformata di Hadamard. Questa relazione permette il calcolo della correlazione di una sequenza di massima lunghezza con un algoritmo rapido simile alla FFT.

Bibliografia

• Golomb, S. Shift Register Sequences, San Francisco, Holden-Day, 1967. ISBN 0894120484
• Cohn, M. and Lempel, A. On Fast M-Sequence Transforms,IEEE Trans. Information Theory, vol. IT-23, pp. 135–137, January, 1977.
• Solomon W. Golomb and Guang Gong Signal Design for Good Correlation: For Wireless Communication, Cryptography, and Radar, 2005. ISBN 0521821045

Voci correlate

• Anello dei polinomi
• Risposta in frequenza

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Sequenza di lunghezza massima

Collegamenti esterni

• (EN) Guide to Creation of M-Sequences, su cfn.upenn.edu.
• (EN) LFSR Reference Archiviato il 1º ottobre 2018 in Internet Archive. Properties of maximal length sequences, and comprehensive feedback tables for maximal lengths from 7 to 16,777,215 (3 to 24 stages), and partial tables for lengths up to 4,294,967,295 (25 to 32 stages).