introducción a los códigos compresores - parte i de la lección 2

FuentesCódigos (compresores)

Introducción a los códigos compresoresParte I de la Lección 2, Compresores sin pérdidas, de CTI

Ramiro Moreno Chiral

Dpt. Matemàtica (UdL)

Febrero de 2010

Ramiro Moreno (Matemàtica, UdL) Introducción a los códigos compresores Febrero de 2010 1 / 26


Índice

1 Fuentes

2 Códigos (compresores)



Definición de fuenteTipos de fuentesEntropía de una fuente

Índice

1 FuentesDefinición de fuenteTipos de fuentesEntropía de una fuente

2 Códigos (compresores)




Resumen

Veremos en este apartadoUna definición muy general del concepto de fuente deinformación.Los diferentes tipos de fuentes que sirven para modelarlas fuentes de información reales.Finalmente, una definición también muy general deentropía de una fuente




Resumen

Veremos en este apartado

Una definición muy general del concepto de fuente deinformación.Los diferentes tipos de fuentes que sirven para modelarlas fuentes de información reales.Finalmente, una definición también muy general deentropía de una fuente




Resumen

Veremos en este apartadoUna definición muy general del concepto de fuente deinformación.

Los diferentes tipos de fuentes que sirven para modelarlas fuentes de información reales.Finalmente, una definición también muy general deentropía de una fuente




Resumen

Veremos en este apartadoUna definición muy general del concepto de fuente deinformación.Los diferentes tipos de fuentes que sirven para modelarlas fuentes de información reales.

Finalmente, una definición también muy general deentropía de una fuente




Resumen

Veremos en este apartadoUna definición muy general del concepto de fuente deinformación.Los diferentes tipos de fuentes que sirven para modelarlas fuentes de información reales.Finalmente, una definición también muy general deentropía de una fuente




Definición de fuente (I)

Para definir una fuente son necesarios

Un alfabeto finito, X = {x1, . . . , xr}, y las cadenas delongitud n sobre X : X n =

{x = xi1 . . . xin : xij ∈ X

}.

Una familia de v.a.’s (Xt )t∈T sobre X , (T se identifica conel tiempo).Una distribución de probabilidad conjunta,

p(x , t) = P (Xt1 = xt1 , . . . ,Xtn = xtn ) ,

con x = xt1 . . . xtn ∈ X n y t = (t1, . . . , tn) ∈ T n

Un conjunto de probabilidades de transición

pij(t , t ′) = P(Xt ′ = xj |Xt = xi

), ∀t < t ′ ∈ T , xi , xj ∈ X .







{x = xi1 . . . xin : xij ∈ X

}.

Una familia de v.a.’s (Xt )t∈T sobre X , (T se identifica conel tiempo).

Una distribución de probabilidad conjunta,

p(x , t) = P (Xt1 = xt1 , . . . ,Xtn = xtn ) ,




), ∀t < t ′ ∈ T , xi , xj ∈ X .







{x = xi1 . . . xin : xij ∈ X

}.

Una familia de v.a.’s (Xt )t∈T sobre X , (T se identifica conel tiempo).Una distribución de probabilidad conjunta,

p(x , t) = P (Xt1 = xt1 , . . . ,Xtn = xtn ) ,




), ∀t < t ′ ∈ T , xi , xj ∈ X .




Definición de fuente (II)

DefiniciónSe define una fuente S,

S =(X , {pij(t , t ′)}

).

Cuando las probabilidades de transición no se explicitenusaremos la notación más general

S =(X , (Xt )t∈T

)




Tipos de fuentes

Fuentes estacionarias, si las probabilidades de transiciónno dependen del origen de tiempos,

P(Xt ′ = xj |Xt = xi

)= P

(Xt ′+τ = xj |Xt+τ = xi

), ∀τ ∈ T .

Fuentes simples: son fuentes estacionarias donde lasv.a.’s Xn son iid ∼ X ,

S = (X ,X ) .

Fuentes con memoria, cuando pij(t , t ′) 6= pj(t ′): el presentedepende de lo ocurrido en el pasado.Fuentes de Markov: estacionarias, con memoria y con unacondición de Markov de orden m,

P(Xtn = xn|Xt1 , . . . ,Xtn−1

)= P(Xtn = xn|

m︷︸︸︷Xtn−m , . . . ,Xtn−1)




Tipos de fuentes



)= P


), ∀τ ∈ T .


S = (X ,X ) .

Fuentes con memoria, cuando pij(t , t ′) 6= pj(t ′): el presentedepende de lo ocurrido en el pasado.

Fuentes de Markov: estacionarias, con memoria y con unacondición de Markov de orden m,

