03 Codigo de Huffman

Rafael Molina Tema 3: Codificacin Huffman 1

Tema 3: Codificacin Huffman

Rafael MolinaDepto. Ciencias de la Computacin

e Inteligencia ArtificialUniversidad de Granada


Objetivos del tema El algoritmo del cdigo de Huffman

Cdigos de Huffman de mnima varianza Cdigos de Huffman Adaptativos

Procedimiento de codificacin Procedimiento de decodificacin Procedimiento de actualizacin

(*) Cdigos de Golomb (*)Cdigo Tunstall Aplicaciones del cdigo de Huffman Resumen

Bibliografa Apndice: Longitud del cdigo de Huffman y cdigo de

Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen

Contenidos


III.1 Objetivos del tema

En este tema vamos a describir un algoritmo de codificacinmuy conocido: el cdigo de Huffman. Primero supondremosque es conocida la distribucin de probabilidad de la fuentey luego construiremos el cdigo cuando dichasprobabilidades no son conocidas.

A continuacin veremos algunos esquemas de codificacin,en algn sentido, similares al cdigo de Huffman.

Finalmente veremos algunos ejemplos de aplicacin acompresin de imgenes, sonido y texto.


III.2 El algoritmo del cdigo de Huffman.

La codificacin usando el mtodo de Huffman (cdigoHuffman) es un cdigo prefijo ptimo para un conjuntodado de probabilidades.

Puede alcanzar la entropa, aunque no lo hace siempre.

S es ptimo entre los cdigos prefijo.


El cdigo de Huffman est basado en dos propiedades de loscdigos prefijo ptimos:

1. En un cdigo prefijo ptimo, los smbolos ms frecuenteslos que tienen mayor probabilidad- tienen palabras delcdigo ms cortas que las palabras menos frecuentes.

2. En un cdigo prefijo ptimo, los dos smbolos que ocurrencon menos frecuencia tendrn la misma longitud.

Demostracin de que estas condiciones las cumple un cdigoprefijo ptimo:

La primera condicin es obvia. El nmero medio de bits porsmbolo sera mayor si esta condicin no se cumpliese.


Para probar la segunda condicin usaremos reduccin alabsurdo.

Supongamos que existe un cdigo prefijo ptimo, C, en elque los dos smbolos menos probables no tienen la mismalongitud.

Sean P1 y P2 las correspondientes palabras del cdigo ysupongamos que long(P1)=k y long(P2)=n con k


Como estos smbolos son los menos probables ninguna otrapalabra puede ser ms larga que estas dos y por tanto nohay peligro de que al hacer ms corta esta palabra del cdigo(la de P2) se convierta en prefijo de ninguna otra. Por tanto,C sigue siendo prefijo.

Hemos creado un nuevo cdigo, C, que hace que C no seaptimo, lo que contradice la hiptesis inicial sobre C.

Para construir el cdigo de Huffman le aadimos la siguientecondicin a las dos propiedades vistas de los cdigos prefijoptimos:Si u y v son los dos smbolos menos probables en el alfabeto,si la codificacin de u es m*0, la de v ser m*1. Donde m esuna hilera de ceros y unos y * denota concatenacin.


Genera el cdigo de Huffmancorrespondiente a lassiguientes probabilidades

1. Ordena los smbolos de ms probable a menos probable,

2. Comienza a construir un rbol por las hojas combinando los dos smbolos menos probables,

3. Itera el procedimiento

Algoritmo del cdigo de Huffman

P( )=0.5P( )=0.4P( )=0.09P( E )=0.01


E 0.01

0.09

0.4

0.5

1

0

0.1

0

10.5

0

11.0

Cul es la longitud media del cdigo?

Cul es la entropa de la fuente?

probabilidades

Probabilidades acumuladas

Nota: asignamos 1 a la rama menos probableE

0

10

110

111

CdigoSmbolo CdigoSmbolo


D 0.1

0.3

0.3

0.3

1

0

0.4

0.61

