Codificacion huffman

UNIVERSIDAD AUTóNOMA DE CIUDAD JUáREZ |
CÓDIGOS HUFFMAN |
Teoría de la Información |
Maestría en Ciencias en Ingeniería Eléctrica |
Rosa Isela Ochoa Carrillo |
21 de Marzo del 2010 |

|

Contenido
Capitulo 1 Introducción………………………………………………………………….. 3
Capitulo 2 Conceptos de Teoría de la Información………………………………… 5
2.1. Información y Entropía 5
2.2. Propiedad Asintótica deEquipartición AEP 6
2.3. Cadenas de Markov 6
Capitulo 3 Conceptos generales para la codificación de datos………………… 8
3.1. Codificación 8
3.2. Clasificación y propiedades de los códigos 8
3.3. Desigualdad de Kraft 12
3.4. Códigos Óptimos 12
Capitulo 4 Códigos para compresión de datos……………………………………… 14
4.1. Introducción a las técnicas de compresión 14
4.2. Técnicas decompresión estadísticas. 15
Capitulo 5 Códigos Huffman………………………………………………………….… 16
5.1. Definición del código Huffman 16
5.2. Optimización de los códigos Huffman 17
5.3 Codigos Huffman de D bits 17
Capitulo 6 Aplicaciones Prácticas……………………………………………………….19
6.1 Compresión de imágenes usando la transformada de wavelet y el algoritmo
de Huffman

Conclusiones………………………………………………………………………………..20
Bibliografía …………………………………………………………………………………..21

Capitulo 1 Introducción
En 1951, David Huffman era de la clase de asignatura “Teoría de la información”, en la cual se les permitió optar entre la realización de un examen final o un trabajo. El profesor de la asignatura, Robert M. Fano asigno el trabajo el cual consistía en encontrar el código binario más eficiente. Huffman,ante la imposibilidad de demostrar que código era más eficiente, se rindió y decidió comenzar a estudiar para su examen final. Mientras estudiaba se le vino a la mente la idea de usar arboles binarios de frecuencia ordenada con la cual probaba que este era el método más eficiente.

David A. Huffman
La codificación de Huffman es una técnica para la compresión de datos ampliamente usada y muyefectiva. Este algoritmo le asigna secuencias binarias (códigos) a los símbolos de un alfabeto de forma tal de utilizar la menor cantidad de bits posibles. El algoritmo de Huffman es utilizado para la construcción de códigos de Huffman, desarrollado en 1952 cuando Huffman era estudiante de Doctorado en MIT y explicado en A Method for the Construction of Minimum-Redundancy Code[1]. La codificaciónHuffman usa un método específico para elegir la representación de cada símbolo, que da lugar a un código prefijo (es decir, ningún código es prefijo de otro) que representa los caracteres más comunes usando las cadenas de bits más cortas y viceversa. La idea del algoritmo de Huffman es que los datos a ser comprimidos contienen símbolos que aparecen con mayor frecuencia y otros que aparecen muy poco,asignándole un código más corto a los que más aparecen. Este algoritmo toma un alfabeto de n símbolos, junto con sus frecuencias de aparición asociadas, y produce un código de Huffman para ese alfabeto y esas frecuencias.

Capitulo 2 Conceptos de Teoría de la información
La información que transmite un mensaje no está relacionada con su longitud. Podemos tener dos mensajes con distintalongitud y que transmitan la misma información. El concepto de información está muy relacionado con el concepto de probabilidad. Cuanto más probable es un mensaje menos información contiene.

2.1 Información y Entropía
La teoría de la Información es la máxima compresión de datos (la entropía) y la tasa máxima de transmisión de datos (la capacidad del canal C). La teoría de información tambiénsugiere los medios para alcanzar estos límites de comunicación.
En nuestro caso contamos con los símbolos de un alfabeto fuente que son transmitidos por el emisor. Cada uno de estos símbolos tiene asociada una probabilidad. El contenido en información de cada uno de los símbolos se define como:

Las unidades son bits de información. Un concepto muy ligado al de cantidad de...