P(Xtn = xn|Xt1 , . . . ,Xtn−1

)= P(Xtn = xn|

m︷︸︸︷Xtn−m , . . . ,Xtn−1)




Tipos de fuentes



)= P


), ∀τ ∈ T .


S = (X ,X ) .

Fuentes con memoria, cuando pij(t , t ′) 6= pj(t ′): el presentedepende de lo ocurrido en el pasado.Fuentes de Markov: estacionarias, con memoria y con unacondición de Markov de orden m,

P(Xtn = xn|Xt1 , . . . ,Xtn−1

)= P(Xtn = xn|

m︷︸︸︷Xtn−m , . . . ,Xtn−1)




Entropía de una fuente

DefiniciónDefiniremos como entropía por carácter de una fuenteS = (X , (Xn)) al límite

H(S) = limn→∞

H (X1, . . . ,Xn)

n.

Para una fuente simple, S = (X ,X ), es H(S) = H(X ).

Otra definición alternativa,

H′(S) = limn→∞

H (Xn|X1, . . . ,Xn−1) .

pero para fuentes S estacionarias es H(S) = H′(S).



Definición de códigoTipos de códigosCódigos instantáneos

Índice

1 Fuentes

2 Códigos (compresores)Definición de códigoTipos de códigosCódigos instantáneos




Resumen

Trataremos de los siguientes temasLa definición de qué es un código compresor.Los tipos de códigos que se pueden presentar y su posibleuso en compresión de fuentes.Y, finalmente, dedicaremos nuestra atención al tipo decódigos más usual: los instantáneos.




Resumen

Trataremos de los siguientes temas

La definición de qué es un código compresor.Los tipos de códigos que se pueden presentar y su posibleuso en compresión de fuentes.Y, finalmente, dedicaremos nuestra atención al tipo decódigos más usual: los instantáneos.




Resumen

Trataremos de los siguientes temasLa definición de qué es un código compresor.

Los tipos de códigos que se pueden presentar y su posibleuso en compresión de fuentes.Y, finalmente, dedicaremos nuestra atención al tipo decódigos más usual: los instantáneos.




Resumen

Trataremos de los siguientes temasLa definición de qué es un código compresor.Los tipos de códigos que se pueden presentar y su posibleuso en compresión de fuentes.

Y, finalmente, dedicaremos nuestra atención al tipo decódigos más usual: los instantáneos.




Resumen

Trataremos de los siguientes temasLa definición de qué es un código compresor.Los tipos de códigos que se pueden presentar y su posibleuso en compresión de fuentes.Y, finalmente, dedicaremos nuestra atención al tipo decódigos más usual: los instantáneos.




Códigos: definición

DefiniciónDados

un alfabeto–fuente, X , tal que |X | = r ;un alfabeto–código, Σ, con |Σ| = d , y el lenguaje sin lacadena vacía, Σ+;

diremos que un código, C, para la extensión n-ésima delalfabeto–fuente, es una aplicación

X n C−→ Σ+

x 7−→ C(x),

donde x =(xi1 , . . . , xin

), xik ∈ X . A los elementos del código,

C(x), los llamaremos palabras–código.




Codificación de fuentes

DefiniciónDada una fuente S = (X , (Xn)), definimos un código para Scomo un código asociado al alfabeto–fuente, X . Entonces,

Llamaremos L(C(x)) = |C(x)| a las longitudes de laspalabras–código.Y la longitud media del código será

L = L(C) = EX1...XnL(C(x)) =∑

x∈X n

p(x)L(C(x)).




Codificación de fuentes simples

Si la fuente es simple, S = (X ,X ), la aplicación código es mássencilla

X C−→ Σ+

x 7−→ C(x),

y la logitud media también:

L = L(C) = EX L(C(x)) =∑x∈X

p(x)L(C(x)).




Tipos de códigos: definiciones

C es no–singular si ∀x 6= x ′ ∈ X n es C(x) 6= C(x ′), i.e., siC es una aplicación inyectiva.Dado un código C : X → Σ+, definimos C∗, su códigoextensión,

X n C∗−→ Σ+

x = (x1 . . . xn) 7−→ C(x1) . . .C(xn)

C es de decodificación única si su extensión n-ésima, C∗,es no–singular para cualquier n.C es un código instantáneo o libre de prefijo si ningunapalabra–código es prefijo de otra palabra–código.





C es no–singular si ∀x 6= x ′ ∈ X n es C(x) 6= C(x ′), i.e., siC es una aplicación inyectiva.

Dado un código C : X → Σ+, definimos C∗, su códigoextensión,

