Secuencias complementarias
Las secuencias complementarias son conjuntos de secuencias discretas utilizadas ampliamente en las más diversas áreas de la ingeniería: telecomunicaciones, 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).
Pares de secuencias complementarias (secuencias de Golay)
editarLa 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, y , compuestas por elementos {-1;+1}, donde es una potencia de 2 . Las respectivas autocorrelaciones de las secuencias y son:
![{\displaystyle a_{n}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6490a21dff5b5bc8a766f43fe1b248d9a0c65448)
![{\displaystyle b_{n}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd8cf0fc3d1911e7fedfad5afdac4b62cfa9e4ae)
![{\displaystyle C_{aa}[i]=\sum _{k=1}^{L}a_{n}[k]a_{n}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19355f463ed15fe53b7db36fa3ed30bf603c17b7)
![{\displaystyle C_{bb}[i]=\sum _{k=1}^{L}b_{n}[k]b_{n}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/84051612c207e2c639183a5f8455d299f4c2659e)
La suma de las autocorrelaciones es una delta de Kronecker de amplitud :
![{\displaystyle C_{aa}[i]+C_{bb}[i]=2L\delta [i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed1636b5f7154ff93d4aa67f32a7678be5da0aa3)
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 de 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, y , existe otro par, y , tal que la suma de las correlaciones cruzadas es completamente nula:
![{\displaystyle c_{n}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/085f2286d777fb5b9a9b0d5670f73da3693ab242)
![{\displaystyle d_{n}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f0caaaa3c943cef2d86e273c67d6d934ed160b46)
![{\displaystyle C_{ac}[i]=\sum _{k=1}^{L}a_{n}[k]c_{n}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4bcd910f6cdaf25df2c5fc72c2e08052923b152f)
![{\displaystyle C_{bd}[i]=\sum _{k=1}^{L}b_{n}[k]d_{n}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddd406da605db39edd225cc07570b439cf0e2572)
![{\displaystyle C_{ac}[i]+C_{bd}[i]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eac01502f3255bd122da0cc99acd8bdad3aa6a87)
Conjuntos de secuencias complementarias
editarLos 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, , compuestas por L elementos {-1;+1}, donde M es potencia de 2 y L es potencia de M . Las respectivas autocorrelaciones de las secuencias del conjunto son:
![{\displaystyle S_{i}[k]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90c140e00fcd507fdf0710a0f77cfef65ec8ae93)
![{\displaystyle C_{S_{1}}[i]=\sum _{k=1}^{L}S_{1}[k]S_{1}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47573fdf9f025046a28c18d294399700c4847419)
![{\displaystyle C_{S_{2}}[i]=\sum _{k=1}^{L}S_{2}[k]S_{2}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ca79897c37d7911e603951ac6bde443e125cd7e)
![{\displaystyle C_{S_{M}}[i]=\sum _{k=1}^{L}S_{M}[k]S_{M}[k+i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1576c4405b2861cb6a617b3f52b399e0f4f1eab2)
La suma de las autocorrelaciones es una delta de Kronecker de amplitud :
![{\displaystyle C_{S_{1}}[i]+C_{S_{2}}[i]+...+C_{S_{M}}[i]=ML\delta [i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0447d95cb8eda9f32c60e1b49843cf7c206d21be)
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 . Sea un conjunto complementario compuesto por M secuencias de longitud L, generado con una semilla :
Sea otro conjunto complementario compuesto por M secuencias de longitud , generado con una semilla :
Ambos conjuntos son ortogonales si se cumple que:
![{\displaystyle \sum _{q=1}^{M}\sum _{k=1}^{L}X_{w_{1},q,n}[k]X_{w_{2},q,n}[k+i]=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fa2d513a080b3ef91056df038b8ee0104b4866a)
Esto es, la suma de las correlaciones cruzadas entre las secuencias de ambos conjuntos es completamente nula.
Arquitecturas de generación y correlación
editarBasá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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad39a383b55214df34969b6e80909b4d805ce0d2)
![{\displaystyle b_{0}[i]=\delta [i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e1951780f698914b19840ae65bfb4b4fbbf3852)
![{\displaystyle a_{n}[i]=a_{n-1}[i]+w_{n}[i]*b_{n-1}[i-2^{n-1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88f13ecb66fb3b914529ca339522a9f101c331a1)
![{\displaystyle b_{n}[i]=a_{n-1}[i]-w_{n}[i]*b_{n-1}[i-2^{n-1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1722ed968f93ae2d331e8d5902a1ec142d29449c)
El algoritmo recursivo puede verse en la forma de una arquitectura lógica, tal como lo muestra la figura.
Aplicaciones
editar- 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).
Referencias
editar- 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.
Datos: Q5156430
