Codigo huffman

Solo disponible en BuenasTareas
  • Páginas : 5 (1239 palabras )
  • Descarga(s) : 0
  • Publicado : 26 de marzo de 2011
Leer documento completo
Vista previa del texto
Tema 3: Codificación Huffman
Rafael Molina Depto. Ciencias de la Computación e Inteligencia Artificial Universidad de Granada
Rafael Molina Tema 3: Codificación Huffman 1

• Objetivos del tema • El algoritmo del código de Huffman – Códigos de Huffman de mínima varianza • Códigos de Huffman Adaptativos – Procedimiento de codificación – Procedimiento de decodificación – Procedimiento deactualización • (*) Códigos de Golomb • (*)Código Tunstall • Aplicaciones del código de Huffman • Resumen • Bibliografía

Contenidos

• Apéndice: Longitud del código de Huffman y código de Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen
Rafael Molina Tema 3: Codificación Huffman 2

III.1 Objetivos del tema
En este tema vamos a describir un algoritmo de codificaciónmuy conocido: el código de Huffman. Primero supondremos que es conocida la distribución de probabilidad de la fuente y luego construiremos el código cuando dichas probabilidades no son conocidas. A continuación veremos algunos esquemas de codificación, en algún sentido, similares al código de Huffman. Finalmente veremos algunos ejemplos de aplicación a compresión de imágenes, sonido y texto.Rafael Molina Tema 3: Codificación Huffman 3

III.2 El algoritmo del código de Huffman.
La codificación usando el método de Huffman (código Huffman) es un código prefijo óptimo para un conjunto dado de probabilidades. Puede alcanzar la entropía, aunque no lo hace siempre. Sí es óptimo entre los códigos prefijo.

Rafael Molina

Tema 3: Codificación Huffman

4

El código de Huffman estábasado en dos propiedades de los códigos prefijo óptimos: 1. En un código prefijo óptimo, los símbolos más frecuentes –los que tienen mayor probabilidad- tienen palabras del código más cortas que las palabras menos frecuentes. 2. En un código prefijo óptimo, los dos símbolos que ocurren con menos frecuencia tendrán la misma longitud.

Demostración de que estas condiciones las cumple un códigoprefijo óptimo:
La primera condición es obvia. El número medio de bits por símbolo sería mayor si esta condición no se cumpliese.
Rafael Molina Tema 3: Codificación Huffman 5

Para probar la segunda condición usaremos reducción al absurdo.

Supongamos que existe un código prefijo óptimo, C, en el que los dos símbolos menos probables no tienen la misma longitud. Sean P1 y P2 las correspondientespalabras del código y supongamos que long(P1)=k y long(P2)=n con kn1) cuya probabilidad es la mitad. ¿Cómo están relacionados n2 y n1?.

P( N
de donde

n2 ) qp n2

q 2 n2 log p n1 ) 0.5q 2 n1 log p q 2 1 n1 log p
Muy importante

0.5 u P( N

n2 log p 1  n1 log p
o

n2

1 n1  log p

§ 1 · n1  ¨  ¨ log p ¸ ¸ © ¹

Rafael Molina

Tema 3: Codificación Huffman

54 Intutivamente, nos gustaría que el código de n2 fuese un bit más largo que el de n1. Esto es lo que consigue el código de Golomb. Antes un poco de notación

¬x ¼ entero más próximo a x por abajo ªx º entero más próximo a x por arriba ¬3.5¼ 3 ª3.5º 4
Continuemos con el código de Golomb. Sea

Rafael Molina

ª 1 º w « log p » « »

Tema 3: Codificación Huffman

55

Para cada n sean

Q«n» « w» ¬ ¼

y R

n  Qw

En otras palabras Q es el cociente y R es el resto de la división de n por w (Observa que si n’=n+w entonces Q’=Q+1) La codificación de Golomb para n consiste en: 1. un prefijo unario (para el cociente, es decir para Q), 2. y un sufijo binario (para el resto, R) usando
* Este código va a ser mejorado después
Rafael Molina Tema 3: Codificación Huffman 56

ªlog wºbits *

Supongamos que p=2^(-1/4) ~ 0.8409, entonces

w 4, ªlog wº 2

N 0 1 2 3 4 5 6
Rafael Molina

Q 0 0 0 0 1 1 1

R 0 1 2 3 0 1 2

Representación 000 001 010 011 1000 1001 1010
57

Tema 3: Codificación Huffman

Supongamos que p=2^(-1/5) , entonces

w 5, ªlog wº 3

N 0 1 2 3 4 5 6
Rafael Molina

Q 0 0 0 0 0 1 1

R 0 1 2 3 4 0 1

Representación 0000 0001 0010 0011...
tracking img