X n C∗−→ Σ+

x = (x1 . . . xn) 7−→ C(x1) . . .C(xn)







X n C∗−→ Σ+

x = (x1 . . . xn) 7−→ C(x1) . . .C(xn)







X n C∗−→ Σ+

x = (x1 . . . xn) 7−→ C(x1) . . .C(xn)

C es de decodificación única si su extensión n-ésima, C∗,es no–singular para cualquier n.

C es un código instantáneo o libre de prefijo si ningunapalabra–código es prefijo de otra palabra–código.






X n C∗−→ Σ+

x = (x1 . . . xn) 7−→ C(x1) . . .C(xn)





Relación entre los tipos de códigos

La siguiente figura ilustra la relación entre los distintos tipos decódigos

Todos los codigos

No-singulares

Decodificacion unica

Libres de prefijo




Ejemplos de códigos





X C0 C1 C2 C3





X C0 C1 C2 C3

x1 0 0 00 0





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110x4 0 11 110 111





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110x4 0 11 110 111

Singular

Porque C0(x1) = C0(x1) = ′0′.





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110x4 0 11 110 111

Singular No–singular

No es de decodificación única:

11→ 1 |1 x2x211→ 11 x4





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110x4 0 11 110 111

Singular No–singular Decod. única

Porque existe un algoritmo con el que decodifi-camos siempre.





X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10x3 10 01 11 110x4 0 11 110 111

Singular No–singular Decod. única Instantáneo

Ninguna palabra código es prefijo de otra.




Representación en árbol de los Σ∗

DefiniciónDado Σ, |Σ| = d , ordenado, una representación literal de Σ∗ esel árbol d-ario completo con raíz, T = (V ,A) que se obtiene

1 Asignando a cada vértice de V una palabra de Σ∗. Lapalabra vacía λ ∈ Σ∗ se asigna al vértice raíz.

2 Dado un vértice v ∈ V se etiqueta cada arista que sale deél con cada uno de los caracteres de Σ.

3 Dados u, v ∈ V , la arista uv ∈ A sii existe un α ∈ Σ tal quev = uα, considerando u, v ∈ Σ∗.




Ejemplos: árboles de representación de los alfabetos{0,1} y {α, β, γ}





Σ∗ = {0,1}∗





Σ∗ = {0,1}∗

λ

0

0

00

0

00. . .

01

1

01. . .

1

1

10

0

10. . .

11

1

11. . .





Σ∗ = {α, β, γ}∗





Σ∗ = {α, β, γ}∗

λ

α

α

αα

α

αα . . .

αβ

β

αβ . . .

αγ

γ

αγ . . .

β

β

βα

α

βα . . .

ββ

β

ββ . . .

βγ

γ

βγ . . .

γ

γ

γα

α

γα . . .

γβ

β

γβ . . .

γγ

γ

γγ . . .

En T , palabras de la misma longitud ` de Σ∗ están a la mismaprofundidad ` y ordenadas según el orden de Σ.




Representación en árbol de los códigos

•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

•

10

100 101

•

110 111

Identificando un código C con su imagen, consideramosC ⊂ Σ∗, siendo Σ el alfabeto–código. La representación literalde un código será el subárbol del árbol T de representaciónliteral de Σ∗, obtenido al eliminar los subárboles cuyos vérticesno pertenezcan a C.





•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

•

10

100 101

•

110 111

Identificando un código C con su imagen, consideramosC ⊂ Σ∗, siendo Σ el alfabeto–código.

La representación literalde un código será el subárbol del árbol T de representaciónliteral de Σ∗, obtenido al eliminar los subárboles cuyos vérticesno pertenezcan a C.





•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

•

10

100 101

•

110 111

Identificando un código C con su imagen, consideramosC ⊂ Σ∗, siendo Σ el alfabeto–código. La representación literalde un código será el subárbol del árbol T de representaciónliteral de Σ∗,

obtenido al eliminar los subárboles cuyos vérticesno pertenezcan a C.





•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

1

10

100 101

11

110 111

•

0

00

000 001

01

010 011

•

10

100 101

•

110 111

Identificando un código C con su imagen, consideramosC ⊂ Σ∗, siendo Σ el alfabeto–código. La representación literalde un código será el subárbol del árbol T de representaciónliteral de Σ∗, obtenido al eliminar los subárboles cuyos vérticesno pertenezcan a C.




Ejemplos de árboles de códigos

C1b

bc

00 01

bc

10 11

C2b

0 bc

10 bc

110 bc

1110

C3b

0

01

011

0111

C4b

0 bc

10 bc

110 111

C5b

0 1

01 11

