Secuencia de longitud máxima

Una secuencia de longitud máxima ( MLS ) es un tipo de secuencia binaria pseudoaleatoria .

Son secuencias de bits generadas utilizando registros de desplazamiento de retroalimentación lineal máxima y se llaman así porque son periódicas y reproducen cada secuencia binaria (excepto el vector cero) que puede representarse mediante los registros de desplazamiento (es decir, para registros de longitud m producen un secuencia de longitud 2 ^m − 1). Una MLS a veces también se denomina secuencia n o secuencia m . Los MLS son espectralmente planos , con la excepción de un término DC cercano a cero.

Estas secuencias se pueden representar como coeficientes de polinomios irreducibles en un anillo polinomial sobre Z/2Z .

Las aplicaciones prácticas de MLS incluyen la medición de respuestas de impulso (por ejemplo, de la reverberación ambiental o los tiempos de llegada de fuentes remolcadas al océano ^[1] ). También se utilizan como base para derivar secuencias pseudoaleatorias en sistemas de comunicación digital que emplean sistemas de transmisión de espectro ensanchado de secuencia directa y espectro ensanchado por salto de frecuencia , y en el diseño eficiente de algunos experimentos de resonancia magnética funcional. ^[2]

Generación

Los MLS se generan utilizando registros de desplazamiento de retroalimentación lineal máxima . En la Fig. 1 se muestra un sistema generador de MLS con un registro de desplazamiento de longitud 4. Se puede expresar utilizando la siguiente relación recursiva:

{\begin{casos}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{casos}}

donde n es el índice de tiempo y representa la suma de módulo 2 . Para valores de bits 0 = FALSO o 1 = VERDADERO, esto es equivalente a la operación XOR. $+$

Como los MLS son periódicos y los registros de desplazamiento pasan por todos los valores binarios posibles (con la excepción del vector cero), los registros se pueden inicializar en cualquier estado, con la excepción del vector cero.

Interpretación polinomial

Se puede asociar un polinomio sobre GF(2) con el registro de desplazamiento de retroalimentación lineal. Tiene un grado de longitud del registro de desplazamiento y tiene coeficientes que son 0 o 1, correspondientes a las derivaciones del registro que alimentan la puerta xor . Por ejemplo, el polinomio correspondiente a la Figura 1 es . $x^{4}+x+1$

Una condición necesaria y suficiente para que la secuencia generada por un LFSR tenga longitud máxima es que su polinomio correspondiente sea primitivo . ^[3]

Implementación

Los MLS son económicos de implementar en hardware o software, y los registros de desplazamiento de retroalimentación de orden relativamente bajo pueden generar secuencias largas; una secuencia generada utilizando un registro de desplazamiento de longitud 20 tiene una longitud de 2 · ²⁰ − 1 muestras (1.048.575 muestras).

Propiedades de secuencias de longitud máxima.

MLS tiene las siguientes propiedades, según lo formulado por Solomon Golomb . ^[4]

Propiedad de equilibrio

La aparición de 0 y 1 en la secuencia debe ser aproximadamente la misma. Más precisamente, en una secuencia de longitud máxima hay unos y ceros. El número de unos es igual al número de ceros más uno, ya que el estado que contiene sólo ceros no puede ocurrir. $2^{n}-1$ $2^{n-1}$ $2^{n-1}-1$

Ejecutar propiedad

Una "ejecución" es una subsecuencia de "1" o "0" consecutivos dentro del MLS en cuestión. El número de ejecuciones es el número de dichas subsecuencias. ^{[ impreciso ]}

De todas las "ejecuciones" (que constan de "1" o "0") en la secuencia:

La mitad de las carreras tienen una longitud de 1.
Una cuarta parte de las carreras tienen una longitud de 2.
Una octava parte de las carreras tienen una longitud de 3.
... etc. ...

Propiedad de correlación

La autocorrelación circular de un MLS es una función delta de Kronecker ^[5]^[6] (con compensación de CC y retardo de tiempo, según la implementación). Para la convención ±1, es decir, se asigna el valor de bit 1 y el valor de bit 0 , asignando XOR al negativo del producto: $s=+1$ $s=-1$

$R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N} ={\begin{casos}1&{\text{si }}n=0,\\-{\frac {1}{N}}&{\text{si }}0<n<N.\end{casos }}$

donde representa el conjugado complejo y representa un desplazamiento circular . $s^{*}$ $[m+n]_{N}$

La autocorrelación lineal de un MLS se aproxima a un delta de Kronecker.

Extracción de respuestas impulsivas.

Si se va a medir la respuesta al impulso de un sistema lineal invariante en el tiempo (LTI) utilizando un MLS, la respuesta se puede extraer de la salida medida del sistema y [ n ] tomando su correlación cruzada circular con el MLS. Esto se debe a que la autocorrelación de un MLS es 1 para el retraso cero y casi cero (−1/ N donde N es la longitud de la secuencia) para todos los demás retrasos; en otras palabras, se puede decir que la autocorrelación del MLS se acerca a la función de impulso unitario a medida que aumenta la longitud del MLS.

Si la respuesta al impulso de un sistema es h [ n ] y el MLS es s [ n ], entonces

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

Tomando la correlación cruzada con respecto a s [ n ] de ambos lados,

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

y suponiendo que φ _ss es un impulso (válido para secuencias largas)

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

