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 cometerse errores de trasmisión, los

cuales se producen por variaciones en la corriente eléctrica. Dicha información puede no ser recibida

correctamente. Una forma de detectar esos errores es usando algún código de detección de errores, o bits de

paridad, los cuales se agregan al dato inicial para poder controlar alguna desviación. Para saber si dicha

información se ha enviado correctamente se utiliza principalmente el método Hamming.

Este método, sirve para corregir errores en k bits y es una aplicación inyectiva que permite codificar datos

de n bits en n+r bits, de modo que a partid de los n+r se pueda recuperar el código original de n bits incluso

cuando el código de n+r tenga k bits erróneos.

Un ejemplo de este código es el siguiente:

...