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:
- Códigos correctores de error.
- Códigos usados en compresión de datos
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:
- Códigos de Hamming (códigos perfectos para
errores simples) y sus variantes, descritos en el capítulo 2.
- Códigos de Golay (código perfecto para errores triples),
descrito en el capítulo 3.
- Códigos BCH (correctores de errores múltiples) y una de
sus variantes, los códigos Reed-Solomon (correctores de errores
a ráfagas), descritos también en el capítulo 3.
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