Seqüència de longitud màxima

Figura 1: El següent valor del registre a₃ en un registre de desplaçament de retroalimentació de longitud 4 està determinat per la suma mòdul-2 d' un ₀ i un ₁ .

Són seqüències de bits generades mitjançant registres de desplaçament de retroalimentació lineal màxima i s'anomenen així perquè són periòdiques i reprodueixen totes les seqüències binàries (excepte el vector zero) que es poden representar pels registres de desplaçament (és a dir, per als registres de longitud m produeixen un seqüència de longitud 2^m−1). Un MLS també s'anomena de vegades una seqüència n o una seqüència m. Els MLS són espectralment plans, amb l'excepció d'un terme DC gairebé nul.^[1]

Aquestes seqüències es poden representar com a coeficients de polinomis irreductibles en un anell polinomial sobre Z/2Z.

Les aplicacions pràctiques de MLS inclouen la mesura de respostes d'impuls (per exemple, de la reverberació de l'habitació o els temps d'arribada des de fonts remolcades a l'oceà ^[2]). També s'utilitzen com a base per a la derivació de seqüències pseudoaleatòries en sistemes de comunicació digital que utilitzen sistemes de transmissió d'espectre expandit de seqüència directa i espectre expandit de salt de freqüència, i en el disseny eficient d'alguns experiments de fMRI.^[3]

Generació

Els MLS es generen mitjançant registres de desplaçament de retroalimentació lineal màxim. A la figura 1 es mostra un sistema generador de MLS amb un registre de desplaçament de longitud 4. Es pot expressar mitjançant la següent relació recursiva:

${\displaystyle {\begin{cases}a_{3}[n+1]=a_{0}[n]+a_{1}[n]\\a_{2}[n+1]=a_{3}[n]\\a_{1}[n+1]=a_{2}[n]\\a_{0}[n+1]=a_{1}[n]\\\end{cases}}}$

on n és l'índex de temps i ${\displaystyle +}$ representa l'addició mòdul 2. Per als valors de bits 0 = FALS o 1 = VERTADER, això és equivalent a l'operació XOR.

Com que els MLS són periòdics i els registres de desplaçament recorren tots els valors binaris possibles (a excepció del vector zero), els registres es poden inicialitzar a qualsevol estat, amb l'excepció del vector zero.

Interpretació polinomial

Un polinomi sobre GF(2) es pot associar amb el registre de desplaçament de retroalimentació lineal. Té el grau de longitud del registre de desplaçament, i té coeficients que són 0 o 1, corresponents a les aixetes del registre que alimenten la porta xor. Per exemple, el polinomi corresponent a la figura 1 és x⁴ + x³ + 1.

Una condició necessària i suficient perquè la seqüència generada per un LFSR tingui una longitud màxima és que el seu polinomi corresponent sigui primitiu.

Implementació

Els MLS són de baix cost d'implementar en maquinari o programari, i els registres de canvi de retroalimentació d'ordre relativament baix poden generar seqüències llargues; una seqüència generada mitjançant un registre de desplaçament de longitud 20 és 2²⁰−1 mostres de llarg (1.048.575 mostres).^[4]

Referències

1. Mathuranathan. «Maximum-length sequence (m-sequence) generator» (en anglès americà), 24-09-2018. [Consulta: 31 octubre 2023].
2. Gemba, Kay L.; Vazquez, Heriberto J.; Fialkowski, Joseph; Edelmann, Geoffrey F.; Dzieciuch, Matthew A. (en anglès) The Journal of the Acoustical Society of America, 150, 4, 10-2021, pàg. 2613–2623. Bibcode: 2021ASAJ..150.2613G. DOI: 10.1121/10.0006656. PMID: 34717519.
3. Buracas GT, Boynton GM NeuroImage, 16, 3 Pt 1, 7-2002, pàg. 801–13. DOI: 10.1006/nimg.2002.1116. PMID: 12169264.
4. «1 Maximum-Length Sequences» (en anglès). [Consulta: 31 octubre 2023].