0

1

0

1.0C

B

A

A 00 B 01 C 10 D 11

probabilidades Otro ejemplo


E 0.1

0.1

0.2

0.2

1

0

0.2

0

10.4

probabilidades

D

C

A

B 0.4

0.6

0

1

0

11.0

B 1A 01C 000D 0010E 0011

Para decodificar una secuencia de palabras slo tenemos querecorrer el rbol del cdigo prefijo correspondiente al cdigoHuffman como vimos en el captulo anterior.

Otro ejemplo


III.2.1 Cdigos de Huffman de mnima varianzaConsideremos el cdigo de Huffman del ejemplo anterior. Elnmero medio de bits por smbolo es

L=0.4x1+0.2x2+0.2x3+0.1x4+0.1x4=2.2 bits/smbolo

Supongamos que queremos transmitir 10000 smbolos/sg.Con una capacidad de transmisin de 22000 bits/sg el canalira en media bien. Sin embargo, si tenemos que transmitirmuchas veces seguidas los smbolos D o E podemos necesitarun buffer mucho mayor.

Lo mejor sera que, manteniendo la misma longitud media,pudisemos disear un cdigo de Huffman con menorvarianza en la longitud de la codificacin de cada smbolo.

Rafael Molina Tema 3: Codificacin Huffman 13E 0.1

0.1

0.2

0.2

1

0

0.2

0

1 0.4

probabilidades

D

C

A

B 0.4

B 00A 10C 11D 010E 011

0

1 1.0

Para disminuir la varianza colocamos, en caso de empate enlas probabilidades de los nodos, los nodos ya utilizados loms alto posible procurando utilizarlos lo ms tarde posible.Retomemos el ejemplo de la seccin anterior.

0.6

0

1


III.3 Cdigo de Huffman adaptativo

El cdigo de Huffman necesita conocer la probabilidad deaparicin de cada smbolo.

Para la construccin del rbol adaptativamente, veamos acontinuacin qu propiedades caracterizan a un rbol binariopara que sea el correspondiente a un cdigo de Huffman.

1. Para tener estas probabilidades podemos leer los datospara obtenerlas y luego codificar los smbolos usando elcdigo de Huffman para dichas probabilidades,

2. o bien podemos ir construyndolo (adaptativamente)mientras vamos leyendo los smbolos. Esta es la base delcdigo Huffman adaptativo.


Consideremos un rbol binario correspondiente a un alfabeto detamao n en el que los smbolos del alfabeto son las hojas.Entonces, el nmero de nodos del rbol es 2n-1 (prubalo porinduccin).

A cada nodo del rbol binario le vamos a asignar doscampos: Nmero del nodo y peso del nodo.

El nmero de nodo es un nmero nico asignado a cada nododel rbol entre 1 y 2n-1. Los nmeros los notaremos y1,,y2n-1.

El peso de un nodo hoja es simplemente el nmero de vecesque aparece el smbolo correspondiente y el de uno interno lasuma de los pesos de sus dos hijos. Los pesos los notaremosx1,,x2n-1.


Puede probarse que:

