Secuencias complementarias

Pares de secuencias

Para secuencias complementarias en biología, véase complementariedad (biología molecular) . Para secuencias de números enteros con conjuntos complementarios de miembros, véase teorema de Lambek-Moser .

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 desfasada 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 dio 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 ^N 10 ^K 26 ^M .

Posteriormente, otros autores generalizaron la teoría de las secuencias complementarias a las secuencias complementarias polifásicas, secuencias complementarias multinivel y secuencias complementarias complejas arbitrarias. También se han considerado los conjuntos complementarios , que pueden contener más de dos secuencias.

Definición

Sean ( a ₀ , a ₁ , ..., a _{N  − 1} ) y ( b ₀ , b ₁ , ..., b _{N  − 1} ) 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 a y b es complementario 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 el delta de Kronecker podemos escribir:

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

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

Ejemplos

• 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 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). 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) 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 complementarios de secuencias

• 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 _a 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 rellenadas con 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 CS tienen un límite superior. Como S _a y S _b son valores no negativos, podemos escribir

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

también

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

• Si cualquiera de las secuencias del par CS se invierte (se multiplica por −1), siguen siendo complementarias. De manera más general, si cualquiera de las secuencias se multiplica por e ^{j φ,} siguen siendo complementarias;
• Si se invierte cualquiera de las secuencias, siguen siendo complementarias;
• Si alguna de las secuencias se retrasa, siguen siendo complementarias;
• Si las secuencias se intercambian siguen siendo complementarias;
• Si ambas sucesiones se multiplican por la misma constante (real o compleja) siguen siendo complementarias;
• Si se invierten bits alternos de ambas secuencias, siguen siendo complementarias. En general, para secuencias complejas arbitrarias, si ambas secuencias se multiplican por e ^{j π kn / N} (donde k es una constante y n es el índice de tiempo), siguen siendo complementarias;
• Se puede formar un nuevo par de secuencias complementarias como [ a b ] y [ a  − b ] donde [..] denota concatenación y a 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.
• Se puede formar un nuevo par de secuencias como a  +  b y a  −  b .

Pareja 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. Algunos ejemplos incluyen los polinomios de Shapiro , que dan lugar a secuencias complementarias de longitud una potencia de dos .

Aplicaciones de las secuencias complementarias

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

Véase también

• Código binario Golay ( código corrector 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 corrector de errores )
• Secuencias de Walsh-Hadamard
• Secuencia de Zadoff-Chu

Referencias

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

• Golay, Marcel JE (1949). "Espectroscopia multirranura". J. Opt. Soc. Am . 39 (6): 437–444. doi :10.1364/JOSA.39.000437. PMID  18152021.
• Golay, Marcel JE (abril de 1961). "Series complementarias". IRE Trans. Inf. Theory . 7 (2): 82–87. doi :10.1109/TIT.1961.1057620.
• Golay, Marcel JE (1962). "Nota sobre las "series complementarias"". Proc. IRE . 50 : 84. doi : 10.1109/JRPROC.1962.288278.
• Turyn, RJ (1974). "Matrices de Hadamard, unidades Baumert-Hall, secuencias de cuatro símbolos, compresión de pulsos y codificaciones de ondas superficiales". J. Comb. Theory 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. Springer. Págs. 110-119. 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 un conjunto de sensores magnéticos para la detección de ruedas de tren". Sensores y actuadores A: Física . 132 (2): 516–525. Bibcode :2006SeAcA.132..516D. doi :10.1016/j.sna.2006.02.043.