Se ve que un código es instantáneo sii todas laspalabras–código son hojas del árbol de su representaciónliteral. Lo son los C1, C2 y C4. El C3 es de decodificación única:lo decodificamos esperarando un 0 y decodificando los bitsrecibidos hasta entonces. El C5 no es instantáneo ni dedecodificación única: es tan sólo no–singular.




Ejemplos de árboles de códigosC1

b

bc

00 01

bc

10 11

C2b

0 bc

10 bc

110 bc

1110

C3b

0

01

011

0111

C4b

0 bc

10 bc

110 111

C5b

0 1

01 11






b

bc

00 01

bc

10 11

C2b

0 bc

10 bc

110 bc

1110

C3b

0

01

011

0111

C4b

0 bc

10 bc

110 111

C5b

0 1

01 11

Se ve que un código es instantáneo sii todas laspalabras–código son hojas del árbol de su representaciónliteral. Lo son los C1, C2 y C4.

El C3 es de decodificación única:lo decodificamos esperarando un 0 y decodificando los bitsrecibidos hasta entonces. El C5 no es instantáneo ni dedecodificación única: es tan sólo no–singular.





b

bc

00 01

bc

10 11

C2b

0 bc

10 bc

110 bc

1110

C3b

0

01

011

0111

C4b

0 bc

10 bc

110 111

C5b

0 1

01 11

Se ve que un código es instantáneo sii todas laspalabras–código son hojas del árbol de su representaciónliteral. Lo son los C1, C2 y C4. El C3 es de decodificación única:lo decodificamos esperarando un 0 y decodificando los bitsrecibidos hasta entonces.

El C5 no es instantáneo ni dedecodificación única: es tan sólo no–singular.





b

bc

00 01

bc

10 11

C2b

0 bc

10 bc

110 bc

1110

C3b

0

01

011

0111

C4b

0 bc

10 bc

110 111

C5b

0 1

01 11





Caracterización algebraica de los códigosinstantáneos

Proposición (Desigualdad de Kraft para códigos instantáneos)

Si C es un código instantáneo o libre de prefijos sobre unalfabeto X , con |X | = r y sobre un alfabeto–código Σ d-ario,|Σ| = d, se verifica la desigualdad de Kraft

r∑i=1

d−li ≤ 1,

siendo li = L(C(xi)), ∀xi ∈ X . Recíprocamente, sili , 1 ≤ i ≤ r , li ∈ Z>0, satisfacen la desigualdad de Kraft, existeun código instantáneo d-ario para X , cuyas longitudes de laspalabras–código son los li .






Si C es un código instantáneo o libre de prefijos sobre unalfabeto X , con |X | = r y sobre un alfabeto–código Σ d-ario,|Σ| = d,

se verifica la desigualdad de Kraft

r∑i=1

d−li ≤ 1,








r∑i=1

d−li ≤ 1,








r∑i=1

d−li ≤ 1,

siendo li = L(C(xi)), ∀xi ∈ X .

Recíprocamente, sili , 1 ≤ i ≤ r , li ∈ Z>0, satisfacen la desigualdad de Kraft, existeun código instantáneo d-ario para X , cuyas longitudes de laspalabras–código son los li .







r∑i=1

d−li ≤ 1,

siendo li = L(C(xi)), ∀xi ∈ X . Recíprocamente, sili , 1 ≤ i ≤ r , li ∈ Z>0, satisfacen la desigualdad de Kraft,

existeun código instantáneo d-ario para X , cuyas longitudes de laspalabras–código son los li .







r∑i=1

d−li ≤ 1,





Códigos instantáneos de longitud media mínima

Los códigos instantáneos son de codificación y decodificaciónfáciles: ¿pueden ser, además, de longitud media mínima?Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ). Su longitud media L ha deser mínima.Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑

i=1d−li ≤ 1 (Kraft)

li ∈ Z>0, 1 ≤ i ≤ r





Los códigos instantáneos son de codificación y decodificaciónfáciles:

¿pueden ser, además, de longitud media mínima?Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ). Su longitud media L ha deser mínima.Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑


li ∈ Z>0, 1 ≤ i ≤ r





Los códigos instantáneos son de codificación y decodificaciónfáciles: ¿pueden ser, además, de longitud media mínima?

Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ). Su longitud media L ha deser mínima.Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑


li ∈ Z>0, 1 ≤ i ≤ r





Los códigos instantáneos son de codificación y decodificaciónfáciles: ¿pueden ser, además, de longitud media mínima?Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ).

Su longitud media L ha deser mínima.Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑


li ∈ Z>0, 1 ≤ i ≤ r





