Huffman, Hamming

Códigos Huffman, Hamming y relación entre

ellos.

Código Huffman

El Código Huffman es un algoritmo para la compresión de archivos sin pérdida de datos desarrollado por

David Huffman. Para llevar a cabo dicha compresión, se debe basar principalmente en la frecuencia de

ocurrencia de un símbolo en un archivo que será comprimido.

Este algoritmo, está basado en codificación estadística, lo que significa que la probabilidad de un símbolo

tiene una directa relación con el tamaño de su representación. “Hay mayor probabilidad de ocurrencia de un

símbolo, mientras más corto sea el tamaño de su representación en bits”.

En cualquier archivo, ciertos caracteres son usados más que otros. Si usamos representación binaria, el

número de bits requeridos para representar cada carácter depende del número de caracteres que tienen que

ser representados. Por ejemplo:

Si se usa un bit, significa que pueden representarse como máximo dos caracteres (0 un carácter, y 1 el

otro).

Si se usan dos bits significa que pueden representarse cuatro caracteres (00, 01, 10, 11, cada uno

representa un carácter),

y así sucesivamente.

La compresión Huffman a grandes rasgos es un sistema de longitud variable que asigna los códigos más

pequeños a aquellos caracteres más frecuentemente usados y los códigos más largos a aquellos menos

frecuentes. Esto sirve para reducir el tamaño de los archivos.

Circuitos electrónicos para sistemas de comunicación

Veamos un ejemplo:

Supongamos que en un archivo de datos se tiene la siguiente información:

 AAAAAABBBBCC, donde

 A tiene una frecuencia de 6,

 B de 4 y

 C de 2.

Cada carácter es representado usando una longitud fija de códigos de dos bits, entonces el número de bits

requeridos para almacenar el archivo sería 24:

(2 bits x 6) + (2 bits x 4) + (2 bits x 2) = 24 bits.

Si esa información es comprimida usando compresión Huffman, el carácter más frecuente debería ser

representado por los bits más pequeños:

A por el código 0 (1 bit)

B por el código 10 (2 bits)

C por el código 11 (2 bits)

Por lo tanto el tamaño del archivo pasará a ser de 18:

(1 bit x 6) + (2 bits x 4) + (2 bits x 2) = 18 bits

O sea:

000000101010101111

En el ejemplo anterior, los caracteres que se repetían más frecuentemente son asignados al código más

pequeño, resultando en un menor número de bits en el archivo final comprimido. Circuitos electrónicos para sistemas de comunicación

Código Hamming

Cuando enviamos información digital por un medio físico (cable) puede

...