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 simultánea (sistemas de multiemisión).

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, ${\displaystyle a_{n}[k]}$ y ${\displaystyle b_{n}[k]}$, compuestas por ${\displaystyle L}$ elementos {-1;+1}, donde ${\displaystyle L}$ es una potencia de 2 ${\displaystyle (L=2^{n})}$. Las respectivas autocorrelaciones de las secuencias ${\displaystyle a_{n}[k]}$ y ${\displaystyle b_{n}[k]}$ son:

${\displaystyle C_{aa}[i]=\sum _{k=1}^{L}a_{n}[k]a_{n}[k+i]}$

${\displaystyle 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 ${\displaystyle 2L}$:

${\displaystyle C_{aa}[i]+C_{bb}[i]=2L\delta [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, ${\displaystyle a_{n}[k]}$ y ${\displaystyle b_{n}[k]}$, existe otro par, ${\displaystyle c_{n}[k]}$ y ${\displaystyle d_{n}[k]}$, tal que la suma de las correlaciones cruzadas es completamente nula:

${\displaystyle C_{ac}[i]=\sum _{k=1}^{L}a_{n}[k]c_{n}[k+i]}$

${\displaystyle C_{bd}[i]=\sum _{k=1}^{L}b_{n}[k]d_{n}[k+i]}$

${\displaystyle C_{ac}[i]+C_{bd}[i]=0}$

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, ${\displaystyle S_{i}[k]}$, compuestas por L elementos {-1;+1}, donde M es potencia de 2 y L es potencia de M ${\displaystyle (L=M^{n};M=2^{m})}$. Las respectivas autocorrelaciones de las secuencias del conjunto son:

${\displaystyle C_{S_{1}}[i]=\sum _{k=1}^{L}S_{1}[k]S_{1}[k+i]}$

${\displaystyle C_{S_{2}}[i]=\sum _{k=1}^{L}S_{2}[k]S_{2}[k+i]}$

${\displaystyle ...}$

${\displaystyle 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 ${\displaystyle ML}$:

${\displaystyle 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 ${\displaystyle L=M^{n}}$. Sea un conjunto complementario compuesto por M secuencias de longitud L, generado con una semilla ${\displaystyle w_{1}}$:

${\displaystyle X_{w_{1},M,n}}$

Sea otro conjunto complementario compuesto por M secuencias de longitud ${\displaystyle L}$, generado con una semilla ${\displaystyle w_{2}}$:

${\displaystyle X_{w_{2},M,n}}$

Ambos conjuntos son ortogonales si se cumple que:

${\displaystyle C_{S_{1}}[i]+C_{S_{2}}[i]+...+C_{S_{M}}[i]=ML\delta [i]}$

${\displaystyle \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.

Basándose en algunas de las propiedades descritas 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:

${\displaystyle a_{0}[i]=\delta [i]}$

${\displaystyle b_{0}[i]=\delta [i]}$

${\displaystyle a_{n}[i]=a_{n-1}[i]+w_{n}[i]*b_{n-1}[i-2^{n-1}]}$

${\displaystyle 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.

• Comunicaciones por la red eléctrica (PLC, Power Line Communications).
• 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).

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