Secuencias complementarias

Para secuencias complementarias en biología, consulte complementariedad (biología molecular) .

En matemáticas aplicadas, las secuencias complementarias ( CS ) son pares de secuencias con la útil propiedad de que sus coeficientes de autocorrelación aperiódica fuera de fase suman cero. Las secuencias complementarias binarias fueron introducidas por primera vez por Marcel JE Golay en 1949. En 1961-1962, Golay dio varios métodos para construir secuencias de longitud 2 ^N y dio ejemplos de secuencias complementarias de longitudes 10 y 26. En 1974, RJ ​​Turyn proporcionó un método para construir secuencias de longitud mn a partir de secuencias de longitudes m y n , que permite la construcción de secuencias de cualquier longitud de la forma 2 ^N10 ^K 26 ^M .

Posteriormente, la teoría de secuencias complementarias fue generalizada por otros autores a secuencias complementarias polifásicas, secuencias complementarias multinivel y secuencias complementarias complejas arbitrarias. También se han considerado conjuntos complementarios ; estos pueden contener más de dos secuencias.

Definición

Sea ( a ₀ , a ₁ , ..., a _{N  - 1} ) y ( b ₀ , b ₁ , ..., b _{N  - 1} ) ser un par de secuencias bipolares, lo que significa que a ( k ) y b ( k ) tienen valores +1 o -1. Sea la función de autocorrelación aperiódica de la secuencia x definida por

${\displaystyle R_{x}(k)=\sum _{j=0}^{N-k-1}x_{j}x_{j+k}.\,}$

Entonces el par de secuencias de una y b es complementaria si:

${\displaystyle R_{a}(k)+R_{b}(k)=2N,\,}$

para k = 0, y

${\displaystyle R_{a}(k)+R_{b}(k)=0,\,}$

para k = 1, ..., N  - 1.

O usando Kronecker delta podemos escribir:

${\displaystyle R_{a}(k)+R_{b}(k)=2N\delta (k),\,}$

Entonces podemos decir que la suma de funciones de autocorrelación de secuencias complementarias es una función delta, que es una autocorrelación ideal para muchas aplicaciones como compresión de pulsos de radar y telecomunicaciones de espectro ensanchado .

Ejemplos de

• Como ejemplo más simple tenemos secuencias de longitud 2: (+1, +1) y (+1, −1). Sus funciones de autocorrelación son (2, 1) y (2, −1), que suman (4, 0).
• Como el siguiente ejemplo (secuencias de longitud 4), tenemos (+1, +1, +1, −1) y (+1, +1, −1, +1). Sus funciones de autocorrelación son (4, 1, 0, −1) y (4, −1, 0, 1), que suman (8, 0, 0, 0).
• Un ejemplo de longitud 8 es (+1, +1, +1, -1, +1, +1, -1, +1) y (+1, +1, +1, -1, -1, -1 , +1, -1). Sus funciones de autocorrelación son (8, −1, 0, 3, 0, 1, 0, 1) y (8, 1, 0, −3, 0, −1, 0, −1).
• Un ejemplo de longitud 10 dado por Golay es (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) y (+1, +1, −1 , +1, +1, +1, +1, +1, −1, −1). Sus funciones de autocorrelación son (10, −3, 0, −1, 0, 1, −2, −1, 2, 1) y (10, 3, 0, 1, 0, −1, 2, 1, −2 , −1).

Propiedades de pares de secuencias complementarias

• Las secuencias complementarias tienen espectros complementarios. Como la función de autocorrelación y los espectros de potencia forman un par de Fourier, las secuencias complementarias también tienen espectros complementarios. Pero como la transformada de Fourier de una función delta es una constante, podemos escribir

${\displaystyle S_{a}+S_{b}=C_{S},}$

donde C _S es una constante.

S _una y S _b se definen como una magnitud al cuadrado de la transformada de Fourier de las secuencias. La transformada de Fourier puede ser una DFT directa de las secuencias, puede ser una DFT de secuencias con relleno de ceros o puede ser una transformada de Fourier continua de las secuencias que es equivalente a la transformada Z para Z = e ^{j ω} .

• Los espectros de CS tienen límites superiores. Como S _a y S _b son valores no negativos, podemos escribir

${\displaystyle S_{a}=C_{S}-S_{b}<C_{S},}$

además

${\displaystyle S_{b}<C_{S}.}$

