UABDivulga - Barcelona recerca i innovació

Los canales de comunicación digital permiten transmitir información entre puntos diferentes y se espera de ellos que la información que llega al receptor coincida con la enviada por el emisor. Desgraciadamente, muy a menudo estos medios no pueden garantizar que la información llegue intacta al receptor, debido a ruidos de diversa naturaleza. Es el caso, por ejemplo, de las llamadas con pérdida de señal. Los códigos de canal son una herramienta utilizada para la transmisión de información que permite detectar y corregir un determinado número de posibles errores producidos en la transmisión de información a través de los canales digitales.

Desde los primeros trabajos sobre teoría de la información de Claude Shannon [10] han sido muchos los esfuerzos realizados para proporcionar códigos con buenos parámetros. La investigación de códigos que fueran óptimos asintóticamente puso mucho interés en los denominados códigos algebraico-geométricos, definidos mediante curvas algebraicas y funciones sobre éstas. Resultados de gran importancia dentro de la geometría algebraica, como el teorema de Riemann-Roch, darían resultados por los parámetros de estos códigos. Un buen resumen de los códigos algebraico-geométricos y de sus propiedades asintóticas se puede encontrar en [4].

Si la geometría algebraica se hizo un lugar en la teoría de los códigos, veremos cómo la democracia también hizo su aportación. Uno de los algoritmos existentes para la detección y corrección de errores en códigos algebraico-geométricos, el algoritmo de Berlekamp-Massey-Sakata [9] se puede mejorar a partir de un proceso democrático de votaciones [2,3]. Para determinar unos valores necesarios para la descodificación se define un conjunto de votantes y cada uno de ellos apuesta por un valor. De entre todos los valores, se puede demostrar que el que realmente es válido es el más votado.

No se ha de obviar, sin embargo, que la democracia, sin querer desmerecer sus virtudes, es injusta con las minorías. Y más con aquéllas que suponen más costes. En esta línea encontramos un conjunto muy pequeño de los posibles errores del canal que requieren muchos más pasos para su corrección que el resto de errores. Del resto de errores, que son la gran mayoría, se dice que son errores genéricos [6,7]. En este trabajo hemos estudiado la corrección de los errores genéricos y hemos definido códigos por los que, al menos, la corrección de los errores genéricos está garantizada, dejando de lado los errores de la minoría más difícil de corregir. Esto permite obtener parámetros mucho más buenos.

Finalmente, en este trabajo volvemos a hacer énfasis en los semigrupos numéricos ya explicados en el artículo ¿Cómo reducir los fallos en la transmisión de datos? Las matemáticas dan la respuesta. Se demuestra cómo la conocida clase de los semigrupos numéricos de Arf [1,5,8] puede ser caracterizada en términos de los códigos que se obtienen cuando garantizamos exclusivamente la corrección de los errores genéricos. En efecto, los semigrupos de Arf son aquellos por los que se tienen los mismos requerimientos para descodificar un error de los caros que para descodificar un error genérico. Son exactamente los que no discrminan.

[1] Arf, C.: Une interprétation algébrique de la suite des ordres de multiplicité d'une branche algébrique, Proc. London Math. Soc. 50 (2), 256–287, (1948)

[2] Duursma, I.M.: Majority coset decoding, IEEE Trans. Inform. Theory 39 (3), 1067–1070, (1993)

[3] Feng, G.L., Rao, T.R.N.: Decoding algebraic-geometric codes up to the designed minimum distance, IEEE Trans. Inform. Theory 39 (1), 37–45, (1993)

[4] Høoholdt, T., van Lint, J.H., Pellikaan, R.: Algebraic geometry codes, Amsterdam: North-Holland, 871–961, (1998)

[5] Lipman, J.: Stable ideals and Arf rings, Am. J. Math. 93, 649–685, (1971)

[6] O'Sullivan, M.E.: Decoding of Hermitian codes beyond (dmin-1)/2, In Proceedings of the 1997 IEEE Int. Symp. on Inform. Theory, 384, Ulm, (1997)

[7] Pellikaan, R.: On decoding by error location and dependent sets of error positions, Discrete Math. 106/107, 369–381, (1992)

[8] Rosales, J.C., García–Sánchez, P.A., García–García, J.I., Branco, M.B.: Arf numerical semigroups, J. Algebra 276 (1), 3–12, (2004)

[9] Sakata, S.: Extension of the Berlekamp–Massey algorithm to N dimensions, Inform. Comput. 85 (2), 207–239, (1990)

[10] Shannon, C.E.: A mathematical theory of communication, Bell System Tech. J. 27, 379–423, 623–656, (1948) 2