Los códigos instantáneos son de codificación y decodificaciónfáciles: ¿pueden ser, además, de longitud media mínima?Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ). Su longitud media L ha deser mínima.

Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑


li ∈ Z>0, 1 ≤ i ≤ r





Los códigos instantáneos son de codificación y decodificaciónfáciles: ¿pueden ser, además, de longitud media mínima?Se busca, pues, un código d-ario instantáneo, C, para unafuente simple S = (X , {pi}1≤i≤r ). Su longitud media L ha deser mínima.Se trata de un problema de extremos condicionados:

Minimizar: L =r∑

i=1

pi li ,

Restricciones:

r∑


li ∈ Z>0, 1 ≤ i ≤ r




Códigos de Shannon (I)Solución al problema de extremos condicionados

Los siguientes valores resuelven el problema de extremoscondicionados anterior, sin la restricciones li ∈ Z>0:

l∗i = − logd pi ,

L∗

= −r∑

i=1pi logd pi = Hd (S),

donde Hd (S) = H(S) log d es la entropía de la fuente en d-bits.Ahora considerando que li ∈ Z>0, 1 ≤ i ≤ r , se obtiene

l(s)i = dl∗i e = d− logd pie .







L∗

= −r∑


donde Hd (S) = H(S) log d es la entropía de la fuente en d-bits.

Ahora considerando que li ∈ Z>0, 1 ≤ i ≤ r , se obtiene








L∗

= −r∑


donde Hd (S) = H(S) log d es la entropía de la fuente en d-bits.Ahora considerando que li ∈ Z>0, 1 ≤ i ≤ r , se obtiene





Códigos de Shannon (II)

Los valores l(s)i definen los llamados códigos de Shannon, que

son instantáneos y que verifican el siguiente resultado

Proposición (SCT para los códigos de Shannon)

Dada una fuente simple S = (X , {pi}1≤i≤r ), existe un códigod-ario instantáneo de longitud media mínima definido por laslongitudes

l(s)i = d− logd pie ,

llamado código de Shannon, tal que

Hd (S) ≤ L(s) ≤ Hd (S) + 1.










llamado código de Shannon,

tal que

Hd (S) ≤ L(s) ≤ Hd (S) + 1.










llamado código de Shannon, tal que

Hd (S) ≤ L(s) ≤ Hd (S) + 1.




Códigos de Shannon (III)Ejemplo

Sea la fuente simple S =({x1, x2, x3, x4}, {1

3 ,13 ,

14 ,

112}). Vamos

a construir el código de Shannon sobre Σ = {0,1}.

Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4

Código: C(x1) = 00, C(x2) = 01, C(x3) = 10, C(x4) = 1100.Longitud media: L

(s)= 2′1667 bits y entropía: H(S) = 1′8554

bits, cumpliéndose que 1′8554 < 2′1667 < 2′8554.






3 ,13 ,

14 ,

112}).

Vamosa construir el código de Shannon sobre Σ = {0,1}.

Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4









3 ,13 ,

14 ,

112}). Vamos


Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4









3 ,13 ,

14 ,

112}). Vamos


Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4

Código: C(x1) = 00, C(x2) = 01, C(x3) = 10, C(x4) = 1100.

Longitud media: L(s)

= 2′1667 bits y entropía: H(S) = 1′8554bits, cumpliéndose que 1′8554 < 2′1667 < 2′8554.






3 ,13 ,

14 ,

112}). Vamos


Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4


(s)= 2′1667 bits

y entropía: H(S) = 1′8554bits, cumpliéndose que 1′8554 < 2′1667 < 2′8554.






3 ,13 ,

14 ,

112}). Vamos


Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4



bits

, cumpliéndose que 1′8554 < 2′1667 < 2′8554.






3 ,13 ,

14 ,

112}). Vamos


Longitudes:

l(s)1 = L(C(x1)) =

⌈− log 13

⌉= 2

l(s)2 = L(C(x2)) =

⌈− log 13

⌉= 2

l(s)3 = L(C(x3)) =

⌈− log 14

⌉= 2

l(s)4 = L(C(x4)) =

⌈− log 112

⌉= 4







Códigos optimales

Obsérvese que el código instantáneo

C(o)(x1) = 0, C(o)(x2) = 10, C(o)(x3) = 110, C(o)(x4) = 111

para la fuente S anterior tiene longitud media menor que el deShannon

L(o)

= 2 bits < L(s)

= 2′1667 bits

Definición (Códigos optimales)

Diremos que un código C(o) instantáneo es optimal para unafuente S si su longitud media L

(o)es menor o igual que la de

cualquier otro código instantáneo para la misma fuente


introducción a los códigos compresores - parte i de la lección 2

Documents