• Si alguna de las secuencias del par CS está invertida (multiplicada por -1), siguen siendo complementarias. De manera más general, si alguna de las secuencias se multiplica por e ^{j φ} , siguen siendo complementarias;
• Si alguna de las secuencias se invierte, siguen siendo complementarias;
• Si alguna de las secuencias se retrasa, siguen siendo complementarias;
• Si las secuencias se intercambian, siguen siendo complementarias;
• Si ambas secuencias se multiplican por la misma constante (real o compleja), siguen siendo complementarias;
• Si ambas secuencias son diezmadas en el tiempo por K , siguen siendo complementarias. Más precisamente, si de un par complementario ( a ( k ), b ( k )) formamos un nuevo par ( a ( Nk ), b ( Nk )) con las muestras omitidas descartadas, entonces las nuevas secuencias son complementarias.
• Si se invierten los bits alternos de ambas secuencias, siguen siendo complementarios. En general, para secuencias complejas arbitrarias, si ambas secuencias se multiplican por e ^{j π kn / N} (donde k es una constante yn es el índice de tiempo), siguen siendo complementarias;
• Un nuevo par de secuencias complementarias puede estar formado como [ un b ] y [ un  - b ] donde [..] denota la concatenación y un y b son un par de CS;
• Se puede formar un nuevo par de secuencias como { a b } y { a  - b } donde {..} denota entrelazado de secuencias.
• Un nuevo par de secuencias se puede formar como un  +  b y un  -  b .

Par de golay

Un par complementario a , b puede codificarse como polinomios A ( z ) = a (0) + a (1) z + ... + a ( N  - 1) z ^{N −1} y de manera similar para B ( z ). La propiedad de complementariedad de las secuencias es equivalente a la condición

${\displaystyle \vert A(z)\vert ^{2}+\vert B(z)\vert ^{2}=2N\,}$

para todo z en el círculo unitario, es decir, | z | = 1. Si es así, A y B forman un par de polinomios de Golay . Los ejemplos incluyen los polinomios de Shapiro , que dan lugar a secuencias complementarias de longitud una potencia de dos .

Aplicaciones de secuencias complementarias

• Espectrometría multiluminación
• Mediciones de ultrasonido
• Medidas acústicas
• compresión de pulsos de radar
• Redes Wi-Fi ,
• Redes inalámbricas 3G CDMA
• Sistemas de comunicación OFDM
• Sistemas de detección de ruedas de tren ^{[1] [2]}
• Ensayos no destructivos (END)
• Comunicaciones
• Las máscaras de apertura codificadas se diseñan utilizando una generalización bidimensional de secuencias complementarias.

Ver también

• Código binario de Golay ( código de corrección de errores )
• Secuencias de oro
• Secuencias de Kasami
• Secuencia polifásica
• Secuencias binarias pseudoaleatorias (también llamadas secuencias de longitud máxima o secuencias M)
• Código ternario de Golay ( código de corrección de errores )
• Secuencias de Walsh-Hadamard
• Secuencia de Zadoff-Chu

Referencias

1. Donato, PG; Ureña, J .; Mazo, M .; Álvarez, F. "Detección de rueda de tren sin equipo electrónico cerca de la vía férrea". 2004. doi : 10.1109 / IVS.2004.1336500
2. JJ García; A. Hernández; J. Ureña; JC García; M. Mazo; JL Lazaro; MC Pérez; F. Álvarez. "Detección de obstáculos de bajo coste para infraestructuras ferroviarias inteligentes" . 2004.

• Golay, Marcel JE (1949). "Espectroscopía multiluminación". J. Opt. Soc. Am . 39 (6): 437–444. doi : 10.1364 / JOSA.39.000437 . PMID  18152021 .
• Golay, Marcel JE (abril de 1961). "Serie complementaria". IRE Trans. Inf. Teoría . 7 (2): 82–87. doi : 10.1109 / TIT.1961.1057620 .
• Golay, Marcel JE (1962). "Nota sobre" Serie complementaria " ". Proc. IRE . 50 : 84. doi : 10.1109 / JRPROC.1962.288278 .
• Turyn, RJ (1974). "Matrices de Hadamard, unidades de Baumert-Hall, secuencias de cuatro símbolos, compresión de pulsos y codificaciones de ondas superficiales" . J. Comb. Una teoría . 16 (3): 313–333. doi : 10.1016 / 0097-3165 (74) 90056-9 .
• Borwein, Peter (2002). Excursiones computacionales en análisis y teoría de números . Saltador. págs. 110–9. ISBN 978-0-387-95444-8.
• Donato, PG; Ureña, J .; Mazo, M .; De Marziani, C .; Ochoa, A. (2006). "Diseño y procesamiento de señales de una matriz de sensores magnéticos para la detección de ruedas de tren". Sensores y actuadores A: Físicos . 132 (2): 516–525. doi : 10.1016 / j.sna.2006.02.043 .