Para este propósito se puede utilizar cualquier señal con una autocorrelación impulsiva, pero las señales con un factor de cresta alto , como el propio impulso, producen respuestas impulsivas con una relación señal-ruido deficiente . Generalmente se supone que MLS sería entonces la señal ideal, ya que consta únicamente de valores de escala completa y su factor de cresta digital es el mínimo, 0 dB. ^[7]^[8] Sin embargo, después de la reconstrucción analógica , las marcadas discontinuidades en la señal producen fuertes picos entre muestras, degradando el factor de cresta entre 4 y 8 dB o más, aumentando con la longitud de la señal, haciéndolo peor que un barrido sinusoidal. ^[9] Otras señales se han diseñado con un factor de cresta mínimo, aunque se desconoce si se puede mejorar más allá de 3 dB. ^[10]

Relación con la transformación de Hadamard

Cohn y Lempel ^[11] mostraron la relación del MLS con la transformada de Hadamard . Esta relación permite calcular la correlación de un MLS en un algoritmo rápido similar al FFT .

Ver también

Referencias

Golomb, Salomón W.; Guang Gong (2005). Diseño de señales para una buena correlación: para comunicación inalámbrica, criptografía y radar. Prensa de la Universidad de Cambridge . ISBN 978-0-521-82104-9.

^ Gemba, Kay L.; Vázquez, Heriberto J.; Fialkowski, José; Edelmann, Geoffrey F.; Dzieciuch, Mateo A.; Hodgkiss, William S. (octubre de 2021). "Una comparación de rendimiento entre secuencias m y barridos lineales de frecuencia modulada para la estimación del tiempo de viaje con una fuente en movimiento". La Revista de la Sociedad de Acústica de América . 150 (4): 2613–2623. Código Bib : 2021ASAJ..150.2613G. doi :10.1121/10.0006656. PMID 34717519. S2CID 240355915.
^ Buracas GT, Boynton GM (julio de 2002). "Diseño eficiente de experimentos de resonancia magnética funcional relacionados con eventos utilizando secuencias M". NeuroImagen . 16 (3 partes 1): 801–13. doi :10.1006/nimg.2002.1116. PMID 12169264. S2CID 7433120.
^ "Implementación de registros de desplazamiento de retroalimentación lineal, propiedades de secuencia M, tablas de retroalimentación" [1], New Wave Instruments (NW), obtenido el 3 de diciembre de 2013.
^ Golomb, Salomón W. (1967). Secuencias de registros de desplazamiento. Holden-Day. ISBN 0-89412-048-4.
^ Jacobsen, finlandés; Juhl, Peter Moller (4 de junio de 2013). Fundamentos de Acústica Lineal General. John Wiley e hijos. ISBN 978-1118636176. Una secuencia de longitud máxima es una secuencia binaria cuya autocorrelación circular (excepto por un pequeño error de CC) es una función delta.
^ Sarwate, DV; Pursley, MB (1 de mayo de 1980). "Propiedades de correlación cruzada de secuencias pseudoaleatorias y relacionadas". Actas del IEEE . 68 (5): 593–619. doi :10.1109/PROC.1980.11697. ISSN 0018-9219. S2CID 6179951.
^ "Un pequeño tutorial de MLS (secuencia de longitud máxima) | dspGuru.com". dspguru.com . Consultado el 19 de mayo de 2016 . sus valores RMS y pico son ambos X, lo que hace que su factor de cresta (pico/RMS) sea igual a 1, el más bajo que puede alcanzar.
^ "Otras técnicas de medición electroacústica". www.clear.rice.edu . Consultado el 19 de mayo de 2016 . El factor de cresta para MLS es muy cercano a 1, por lo que tiene sentido utilizar este tipo de señal de entrada cuando necesitamos una relación señal-ruido alta para nuestra medición.
^ Chan, Ian H. "Chirridos sinusoidales de barrido para medir la respuesta al impulso" (PDF) . thinksrs.com . Consultado el 19 de mayo de 2016 .
^ Friese, M. (1 de octubre de 1997). "Señales multitono con factor de cresta bajo" (PDF) . Transacciones IEEE sobre Comunicaciones . 45 (10): 1338-1344. doi : 10.1109/26.634697. ISSN 0090-6778.
^ Cohn, M.; Lempel, A. (enero de 1977). "Sobre transformaciones rápidas de secuencia M". Traducción IEEE. inf. Teoría . 23 (1): 135–7. doi :10.1109/TIT.1977.1055666.

enlaces externos

Bristow-Johnson, Robert. "Un pequeño tutorial de la MLS".— Breve tutorial en línea que describe cómo se utiliza MLS para obtener la respuesta al impulso de un sistema lineal invariante en el tiempo . También describe cómo las no linealidades en el sistema pueden manifestarse como picos espurios en la aparente respuesta al impulso.
Je, Jens. "Medición de respuesta al impulso mediante MLS" (PDF) . — Artículo que describe la generación MLS. Contiene código C para la generación de MLS utilizando hasta LFSR de 18 derivaciones y una transformada de Hadamard coincidente para la extracción de respuesta al impulso.
Schäfer, Magnus (octubre de 2012). "Base de datos de respuesta al impulso de Aquisgrán". Instituto de Sistemas de Comunicación y Procesamiento de Datos, Universidad RWTH Aachen. V1.4.Una base de datos de respuesta al impulso espacial (binaural) generada mediante secuencias de longitud máxima.
"Registros de desplazamiento eficientes, contadores LFSR y generadores de secuencias pseudoaleatorias largas: obsoletos" (PDF) . Xilinx. Julio de 1996. XAPP052 v1.1.— La implementación de lfsr en FPGA incluye una lista de derivaciones de 3 a 168 bits