Hispanopedia Wiki
Articulo de referencia

Secuencia de longitud máxima

Una secuencia de longitud máxima ( MLS ) es un tipo de secuencia binaria pseudoaleatoria . Son secuencias de bits generadas mediante registros de desplazamiento con retroaliment...

Hispanopedia WikiContenido en espanolLectura gratuita

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

Son secuencias de bits generadas mediante registros de desplazamiento con retroalimentación lineal máxima , y ​​se denominan así porque son periódicas y reproducen cualquier secuencia binaria (excepto el vector cero) que puedan representar dichos registros (es decir, para registros de longitud m, generan una secuencia de longitud 2m − 1 ). Una MLS también se conoce a veces como secuencia n o secuencia m . Las MLS son espectralmente planas , con la excepción de un término de CC cercano a cero.  

Estas secuencias pueden representarse como coeficientes de polinomios primitivos [ 1 ] en un anillo de polinomios sobre Z/2Z .

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

Generación

Figura 1: El siguiente valor del registro a 3 en un registro de desplazamiento con retroalimentación de longitud 4 se determina mediante la suma módulo 2 de a 0 y a 1 .

Los MLS se generan utilizando registros de desplazamiento con 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 mediante la siguiente relación recursiva:

{a3[norte+1]=a0[norte]+a1[norte]a2[norte+1]=a3[norte]a1[norte+1]=a2[norte]a0[norte+1]=a1[norte]{\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+{\displaystyle +}representa la suma 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 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 polinómica

Un polinomio sobre GF(2) puede asociarse con el registro de desplazamiento con retroalimentación lineal. Su grado es igual a la longitud del registro de desplazamiento y sus coeficientes son 0 o 1, correspondientes a las tomas del registro que alimentan la puerta XOR . Por ejemplo, el polinomio correspondiente a la Figura 1 esincógnita4+incógnita+1{\displaystyle x^{4}+x+1}.

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

Implementación

Los MLS son económicos de implementar en hardware o software, y los registros de desplazamiento con 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 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 aparición de 0 y 1 en la secuencia debería ser aproximadamente la misma. Más precisamente, en una secuencia de longitud máxima de longitud2norte−1{\displaystyle 2^{n}-1}hay2norte−1{\displaystyle 2^{n-1}}los y2norte−1−1{\displaystyle 2^{n-1}-1}ceros. El número de unos es igual al número de ceros más uno, ya que no puede darse el estado que contiene solo ceros.

Propiedad de gestión

Una "racha" es una subsecuencia de "1" o "0" consecutivos dentro del MLS correspondiente. El número de rachas es igual al número de dichas subsecuencias.

De todas las "rachas" (que consisten en "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 desplazamiento de CC y retardo de tiempo, dependiendo de la implementación). Para la convención ±1, es decir, se asigna el valor de bit 1s=+1{\displaystyle s=+1}y valor de bit 0s=−1{\displaystyle s=-1}, mapeando XOR al negativo del producto:

R(norte)=1norte∑metro=1nortes[metro]s∗[metro+norte]norte={1si norte=0,−1nortesi 0<norte<norte.{\displaystyle R(n)={\frac {1}{N}}\sum _{m=1}^{N}s[m]\,s^{*}[m+n]_{N}={\begin{cases}1&{\text{si }}n=0,\\-{\frac {1}{N}}&{\text{si }}0<n<N.\end{cases}}}

dóndes∗{\displaystyle s^{*}}representa el conjugado complejo y[metro+norte]norte{\displaystyle [m+n]_{N}}representa un cambio circular .

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

Extracción de respuestas impulsionales

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

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

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

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

φsy=h[norte]∗φss{\displaystyle \varphi _{sy}=h[n]*\varphi _{ss}\,}

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

h[norte]=φsy.{\displaystyle h[n]=\varphi _{sy}.\,}

Cualquier señal con autocorrelación impulsiva puede usarse para este propósito, pero las señales con un alto factor de cresta , como el impulso mismo, producen respuestas de impulso con una relación señal-ruido deficiente . Se suele asumir 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 abruptas 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, lo que lo hace 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 Hadamard transformar

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 a la FFT .

Véase también

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. ↑ "Registros de desplazamiento con retroalimentación lineal: implementación, propiedades de la secuencia M, tablas de retroalimentación", New Wave Instruments (NW), consultado el 3 de diciembre de 2013.
  2. ↑ 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 m-secuencias y barridos de frecuencia modulada lineal para la estimación del tiempo de viaje con una fuente en movimiento" . The Journal of the Acoustical Society of America . 150 (4): 2613– 2623. Bibcode : 2021ASAJ..150.2613G . doi : 10.1121/10.0006656 . PMID 34717519. S2CID 240355915 .  
  3. ↑ 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 .  
  4. ↑ Golomb, Solomon W. (1967). Secuencias de registro 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 por un pequeño error de CC) es una función delta .
  6. ↑ Sarwate, DV; Pursley, MB (1980-05-01). "Propiedades de correlación cruzada de secuencias pseudoaleatorias y relacionadas". Proceedings of the IEEE . 68 (5): 593– 619. doi : 10.1109/PROC.1980.11697 . ISSN 0018-9219 . S2CID 6179951 .  
  7. ↑ "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.
  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. "Sonidos sinusoidales barridos para medir la respuesta impulsional" (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 bruscas y la reproducción de la señal limitada por el ancho de banda 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 .
  • Bristow-Johnson, Robert. "Un pequeño tutorial de MLS" .— Breve tutorial en línea que describe cómo se utiliza MLS para obtener la respuesta impulsional de un sistema lineal invariante en el tiempo . También describe cómo las no linealidades del sistema pueden manifestarse como picos espurios en la respuesta impulsional aparente.
  • Hee, Jens. "Medición de la respuesta al impulso mediante MLS" (PDF) . — Artículo que describe la generación de MLS. Contiene código C para la generación de MLS utilizando LFSR de hasta 18 coeficientes y la transformada de Hadamard correspondiente para la extracción de la respuesta impulsional.
  • Schäfer, Magnus (octubre de 2012). "Base de datos de respuesta impulsional de Aquisgrán" . Instituto de Sistemas de Comunicación y Procesamiento de Datos, Universidad RWTH de Aquisgrán. V1.4.Una base de datos de respuesta impulsional de sala (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 FPGAs incluye la lista de derivaciones para 3 a 168 bits.