Secuencias complementarias

Las secuencias complementarias son conjuntos de secuencias discretas utilizadas ampliamente en las más diversas áreas de la ingeniería: comunicaciones, robótica, ensayos no destructivos de materiales (NDT), etc. Sus particulares propiedades matemáticas las hacen muy atractivas para todas aquellas aplicaciones donde sea necesario recuperar una cierta información digital contenida en una señal afectada por el ruido, atenuación del canal, interferencia de otras fuentes, etc. Sus propiedades de ortogonalidad también las hacen interesantes para aplicaciones donde varias fuentes emisoras utilizan el mismo canal físico en forma simultanea (sistemas de multiemisión).

Pares de secuencias complementarias (Secuencias Golay)

La definición concreta de los pares de secuencias complementarias la establece M.J.E. Golay (Golay, 1961) relacionando la cantidad de pares de elementos iguales y desiguales en cada secuencia del par. Sin embargo la propiedad básica que las hace tan particulares se puede expresar mediante la función de autocorrelación (AC).

Sean dos secuencias, a_n[k] y b_n[k], compuestas por L elementos {-1;+1}, donde L es una potencia de 2 (L = 2ⁿ). Las respectivas autocorrelaciones de las secuencias a_n[k] y b_n[k] son:

$C_{aa}[i]=\sum_{k=1}^L a_n[k]a_n[k+i]$

$C_{bb}[i]=\sum_{k=1}^L b_n[k]b_n[k+i]$

La suma de las autocorrelaciones es una Delta de Kronecker de amplitud 2L:

C_aa[i] + C_bb[i] = 2Lδ[i]

La ausencia de lóbulos laterales de autocorrelación es una característica única que no es compartida por otros códigos o secuencias binarias, tales como los códigos Barker, las secuencias pseudoaleatorias, las secuencias Gold, y un largo etcétera.

Adicionalmente, los pares de secuencias complementarias tienen otra propiedad interesante, que es la ortogonalidad. Dado un par de secuencias complementarias, a_n[k] y b_n[k], existe otro par, c_n[k] y d_n[k], tal que la suma de las correlaciones cruzadas es completamente nula:

$C_{ac}[i]=\sum_{k=1}^L a_n[k]c_n[k+i]$

$C_{bd}[i]=\sum_{k=1}^L b_n[k]d_n[k+i]$

C_ac[i] + C_bd[i] = 0

Conjuntos de secuencias complementarias

Los conjuntos de secuencias complementarias son una generalización de los pares de secuencias complementarias o secuencias Golay. Fueron estudiados por vez primera por C.-C. Tseng y C.L. Liu (Tseng & Liu, 1972), y posteriormente ampliados por R. Sivaswamy (Sivaswamy, 1978) y R. Frank (Frank, 1980).

Sean M secuencias, S_i[k], compuestas por L elementos {-1;+1}, donde M es potencia de 2 y L es potencia de M (L = Mⁿ;M = 2^m). Las respectivas autocorrelaciones de las secuencias del conjunto son:

$C_{S_1}[i]=\sum_{k=1}^L S_1[k]S_1[k+i]$

$C_{S_2}[i]=\sum_{k=1}^L S_2[k]S_2[k+i]$

...

$C_{S_M}[i]=\sum_{k=1}^L S_M[k]S_M[k+i]$

La suma de las autocorrelaciones es una Delta de Kronecker de amplitud ML:

$C_{S_1}[i]+C_{S_2}[i]+...+C_{S_M}[i]=ML\delta[i]$

En el trabajo de Tseng y Liu (Tseng & Liu, 1972) se demuestra que hay conjuntos de secuencias complementarias tales que la suma de las correlaciones cruzadas entre las secuencias que los componen es nula. Dado un conjunto complementario compuesto por M secuencias, existen M conjuntos mutuamente ortogonales de M secuencias de longitud L = Mⁿ. Sea un conjunto complementario compuesto por M secuencias de longitud L, generado con una semilla w₁:

$X_{w_1,M,n}$

Sea otro conjunto complementario compuesto por M secuencias de longitud L, generado con una semilla w₂:

$X_{w_2,M,n}$

Ambos conjuntos son ortogonales si se cumple que:

$C_{S_1}[i]+C_{S_2}[i]+...+C_{S_M}[i]=ML\delta[i]$

$\sum_{q=1}^M\sum_{k=1}^L X_{w_1,q,n}[k]X_{w_2,q,n}[k+i]=0$

Esto es, la suma de las correlaciones cruzadas entre las secuencias de ambos conjuntos es completamente nula.

Arquitecturas de generación y correlación

Basándose en algunas de las propiedades descriptas en los trabajos de Golay, Tseng y Liu, S.Z. Budisin propuso un algoritmo y una arquitectura de generación de pares de secuencias complementarias que tiene una estructura recursiva y modular (Budisin, 1991). El algoritmo puede expresarse de la siguiente forma:

a₀[i] = δ[i]

b₀[i] = δ[i]

a_n[i] = a_{n − 1}[i] + w_n[i] * b_{n − 1}[i − 2^{n − 1}]

b_n[i] = a_{n − 1}[i] − w_n[i] * b_{n − 1}[i − 2^{n − 1}]

El algoritmo recursivo puede verse en la forma de una arquitectura lógica, tal como lo muestra la figura.

Generador de pares de secuencias complementarias (Budisin, 1991)

Aplicaciones

• Comunicaciones.
• Robótica.
• Sistemas Radar/Sonar.
• Sistemas de detección ferroviarios.
• Ensayos No Destructivos (NDT, Non Destructive Tests).
• Radares de penetración terrestre (GPR, Ground Penetration Radar).

Referencias

• Budisin, S.Z. (January 1991). «Efficient pulse compresor for Golay complementary sequences». IEE Electronics Letters 27:  pp. 219–220. 
• Frank, R.L. (November 1980). «Poliphase complementary codes». IEEE Transactions on Information Theory IT-26 (6):  pp. 641–647. 
• Golay, M.J.E. (April 1961). «Complementary series». IRE Trans. Inform. Theory IT-7:  pp. 82–87. 
• Sivaswamy, R. (September 1978). «Multiphase Complementary Codes». IEEE Transactions on Information Theory IT-24 (5):  pp. 546-552. 
• Tseng, C.-C and Liu, C.L. (September 1972). «Complementary sets of sequences». IEEE Trans. on Information Theory IT-18 (5):  pp. 644-652. 
• White, J.D.H. and Challis, R.E. (November 1992). «A Golay sequencer based NDT system for highly attenuating materials». IEE Colloquium on Non-Contacting and Remote NDT:  pp. 7/1-7/7.