Secuencia de longitud máxima

Tipo de secuencia binaria pseudoaleatoria

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 denominan así porque son periódicas y reproducen todas las secuencias binarias (excepto el vector cero) que pueden representarse mediante los registros de desplazamiento (es decir, para registros de longitud m producen una secuencia de longitud 2 ^m  − 1). A un MLS también se lo denomina a veces secuencia n o secuencia m . Los MLS son espectralmente planos , con la excepción de un término de CC cercano a cero.

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

Las aplicaciones prácticas de los MLS incluyen la medición de respuestas de impulsos (por ejemplo, de la reverberación de una sala o de los tiempos de llegada de fuentes remolcadas en el 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 por salto de frecuencia y de espectro ensanchado por secuencia directa , y en el diseño eficiente de algunos experimentos de fMRI . ^[2]

Generación

Figura 1: El siguiente valor del registro a ₃ en un registro de desplazamiento de retroalimentación de longitud 4 está determinado por la suma módulo 2 de a ₀ y a ₁ .

Los MLS se generan utilizando registros de desplazamiento de retroalimentación lineal máxima . En la figura 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:

${\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}}}$

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

Como los MLS son periódicos y los registros de desplazamiento recorren 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 de polinomios

Un polinomio sobre GF(2) se puede asociar con el registro de desplazamiento de retroalimentación lineal. Tiene un grado de la longitud del registro de desplazamiento y coeficientes que son 0 o 1, correspondientes a las tomas del registro que alimentan la compuerta xor . Por ejemplo, el polinomio correspondiente a la Figura 1 es . ${\displaystyle 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 usando un registro de desplazamiento de longitud 20 tiene una longitud de 2 ^{· 20}  − 1 muestras (1.048.575 muestras).

Propiedades de las secuencias de longitud máxima

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

Propiedad de equilibrio

La ocurrencia 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. La cantidad de unos es igual a la cantidad de ceros más uno, ya que no puede ocurrir el estado que contiene solo ceros. ${\displaystyle 2^{n}-1}$ ${\displaystyle 2^{n-1}}$ ${\displaystyle 2^{n-1}-1}$

Ejecutar propiedad

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

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

• La mitad de las pistas tienen una longitud de 1.
• Una cuarta parte de las pistas tienen una longitud de 2.
• Una octava parte de las pistas 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 desplazamiento 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: ${\displaystyle s=+1}$ ${\displaystyle s=-1}$

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

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

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

Extracción de respuestas de impulso

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 del sistema medida 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 un desfase cero y casi cero (−1/ N donde N es la longitud de la secuencia) para todos los demás desfases; en otras palabras, se puede decir que la autocorrelación del MLS se aproxima 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 la MLS es s [ n ], entonces

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

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

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

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

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

Cualquier señal con una autocorrelación impulsiva puede usarse para este propósito, pero las señales con un factor de cresta alto , como el impulso mismo, producen respuestas de impulso con una mala relación señal-ruido . Se asume comúnmente que el MLS sería entonces la señal ideal, ya que consta solo 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 discontinuidades agudas en la señal producen picos fuertes entre muestras, degradando el factor de cresta en 4-8 dB o más, aumentando con la longitud de la señal, haciéndolo peor que un barrido sinusoidal. ^[9] Se han diseñado otras señales 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 transformada de Hadamard

Cohn y Lempel ^[11] demostraron la relación entre la MLS y la transformada de Hadamard . Esta relación permite calcular la correlación de una MLS mediante un algoritmo rápido similar a la FFT .

Véase también

• Código de Barker
• Secuencias complementarias
• Norma federal 1037C
• Respuesta de frecuencia
• Código de oro
• Respuesta al impulso
• Anillo polinomial

Referencias

• Golomb, Solomon W.; Guang Gong (2005). Diseño de señales para una buena correlación: para comunicaciones inalámbricas, criptografía y radar. Cambridge University Press . ISBN 978-0-521-82104-9.

1. Gemba, Kay L.; Vazquez, Heriberto J.; Fialkowski, Joseph; Edelmann, Geoffrey F.; Dzieciuch, Matthew A.; Hodgkiss, William S. (octubre de 2021). "Una comparación de rendimiento entre secuencias m y barridos modulados en frecuencia lineal para la estimación del tiempo de recorrido con una fuente en movimiento". Revista de la Sociedad Acústica de América . 150 (4): 2613–2623. Bibcode :2021ASAJ..150.2613G. doi :10.1121/10.0006656. PMID  34717519. S2CID  240355915.
2. Buracas GT, Boynton GM (julio de 2002). "Diseño eficiente de experimentos de fMRI relacionados con eventos utilizando secuencias M". NeuroImage . 16 (3 Pt 1): 801–13. doi :10.1006/nimg.2002.1116. PMID  12169264. S2CID  7433120.
3. "Registros de desplazamiento de retroalimentación lineal: implementación, propiedades de secuencia M, tablas de retroalimentación"[1], New Wave Instruments (NW), consultado el 3 de diciembre de 2013.
4. Golomb, Solomon W. (1967). Secuencias de registros de desplazamiento. Holden-Day. ISBN 0-89412-048-4.
5. Jacobsen, Finn; Juhl, Peter Moller (4 de junio de 2013). Fundamentos de acústica lineal general. John Wiley & Sons. ISBN 978-1118636176Una secuencia de longitud máxima es una secuencia binaria cuya autocorrelación circular (excepto un pequeño error DC) es una función delta.
6. 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.
7. "Un pequeño tutorial sobre MLS (secuencia de longitud máxima) | dspGuru.com". dspguru.com . Consultado el 19 de mayo de 2016 . Sus valores RMS y pico son X, lo que hace que su factor de cresta (pico/RMS) sea igual a 1, el más bajo que puede alcanzar.
8. "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 alta relación señal-ruido para nuestra medición.
9. Chan, Ian H. "Swept Sine Chirps for Measuring Impulse Response" (PDF) . thinksrs.com . Consultado el 19 de mayo de 2016 . La secuencia de longitud máxima (MLS) teóricamente cumple con los requisitos porque tiene un factor de cresta matemático de 0 dB, el factor de cresta más bajo posible. Sin embargo, en la práctica, las transiciones abruptas y la reproducción limitada por el ancho de banda de la señal dan como resultado un factor de cresta de aproximadamente 8 dB
10. Friese, M. (1997-10-01). "Señales multitono con bajo factor de cresta" (PDF) . IEEE Transactions on Communications . 45 (10): 1338–1344. doi :10.1109/26.634697. ISSN  0090-6778.
11. Cohn, M.; Lempel, A. (enero de 1977). "Sobre transformadas rápidas de secuencias M". IEEE Trans. Inf. Theory . 23 (1): 135–7. doi :10.1109/TIT.1977.1055666.

Enlaces externos

• Bristow-Johnson, Robert. "Un pequeño tutorial sobre 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 del sistema pueden aparecer como picos espurios en la respuesta al impulso aparente.
• Hee, Jens. "Medición de la respuesta al impulso mediante MLS" (PDF) . — Documento que describe la generación de MLS. Contiene código C para la generación de MLS utilizando LFSR de hasta 18 tomas y la transformación de Hadamard correspondiente para la extracción de la respuesta al impulso.
• Schäfer, Magnus (octubre de 2012). "Base de datos de respuesta a impulsos de Aachen". Instituto de sistemas de comunicación y procesamiento de datos, Universidad RWTH de Aachen. V1.4.Una base de datos de respuesta de impulso de sala (binaural) generada por medio de 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 el listado de tomas de 3 a 168 bits