Codificación De Huffman

Universidad Tecnológica de la Mixteca
Instituto de Electrónica y Mecatrónica
Laboratorio de Modulación y Codificación
Práctica 1
Codificación de Huffman

1. OBJETIVO
En ésta práctica se comprobó que la codificación de Huffman, utiliza representaciones más compactas que la codificación fija, en este caso codificación ASCII (7 bits). Aplicando la codificación para dos tipos de archivo:texto e imagen.
2. INTRODUCCIÓN
La historia de la compresión se remonta a los años 1960, en el que diversos estudios sobre la teoría de la información buscaban el codificar los símbolos de la manera más eficiente posible.
Del conjunto de trabajos previos que marcaron la diferencia destaca un trabajo aparecido en los años ’50 (1948) Claude Shannon , sobre la “Teoría sobre la Comunicación” ,donde se inicia el desarrollo de la “Teoría de la Información”. Este trabajo sería el más relevante en el campo de las telecomunicaciones. En 1952, David Huffman propuso un método estadístico que permitía asignar un código binario a los diversos símbolos a comprimir (píxeles o caracteres, por ejemplo).
3. TEORÍA

La codificación Huffman es uno de los métodos clásicos de codificación de fuentede la familia de los métodos estadísticos, esto es, aquellos que necesitan conocer la distribución probabilística de la fuente.
El algoritmo básico consiste en, tras ordenar los símbolos de mayor a menor en probabilidad, ir
juntando parejas de menor probabilidad formando un árbol. Cuando solamente haya dos raíces, se asigna los símbolos 0 y 1 (o 1 y 0) a cada raíz, y se itera hacia atrás.Dada, por ejemplo, una fuente F con 5 símbolos de probabilidades {1/2, 1/4, 1/8, 1/16, 1/16} se podría construir el siguiente diagrama de árbol.

Figura 1: Representación final de la codificación de Huffman.
En cada etapa los dos elementos con menor probabilidad se unen y se obtiene un elemento resultante cuya probabilidad es la suma de las dos anteriores. Cada vez que se realiza una unión dedos elementos se asigna a cada uno de ellos un ‘1’ o un ‘0’ (el resultado dependerá de que criterio de asignación se aplique.
El proceso termina cuando únicamente quedan dos elementos y también a cada uno de ellos se le asigna un ‘1’ o un ‘0’. Finalmente para conocer el código asociado a cada probabilidad se recorre el árbol en sentido inverso y se concatenan los unos o ceros por los que se vapasando hasta llegar al principio de cada ramificación.

4. PROCEDIMIENTO

Para poder visualizar la diferencia entre estas dos codificaciones, se hizo uso del software Matlab, ya que éste software contiene funciones que realizan el algoritmo de Huffman como lo es huffmandict el cual recibe como parámetros la probabilidad y el diccionario de los símbolos mensaje. Para poder dar un veredictoobjetivo acerca de las codificaciones mencionadas, se obtuvo un valor numérico en cada uno de los métodos, el cual representa el número de bits.
El método para calcular este valor es, multiplicar la longitud de bits con el que fue codificado por la frecuencia en la que aparece el símbolo mensaje. Para el caso de la codificación de Huffman, la longitud de bits es variable, contrariamente lacodificación ASCII es fija (7 bits).
El método se aplicó a dos tipos de archivo: texto e imagen. Los símbolos mensaje para el caso de texto son los 95 caracteres ASCII imprimibles, y en el caso de la imagen será el nivel de escala de grises.

Este procedimiento se aplicará a 5 textos en idioma inglés y en 3 imágenes en escala de grises. Posteriormente se analizaron y compararon los resultados obtenidospor cada método de codificación.

5. RESULTADOS EXPERIMENTALES

Los resultados obtenidos en los cinco textos distintos se muestran en la siguiente tabla.

Número de texto | Resultado codificación Huffman | Resultado codificación |
Texto 1 | 106950 | 169680 |
Texto 2 | 72521 | 114912 |
Texto 3 | 130372 | 206591 |
Texto 4 | 135359 | 212016 |
Texto 5 | 126466 | 200557 |
Figura...