Secvența lungimii maxime

O secvență de lungime maximă ( MLS din secvența de lungime maximă engleză ) este un tip de secvență binară pseudorandom .

Acestea sunt inele polinomiale generate folosind registre de deplasare cu feedback liniar maxim și se numesc așa deoarece sunt periodice și reproduc orice secvență binară care poate fi reprodusă prin registre de deplasare (de exemplu pentru registrele de lungime m produc o secvență de lungime $2^{m}-1$ ${\ displaystyle 2 ^ {m} -1}$ ${\ displaystyle 2 ^ {m} -1}$ ). O secvență liniară maximă (MLS) este uneori numită secvență m sau secvență n . Secvențele de lungime maximă sunt spectral plate, cu excepția unui termen DC practic zero.

Aplicațiile practice ale MLS includ măsurarea răspunsurilor la impulsuri (răspunsuri de reverberație în camere). Ele sunt, de asemenea, utilizate ca bază pentru derivarea secvențelor pseudo-aleatorii în sistemele de comunicații digitale utilizând sisteme de transmisie Direct Sequence Spread Spectrum (DSSS) și Frequency Hopping Broad Spectrum (FHSS).

Generarea de secvențe de lungime maximă

MLS-urile sunt generate folosind registre maxime de deplasare a feedback-ului liniar . Un sistem de generare MLS cu un registru de schimbare pe 4 biți este prezentat în Fig 1. Acesta poate fi exprimat folosind următoarea relație recursivă:

Figura 1: Următoarea valoare de registru la ₃ într-un registru de schimbare de feedback de lungime 4 este determinată de suma modulo-2 a unui ₀ și a ₁ .

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

{\ displaystyle a_ {k} [n + 1] = {\ begin {cases} a_ {0} [n] + a_ {1} [n], & k = 3 \\ a_ {k + 1} [n] , și {\ mbox {altfel}} \ end {cases}}}

{\ displaystyle a_ {k} [n + 1] = {\ begin {cases} a_ {0} [n] + a_ {1} [n], & k = 3 \\ a_ {k + 1} [n] , și {\ mbox {altfel}} \ end {cases}}}

unde este $n$ ${\ displaystyle n}$ $n$ este indicele timpului, $k$ ${\ displaystyle k}$ $k$ este poziția din registrul de biți și + reprezintă adunarea modulo-2.

Deoarece MLS-urile sunt periodice și registrele de deplasare parcurg toate valorile binare posibile (cu excepția vectorului zero), registrele pot fi inițializate în orice stare, cu excepția vectorului zero.

Interpretare polinomială

Un [polinom] pe un câmp Galois poate fi asociat cu registre de deplasare de feedback liniar . Are un grad egal cu cel al registrului de deplasare minus unul și are coeficienți care sunt 0 sau 1, corespunzător robinetelor registrului care se comportă ca o poartă xor . De exemplu, polinomul corespunzător figurii 1 este: $x^{3}+x^{2}+1$ ${\ displaystyle x ^ {3} + x ^ {2} +1}$ ${\ displaystyle x ^ {3} + x ^ {2} +1}$ .

O condiție necesară și suficientă pentru ca secvența generată de registrul de schimbare a feedback-ului să aibă lungimea maximă este ca polinomul său corespunzător să fie primitiv.

Implementare

MLS-urile sunt ieftine de implementat atât în hardware, cât și în software, iar registrele de feedback relativ reduse pot genera secvențe lungi; O secvență generată folosind un registru de deplasare de lungime 20 dă $2^{20}-1$ ${\ displaystyle 2 ^ {20} -1}$ ${\ displaystyle 2 ^ {20} -1}$ eșantioane, care este de aproximativ 23,8 secunde atunci când este redat ca sunet de frecvență de eșantionare de 44,1 kHz.

Proprietățile secvențelor de lungime maximă

MLS au următoarele proprietăți, după cum a fost formulat de Solomon Golomb ( 1967 ).

Proprietate bugetară

Numărul de „1s” din secvență este mai mare decât numărul de „0s”.

Rulați proprietatea

Dintre toate "rulările" din secvența fiecărui tip (de exemplu, rulările constând din "1" și rulările constând din "0")

jumătatea alergărilor are lungimea 1.
un sfert din alergări au o lungime de 2.
O optime din alergări au lungimea d 3.
... etc. ...

O „alergare” este o subsecvență „1” sau „0” în cadrul MLS în cauză; numărul de rulări este numărul de astfel de subsecvențe.

Proprietatea de corelație

Funcția de autocorelare a unui MLS este o bună aproximare a unui tren de funcții delta Kronecker .

Extragerea răspunsurilor impulsive

Dacă răspunsul la impuls al unui sistem liniar de invariant în timp (LTI) urmează să fie măsurat utilizând un MLS, răspunsul poate fi extras din ieșirea sistemului y [ n ] luând corelația sa transversală circulară ca secvență MLS. Acest lucru se întâmplă deoarece autocorelația unui MLS este 1 pentru zero lag și aproape de zero (−1 / N unde N este lungimea secvenței) pentru toate celelalte lag; cu alte cuvinte, se poate spune că autocorelația unui MLS se apropie de funcția impulsului unitar pe măsură ce lungimea MLS crește.

Dacă răspunsul la impuls al unui sistem este h [ n ] și un MLS este s [ n ], atunci

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

{\ displaystyle y [n] = (h * s) [n].}

{\ displaystyle y [n] = (h * s) [n].}

luând corelația încrucișată față de s [ n ] de ambele părți,

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

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

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

și presupunând că φ _ss este un impuls (valabil pentru secvențe lungi)

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

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

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

Relația cu transformarea Hadamard

Cohn și Lempel ( 1977 ) au arătat relația secvențelor de lungime maximă cu transformata Hadamard . Această relație permite calcularea corelației unei secvențe de lungime maximă cu un algoritm rapid similar cu FFT .

Bibliografie

Golomb, S. Shift Register Sequences , San Francisco, Holden-Day, 1967. ISBN 0894120484
Cohn, M. și Lempel, A. On Fast M-Sequence Transforms , IEEE Trans. Teoria informației, vol. IT-23, pp. 135–137, ianuarie 1977.
Solomon W. Golomb și Guang Gong Signal Design pentru o bună corelație: pentru comunicații fără fir, criptografie și radar , 2005. ISBN 0521821045

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe secvența de lungime maximă

linkuri externe

( EN ) Ghid pentru crearea secvențelor M , la cfn.upenn.edu .
( EN ) Proprietăți de referință LFSR ale secvențelor de lungime maximă și tabele complete de feedback pentru lungimi maxime de la 7 la 16.777.215 (3 până la 24 de etape) și tabele parțiale pentru lungimi de până la 4.294.967.295 (25 până la 32 de etape).

Portal IT : accesați intrările Wikipedia care se ocupă cu IT