Introducción a la Teoría de Códigos: Corrección de Errores y Compresión de Datos

A. Blanco Ferro
J. L. Doncel Juárez
J. Graña Gil
D. I. Iglesia Iglesias

Resumen

Cuando se persiguen objetivos tales como la protección contra el ruido y el uso eficiente del canal de comunicación, se hace evidente la necesidad de tratar la información de forma especial. Debido a que los problemas que surgen en la transmisión son los mismos que los del almacenamiento, la Teoría de la Información combina, en una única disciplina, los métodos destinados a conseguir esos objetivos.

Este libro está diseñado para enseñar la Teoría de la Información de una manera asequible y con gran cantidad de ejemplos a los estudiantes de ingeniería, de matemáticas y, en especial, a los de informática.

Introduciremos sólo aquellos conceptos matemáticos necesarios y justo en el momento en el que se van a aplicar. No obstante, sería de gran ayuda conocer los conceptos elementales del álgebra lineal y de la teoría de probabilidades. Conceptos más avanzados del álgebra moderna, como los de teoría de cuerpos finitos que aparecen en el capítulo 3, son resultados puramente algebraicos y se referencian a otros textos, por no ser el objetivo de éste.

Nos centraremos en dos tipos de códigos:

El diseño de códigos correctores de errores tiene como objetivo construir códigos con redundancia razonable y rápida decodificación. Debido a sus múltiples aplicaciones en ingeniería e informática, los códigos más importantes tratados aquí son:

La compresión de datos está fuertemente relacionada con los códigos correctores de errores. Ambas disciplinas se iniciaron con el artículo de Claude Shannon (1948). Por tanto, al ser relativamente recientes, no sorprende que todavía no estén arraigadas en la mayoría de las universidades. En dicho artículo se introduce el concepto de entropía como una medida de la información media contenida en un mensaje. Shannon probó que la entropía nos da una información precisa de hasta donde se puede llegar con la compresión de datos, tal como se ve en el capítulo 4.

La famosa construcción de los Códigos de Huffman, combinada con el resultado de Shannon, nos lleva hasta una sencilla ténica de compresión, descrita en el capítulo 5. El capítulo 6 describe otra técnica de compresión: la Codificación Aritmética. Al igual que la anterior, aprovecha únicamente la probabilidad de aparición de los símbolos mensaje, pero consigue resultados muy cercanos al límite impuesto por la entropía.

El programar los pasos y algoritmos aquí descritos puede ser un interesante campo de ejercicios para alguna de las asignaturas de los alumnos de informática. No obstante, además de las que aparecen en el texto, se han desarrollado varias aplicaciones relativas a los temas tratados en los diferentes capítulos. Todas ellas han sido implementadas en lenguaje C, y probadas en SunOS 4 y en el Microsoft C Optimizing Compiler para PC. Se encuentran disponibles como software libre, para lo cual el interesado deberá ponerse en contacto con los autores a través de correo electrónico.
Jorge Graña Gil / grana@dc.fi.udc.es