Si al asignar nmeros a los nodos comenzando por el uno yrecorriendo el rbol por niveles (asignamos, de izquierda aderecha en cada nivel y de las hojas (abajo) a la raz(arriba) los pesos de los nodos quedan ordenados en unorden no decreciente

El rbol obtenido es un rbol binario correspondiente a uncdigo de Huffman para dichos smbolos con lasprobabilidades de cada nodo hoja igual a su peso divididopor la suma de los pesos.La propiedad anterior recibe el nombre de sibling property onode number invariant.


En el ejemplo de la derecha:Entre parntesis los pesos decada nodo. (16)

(7) (9)

(3) (4)

(2)(2)(1) (2)1 2

7 8

5 6

9

3 4

Dentro de los cuadrados elnmero asignado a cadanodo.

Por tanto, este rbol es elcorrespondiente al cdigo deHuffman para estos smboloscon las probabilidades que seobtienen a partir del nmero deveces que ha aparecido cadasmbolo dividido por el nmerode smbolo ledos.


En el cdigo Huffman adaptativo ni el transmisor ni elreceptor conocen al principio las probabilidades de lossmbolos. Por eso:

1. Codificador y decodificar comienzan con un rbol con unnodo nico que corresponde a todos los smbolos notransmitidos (NYT) y que tiene peso cero.

2. Mientras progresa la transmisin se aadirn nodos alrbol correspondientes a smbolos que aparezcan porprimera vez, se modificarn los pesos (tanto si elsmbolo es nuevo como si es ya existente) y seactualizar el rbol para que siga cumpliendo the siblingproperty (siga siendo de Huffman).


El algoritmo de Huffman adaptativo consta de los siguienteselementos:

1. Inicializacin (la misma para el codificador ydecodificador).

Antes de describir estas partes comentaremos brevemente sobre la codificacin de los smbolos:

2 Algoritmo de codificacin.

3. Algoritmo de decodificacin.

4. Proceso de actualizacin del rbol para que mantengathe sibling property.


Codificacin de un smbolo que aparece por primeravez:

Salvo que sea el primero de todos lo smbolos de lasecuencia, la codificacin de un smbolo que aparece porprimera vez consta de la codificacin que proporciona elrbol del nodo NYT seguido de un cdigo fijo para el smboloque deben conocer codificador y decodificador

En el caso en que sea el primer smbolo que aparece en lasecuencia no necesitamos transmitir el cdigo de NYT.

Si el smbolo ya ha aparecido

Utilizamos la codificacin que proporciona el rbol que vamos construyendo.


Inicializacin del cdigo de Huffman adaptativo (tanto para el codificador como para el decodificador

1. Nuestro rbol ha de codificar n+1 smbolos incluyendo el correspondiente a NYT,

2. Necesitamos por tanto 2(n+1)-1=2n+1 nmeros para los nodos,

3. El rbol de Huffman inicial tiene un nodo nico:

0

NYT2n+1

Nmero del nodo

peso


1. Si encontramos un smbolo nuevo (ver nota) entoncesgenerar el cdigo del nodo NYT seguido del cdigo fijo(ver nota) del smbolo. Aadir el nuevo smbolo alrbol,

2. Si el smbolo ya est presente, generar su cdigousando el rbol,

3. Actualizar el rbol para que siga conservando thesibling property.

Nota: Recordemos que para el primer smbolo no hace falta transmitir elcdigo de NYT. El cdigo fijo es conocido al principio por codificador ydecodificador.

Algoritmo de codificacin para el cdigo Huffman adaptativo


1. Decodificar el smbolo usando el rbol actual,

2. Si encontramos el nodo NYT, usar el cdigo fijo paradecodificar el smbolo que viene a continuacin. Aadirel nuevo smbolo al rbol,

3. Actualizar el rbol para que siga conservando thesibling property.

Nota: recordar, de nuevo, que el primer smbolo no va precedido por elcdigo de NYT

Algoritmo de decodificacin para el cdigo Huffman adaptativo


1. Sea y la hoja (smbolo) con peso x,2. Si y es la raz, aumentar x en 1 y salir3. Intercambiar y con el nodo con el nmero mayor que

tenga el mismo peso que l (salvo que sea su padre)4. Aumentar x en 15. Sea y el padre que tiene su peso x (el que sea, no el

definido en 4) ir al paso 2 del algoritmo

Actualizacin del rbol para el cdigo Huffman adaptativo


Ejemplo

Consideremos el alfabeto A={a,b,c,d} y realicemos la codificacin de la secuencia

aabcdad

Primero vemos el nmero de nodos que necesitaremos

Nodos=2*4+1=9

Los cdigos de longitud fija que usamos son

a 000 b 001 c 010 d 011


aabcdad en A={a,b,c,d}

salida=000

NYT

9

0 7

a

8

0

0

Paso 1 del algoritmo de codificacin

0

NYT

9Inicializacin

0 1


NYT

9

0 7

a

8

0

1

Paso 3 del algoritmo de codificacin (actualizacin)

Paso 4 dentro del algoritmo de actualizacin

NYT

9

0 7

a

8

1

1


0 1

0 1


aabcdad

salida=0001

NYT

9

0 7

a

8

1

1

Paso 2 del algoritmo de codificacin

Tenemos

NYT

9

0 7

a

8

1

1

salida=000

0 1

0 1


NYT

9

0 7

a

8

1

2



NYT

9

0 7

a

8

2

2


0 1

0 1


aabcdad

Tenemos

NYT

9

0 7

a

8

2

2

salida=0001

0 1

1

salida=000100019

7

a

8

2

2Paso 1 del

algoritmo de codificacin

Cdigo de b

Cdigo de NYT

NYT

0

0

0 65

b

0

0 1


6

1

9

7

a

8

2

2

NYT

0

0

15

b

0

0 1

5

a1

9

7 8

2

2

NYT

0

1

1 6

b

0

0 1


a1

9

7 8

3

2

NYT

0

1

1 6

b

0

0 1

5


a1

9

7 8

3

2

NYT

0

1

1 6

b

0

0 1

5

aabcdad

Tenemos

salida=00010001

a1

9

7 8

3

2

NYT

1

1 6

b

0

0 1

5

salida=0001000100010

0 0

0

43

c

Cdigo de NYT

c

Algoritmo de codificacin sin adaptacin del rbol

0 1


adaptacin del rbol

a1

9

7 8

3

2

NYT

1

1 6b

0

0 1

5

0 1

0

43c

0 1

a1

9

7 8

3

2

NYT

1

1 6b

0

0 1

5

0 1

1

43

c

0 1

a1

9

7 8

3

2

NYT

2

1 6b

0

0 1

5

0 1

1

43c

0 1

a1

9

7 8

4

2

NYT

2

1 6b

0

0 1

5

0 1

1

43c

0 1


aabcdad

Tenemos

a1

9

7 8

4

2

NYT

2

1 6b

0

0 1

5

0 1

1

43c

0 1

salida=0001000100010

a1

9

7 8

4

22

1 6b

0

0 1

5

1

1

43c

salida=0001000100010000011

NYT0 0 21

d

0


d

NYT

0

0

1

1


a1

9

7 8

4

22

1 6b

0

0 1

5

1

1

43c

NYT0 1 21

d

00

0

1

1

a1

9

7 8

4

22

1 6b

0

0 1

5

1

1

43c

NYT0 1 21

d

10

0

1

1

adaptacin del rbol


a1

9

7 8

4

22

1 6

b

0

0 1

5

1

1

43

c

NYT0 1 21

d

10

0

1

1

a1

9

7 8

4

22

1 6b

0

0 1

5

1

1

43c

NYT0 1 21

d

10

0

1

1

adaptacin del rbolCAMBIO DE ORDEN


a1

9

7 8

4

22

1 6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0

1

1

adaptacin del rbol

a1

9

7 8

4

22

1 6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0

1

1


adaptacin del rbol

11

9

7

1

8

4

2 2

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

11

9

7

1

8

4

2 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

CAMBIO DE ORDEN


adaptacin del rbol

11

9

7

1

8

5

2 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a


11

9

7

1

8

5

2 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

aabcdad

Tenemos salida=0001000100010000011

11

9

7

1

8

5

2 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a


salida=00010001000100000110


11

9

7

1

8

5

3 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a1

1

9

7

1

8

6

3 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

adaptacin del rbol


11

9

7

1

8

6

3 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

aabcdad

Tenemos salida=

00010001000100000110


salida=000100010001000001101101

11

9

7

1

8

6

3 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a

d


11

9

7

1

8

6

3 3

6

b

0

0 1

5

1

2

43

c

NYT0 1 21

d

10

0 1

a1

1

9

7

1

8

6

3 3

6

d

0

0 1

5

1

2

43

c

NYT0 1 21

b

10

0 1

a

Observar cambio


21

9

7

1

8

6

3 3

6

d

0

0 1

5

1

2

43

c

NYT0 1 21

b

10

0 1

a2

1

9

7

1

8

6

3 3

6

d

0

0 1

5

1

2

43

c

NYT0 1 21

b

10

0 1

a


21

9

7

1

8

6

3 4

6

d

0

0 1

5

1

2

43

c

NYT0 1 21

b

10

0 1

a2

1

9

7

1

8

7

3 4

6

d

0

0 1

5

1

2

43

c

NYT0 1 21

b

10

0 1

a


Ejercicio:

Usando el cdigo fijo

a=000, b=001, c=010, d=011

Decodificar la secuencia 00110000 usando el cdigo deHuffman adaptativo.

Aunque el cdigo de Huffman es uno de los mtodos decodificacin de longitud de palabra variable msconocidos, existen otros mtodos algo menos conocidospero tambin muy tiles. En particular los mtodos deGolomb-Rice y Tunstall que veremos a continuacin.


III.4 Cdigo de Golomb

Consideremos un suceso A que tiene probabilidad p y sucomplementario Ac que tiene probabilidad q=1-p (obviamentep+q=1).

Queremos codificar el nmero de veces (racha=run length)que aparece A antes de que aparezca Ac.

Suponemos que las realizaciones son independientes.

Observa que si p es prximo a uno esperamos que aparezcamuchas veces el suceso A antes de que aparezca un Ac.


Ejemplos de estos modelos son:

1. A es que salga cara al lanzar una moneda y Ac es obviamente que salga cruz.

2. En el problema del agente 00111 de Golomb (ver material adicional) el suceso Ac es que salga el cero en la ruleta y A es que no salga (la ruleta tiene los nmeros del 0 al 36).

3. Puntos en blanco y negro como podra ser el contenido de una hoja.


1. Observa que para la ruleta P(A)=36/37 y P(Ac)=1/37.2. En el caso de la moneda (si no est sesgada)

P(A)=P(Ac)=1/2.3. En el caso de hojas en blanco y negro se podra estimar p.

Los fabricantes de impresoras suponen p=0.05

Lo que queremos codificar son las realizaciones de la variablealeatoria N definida por

N= nmero de veces que aparece A antes de que aparezcaAc.

Esta variable tiene la siguiente distribucin de probabilidad

P(N=n)=pnq n=0,1,2,.


Una posible codificacin sera:

Cada vez que aparezca el suceso A lo codificamos con un unoy cuando se produzca el suceso Ac lo codificamos con uncero.

De esta forma el valor n de la variable aleatoria N se codificamediante n unos seguidos de un cero. Es decir,

0 01 102 110

3 1110

N cdigo

. .

. .

Este cdigo recibe el nombre decdigo unario.

Cul es el nmero medio de bits queeste cdigo, C, usa para codificar lavariable N?


( ) pppqpq

pderivpqp

qnpqpp

q

npqpqqpnNC

n

n

n

n

n

n

n

nn

np

=+=

+=+=

+=+=

=

=

=

=

=

11

11

1

11

)1()(

2

00

1

000

Observa que si p est muy prximo a uno Cp(N) es muygrande.Cunto vale la entropa de la variable aleatoria N enfuncin de p?.

Recuerda que q=1-p


( ) ( )

( ) ( )( )ppqq

p

pp

pqp

ppqpqq

pderivadappqpqq

npppqpqq

nppqpqqqppqNH

n

n

n

n

n

n

n

nn

n

np

loglog1

1

)log(1

log1

1)log(1

)log(

)log(1

)log(

)log(1

)log(

log)log(log)(

2

0

0

1

000

+===

=

=

==

=

=

=

=

=

Recuerda que q=1-p


Observa que para p grande deberamos ser capaces de mejorar el cdigo unario.

Sin embargo, para p=0.5, Cp(N) Hp(N)=0 y el cdigo unario es el mejor que podemos utlizar.

Representacin grfica de Cp(N) Hp(N)


Veamos la idea del cdigo de Golomb intuitivamente.

Supongamos que tenemos una racha de apariciones de A de longitud n1 y otra racha de apariciones de A de longitud n2(>n1) cuya probabilidad es la mitad.

Cmo estn relacionados n2 y n1?.

pnpn

pnn

qqnNPqqpnNP

log1log1

log2

11

22

225.0)(5.0

2)(+====

===de donde

pnpn log1log 12 +=o

+==

pn

pnn

log1

log1

112

Muy importante


Intutivamente, nos gustara que el cdigo de n2 fuese un bit ms largo que el de n1. Esto es lo que consigue el cdigo de Golomb.

Antes un poco de notacin

45.3

35.3arribapor x a prximo ms enteroabajopor x a prximo ms entero

==

==

xx

Continuemos con el cdigo de Golomb. Sea

=p

wlog

1


QwnRywnQ =

=Para cada n seanEn otras palabras Q es el cociente y R es el resto de la divisin de n por w

(Observa que si n=n+w entonces Q=Q+1)

La codificacin 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 bits log w ** Este cdigo va a ser mejorado despus


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

2log,4 == wwN Q R Representacin0 0 0 0001 0 1 0012 0 2 0103 0 3 0114 1 0 10005 1 1 10016 1 2 1010


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



La parte sufijo del cdigo es mejorable cuando w no sea unapotencia de 2, si usamos la siguiente representacin delongitud variable:

Sea R {0,1,,w-1}

cdigos 2Msobran nos bits logw Usando logw w=

bits logwcon binariacin representa usamos MR Si < R de bits logen cin representa la usamos R Si MwM +


10

0 1

w=2

0

0 1

21

0 1

w=3

Resto R Representacin

0 0

1 1


0 0

1 10

2 11

Ejemplos:

Los arcos determinan el cdigoLos nodos contienen el resto


43

0 1

0 1

2

0 1

w=5


0 00

1 01

2 10

3 110

4 111

10

0 1

0 1

32

0 1

w=4


0 00

1 01

2 10

3 11

10

0 1

Ms ejemplos de la representacin de la parte sufijo


Supongamos que p=2-1/5 . Entonces


Otro ejemplo de cdigo Gollub:

CDIGO

GOLLUB


III.5 Cdigo Tunstall Es un cdigo de longitud fija en el que cada palabra del cdigo puede representarun nmero diferente de letras.

Supongamos que tenemos inicialmente m smbolos y queremos usar como salida representaciones de longitud fija con n bits, siendo 2n>m. Suponemos que las realizaciones de dichos smbolos son independientes. Construccin del rbol:

Formar un rbol con una raz y m hijos con arcos etiquetados con los smbolos del alfabeto,Si el nmero de hojas del rbol, l, cumple l+(m-1)< 2nseguir, en caso contrario parar.*Encontrar la hoja con mayor probabilidad (la probabilidad es el producto de las probabilidades de los smbolos del camino de la raz a las hojas) y expandirla para que tenga m hijos. Volver al paso anterior,

Cdigo de Tunstall


*Justificacin de la condicin de parada:

Veamos cuantos hojas tiene el rbol,

Si en un instante tiene l hojas, para expandir le quitamos una yde esa una salen m. Por tanto una vez realizada la expansintenemos l-1+m que necesitaremos que sea menor que 2n yaque necesitamos dejarnos al menos un cdigo libre como yaveremos.

Una vez construido el rbol le asignamos un cdigo de longitud n a cada una de las hojas.


Supongamos que P(A)=0.6, P(B)=0.3 y P(C)=0.1 y n=3. Por tanto, deseamos generar una representacin de longitud fija 3.

Paso 1

A B C

0.6 0.3 0.1


l=3, 3+2=5, 5


l=5, 5+2=7, 7


L=7, 7+2=9, 9 8, Salimos

Paso 2

Codificacin final (hay varias opciones)

A B C

A B C

A B C

000 001 010

011 100

101 110Observa que tenemos libre la palabra del cdigo 111


El cdigo de Tunstall ha generado la siguiente representacin

Entrada Salida

AAA 000

AAB 001

AAC 010

AB 011

AC 100

B 101

C 110

Qu ocurre si queremos codificar la secuencia AA?.

AA no tiene representacin.

Para codificar el AA enviamos el cdigo no utilizado (111) y un cdigo fijo para AA.Generalmente, si hay k nodos internos en el rbol necesitaremos k-1 cdigos fijos. En nuestro problema A y AA.


Otro ejemplo. Supongamos P(A)=0.9 y P(B)=0.1 y usamos n=2.

El rbol que construiramos sera

A B

A B

00 01

10

Y dejaramos el 11 para enviar el cdigo de A

Entrada SalidaAA 00

AB 01

B 10


Si ussemos las cuatro palabras tendramos

y no podramos enviar cdigo para A

Entrada SalidaAAA 00

AAB 01

AB 10

B 11

A B

A B

10

11

A B

00 01


Entrada Salida

AAA 000

AAB 001

AAC 010

AB 011

AC 100

B 101

C 110

Problema: considera la tabla en la que el cdigo 111 es utilizado para anunciar que a continuacin viene el cdigo de A o AA.

Qu proceso seguiramos para codificar las secuencias

CABBAACCBBACA

?


III.6 Aplicaciones del cdigo de Huffman En las clases de prcticas se estudiarn las siguientesaplicaciones:

Imgenes: Usaremos imgenes de niveles de gris, es decir,que en cada punto toman un valor entre 0 y 255. Estimaremosla probabilidad de ocurrencia de cada nivel de gris usando elhistograma y aplicaremos Huffman. El modelo ser por tantono adaptativo.

Como los valores de los pxeles estn muy correladoscodificaremos la diferencia entre un pxel y el anterior usandoHuffman, veremos que mejoramos el nivel de compresin.

Tambin usaremos imgenes binarias y cdigos de Huffmanadaptativos


Texto: Usaremos diferentes tipos de texto y aplicaremos Huffman habiendo calculado antes las probabilidades de cada letra a partir del texto.

Eliminar la correlacin aqu es ms complicado y veremos como hacerlo en captulos posteriores.

Sonido: Cada canal estreo se muestrea a 44.1 kHz y utiliza una representacin de 16 bits. Aunque no vamos a construir el cdigo Huffman (tendra 216 entradas), calcularemos la entropa y por tanto una estimacin de la mejor compresin que podemos alcanzar. Podemos tambin eliminar (o disminuir) la correlacin entre los datos y volver a calcular la entropa y por tanto una estimacin de la compresin a alcanzar con este modelo.


III.7 Resumen del tema

1. Cdigo de Huffman, no adaptativo y adaptativo,2. Cdigos unarios y de Golomb,3. Cdigos de Tunstall,4. Aplicaciones.


III.8 BibliografaK. Sayood, Introduction to Data Compression, Morgan and Kaufmann, 2000.Material adicional de la asignaturaG. Langdon, Data Compression, Universidad de California, 1999. (langdon_Run-Length_Encodings.pdf).Roque Marn,Compresores estadsticos, Universidad de Murcia, (00_compresores_estadsticos_univ.murcia.pdf).Notas sobre el cdigo de Golomb (Golomb_Notes.pdf).Otra presentacin sobre compresores estadsticos, (00_compresores_estadsticos_II.pdf).Temas 2, 3 y 4 del curso de compresin de datos impartido en Stony Brook University (NY, USA), (tema[2,3,4]_stony.pdf).Tema 3 del curso de compresin de datos impartido en Chalmers University of Technology (Suecia), curso 2003-2004. (tema3_chalmers.pdf).

S. W. Golomb, Run-Length Encodings, IEEE Trans. On Information Theory, IT-12: 399-401, 1966.D.A. Huffman, A method for the construction of minimum redundancy codes, Proceedings of the IRE, 40:1098-1101, 1951.


Apndice: longitud de los cdigos de Huffman y cdigos de Huffman extendidos

Dado un cdigo de Huffman, puede probarse que, su longitud media n cumple

H(S) n < H(S) + 1

Primer Teorema de Shannon o Teorema Fundamental de la Codificacin sin Ruido:Dada una fuente S = {x1, ... xm} y un alfabeto binario, existe al menos un cdigo prefijo C cuya longitud media cumple

siendo cualquier nmero real arbitrariamente pequeo.

+< )(SHn


1)()( + qqq SHnSH

1)()( + SHqnqSHq

qSHnSH 1)()( +

La demostracin del teorema es la siguiente:Supongamos que codificamos bloques de q mensajes y seguimos suponiendo que son independientes, entonces tendremos (observa que la fuente es ahora Sq)

Reeescribiendo esta ecuacin en funcin de la entropa de la fuente original tendremos

dividiendo por q obtendremos

Basta con elegir un tamao de bloque q suficientemente grande para conseguir 1/q < para que se cumpla lo afirmado por el teorema.

Tema 3: Codificacin Huffman ContenidosIII.1 Objetivos del temaIII.2 El algoritmo del cdigo de Huffman. Nmero de diapositiva 5Nmero de diapositiva 6Nmero de diapositiva 7Nmero de diapositiva 8Nmero de diapositiva 9Nmero de diapositiva 10Nmero de diapositiva 11III.2.1 Cdigos de Huffman de mnima varianzaNmero de diapositiva 13III.3 Cdigo de Huffman adaptativoNmero de diapositiva 15Nmero de diapositiva 16Nmero de diapositiva 17Nmero de diapositiva 18Nmero de diapositiva 19Nmero de diapositiva 20Nmero de diapositiva 21Algoritmo de codificacin para el cdigo Huffman adaptativoAlgoritmo de decodificacin para el cdigo Huffman adaptativoActualizacin del rbol para el cdigo Huffman adaptativoNmero de diapositiva 25Nmero de diapositiva 26Nmero de diapositiva 27Nmero de diapositiva 28Nmero de diapositiva 29Nmero de diapositiva 30Nmero de diapositiva 31Nmero de diapositiva 32Nmero de diapositiva 33Nmero de diapositiva 34Nmero de diapositiva 35Nmero de diapositiva 36Nmero de diapositiva 37Nmero de diapositiva 38Nmero de diapositiva 39Nmero de diapositiva 40Nmero de diapositiva 41Nmero de diapositiva 42Nmero de diapositiva 43Nmero de diapositiva 44Nmero de diapositiva 45Nmero de diapositiva 46III.4 Cdigo de GolombNmero de diapositiva 48Nmero de diapositiva 49Nmero de diapositiva 50Nmero de diapositiva 51Nmero de diapositiva 52Nmero de diapositiva 53Nmero de diapositiva 54Nmero de diapositiva 55Nmero de diapositiva 56Nmero de diapositiva 57Nmero de diapositiva 58Nmero de diapositiva 59Nmero de diapositiva 60Nmero de diapositiva 61Nmero de diapositiva 62III.5 Cdigo Tunstall Nmero de diapositiva 64Nmero de diapositiva 65Nmero de diapositiva 66Nmero de diapositiva 67Nmero de diapositiva 68Nmero de diapositiva 69Nmero de diapositiva 70Nmero de diapositiva 71Nmero de diapositiva 72III.6 Aplicaciones del cdigo de Huffman Nmero de diapositiva 74III.7 Resumen del temaIII.8 BibliografaApndice: longitud de los cdigos de Huffman y cdigos de Huffman extendidosNmero de diapositiva 78

03 Codigo de Huffman

Documents

Transcript of 03 Codigo de Huffman