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 ser representadas por los registros de desplazamiento (es decir, para registros de longitud m producen una secuencia de longitud 2 m - 1). Un 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 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 MLS incluyen la medición de respuestas de impulso (por ejemplo, de la reverberación de la sala ). También se utilizan como base para derivar secuencias pseudoaleatorias en sistemas de comunicación digitales que emplean de espectro ensanchado de secuencia directa y de espectro ensanchado por salto de frecuencia sistemas de transmisión , diseño de múltiples capas reflector dieléctrico óptico, [1] y en el diseño eficiente de algunos fMRI experimentos. [2]
Generacion
Los MLS se generan utilizando registros de desplazamiento de realimentació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 mediante la siguiente relación recursiva:
donde n es el índice de tiempo yrepresenta la suma módulo 2 . Para valores de bit 0 = FALSO o 1 = VERDADERO, esto es equivalente a la operación XOR.
Como MLS es periódico y los registros de desplazamiento recorren cada posible valor binario (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
Un polinomio sobre GF (2) se puede asociar con el registro de desplazamiento de retroalimentación lineal. Tiene el grado de la 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 + 1.
Una condición necesaria y suficiente para que la secuencia generada por un LFSR tenga la 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 2 20 - 1 muestras de longitud (1.048.575 muestras).
Propiedades de las secuencias de longitud máxima
MLS tiene las siguientes propiedades, formuladas por Solomon Golomb . [4]
Equilibrar propiedad
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 existen unos y ceros. El número de unos es igual al número de ceros más uno, ya que el estado que contiene solo ceros no puede ocurrir.
Ejecutar propiedad
Una "carrera" es una subsecuencia de "1" consecutivos o "0" consecutivos dentro del MLS en cuestión. El número de corridas es el número de tales subsecuencias. [ vago ]
De todas las "carreras" (que constan de "1" o "0") en la secuencia:
- La mitad de los recorridos tienen una longitud de 1.
- Una cuarta parte de las carreras tienen una longitud de 2.
- Una octava parte de las carreras tiene una longitud de 3.
- ... etc. ...
Propiedad de correlación
La circular de autocorrelación de un MLS es un delta de Kronecker función [5] [6] (con desviación y de retardo de tiempo, dependiendo de la implementación). Para la convención ± 1, es decir, se asigna el valor de bit 1 y valor de bit 0 , mapeando XOR al negativo del producto:
dónde representa el conjugado complejo y representa un cambio circular .
La autocorrelación lineal de un MLS se aproxima a un delta de Kronecker.
Extracción de respuestas de impulso.
Si la respuesta de impulso de un sistema invariante en el tiempo lineal (LTI) se va a medir usando 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 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 MLS es s [ n ], entonces
Tomando la correlación cruzada con respecto a s [ n ] de ambos lados,
y asumiendo que φ ss es un impulso (válido para secuencias largas)
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 en sí, 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 fuertes picos 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] 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 los 3 dB. [10]
Relación con la transformación de Hadamard
Cohn y Lempel [11] mostraron la relación de 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, Solomon 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.
- ^ Poudel, Khem Narayan; Robertson, William M. (15 de octubre de 2018). "Reflector multicapa dieléctrico de secuencia de longitud máxima" . Continuum OSA . 1 (2): 358–372. doi : 10.1364 / OSAC.1.000358 . ISSN 2578-7519 .
- ^ Buracas GT, Boynton GM (julio de 2002). "Diseño eficiente de experimentos de resonancia magnética funcional relacionados con eventos utilizando secuencias M". NeuroImage . 16 (3 Pt 1): 801-13. doi : 10.1006 / nimg.2002.1116 . PMID 12169264 .
- ^ "Registros de desplazamiento de retroalimentación lineal: implementación, propiedades de secuencia M, tablas de retroalimentación" [1] , New Wave Instruments (NW), obtenido el 2013.12.03.
- ^ Golomb, Solomon W. (1967). Secuencias de registro de cambios . 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 .
- ^ "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 obtener.
- ^ "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 está muy cerca de 1, por lo que tiene sentido usar este tipo de señal de entrada cuando necesitamos una alta relación señal / ruido para nuestra medición.
- ^ Chan, Ian H. "Chirridos sinusoidales barridos 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". IEEE Trans. Inf. Teoría . 23 (1): 135–7. doi : 10.1109 / TIT.1977.1055666 .
enlaces externos
- Bristow-Johnson, Robert. "Un pequeño tutorial de MLS" .- Breve tutorial en línea que describe cómo se usa 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 aparecer como picos espurios en la respuesta de impulso aparente.
- Jens, Jens. "Medición de la respuesta al impulso usando MLS" (PDF) .- Documento que describe la generación MLS. Contiene código C para la generación MLS utilizando hasta 18-tap-LFSR y la transformación de Hadamard correspondiente para la extracción de respuesta de impulso.
- Kerr, Wesley; Drucker, Daniel. "Creación de secuencias M" . Laboratorio Geoffrey Aguirre . Universidad de Pennsylvania.
- "Registros de desplazamiento de retroalimentación lineal" . Instrumentos New Wave. 2005. - Propiedades de secuencias de longitud máxima y tablas de retroalimentación completas para longitudes máximas de 7 a 16.777.215 (3 a 24 etapas) y tablas parciales para longitudes de hasta 4.294.967.295 (25 a 32 etapas).
- Schäfer, Magnus (octubre de 2012). "Base de datos de respuesta a impulsos de Aquisgrán" . Instituto de Sistemas de Comunicación y Procesamiento de Datos, Universidad RWTH Aachen. V1.4. Una base de datos de respuesta de impulso de habitación (binaural) generada por medio de secuencias de longitud máxima.
- "Registros de cambio eficientes, contadores LFSR y generadores de secuencia pseudoaleatoria larga - obsoletos" (PDF) . Xilinx. Julio de 1996. XAPP052 v1.1. - La implementación de lfsr en FPGA incluye una lista de tomas de 3 a 168 bits