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

FuentesCódigos (compresores)

Índice

1 Fuentes

2 Códigos (compresores)

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

FuentesCó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)

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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 .

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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 .

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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 .

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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 .

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

FuentesCódigos (compresores)

Definición de fuenteTipos de fuentesEntropí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 .

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

FuentesCódigos (compresores)

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

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

)

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

FuentesCódigos (compresores)

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

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

)

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

FuentesCódigos (compresores)

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

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

)

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

FuentesCódigos (compresores)

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

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

)

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

FuentesCódigos (compresores)

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

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)

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

FuentesCódigos (compresores)

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

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)

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

FuentesCódigos (compresores)

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

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)

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

FuentesCódigos (compresores)

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

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)

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

FuentesCódigos (compresores)

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

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)

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

FuentesCódigos (compresores)

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

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).

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

FuentesCódigos (compresores)

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

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).

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

FuentesCódigos (compresores)

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

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).

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

FuentesCódigos (compresores)

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

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).

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

FuentesCódigos (compresores)

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

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).

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

FuentesCódigos (compresores)

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

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

FuentesCó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.

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

FuentesCódigos (compresores)

Definición de códigoTipos de códigosCódigos 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.

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

FuentesCó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.

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

FuentesCó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.

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

FuentesCó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.

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

FuentesCódigos (compresores)

Definición de códigoTipos de códigosCódigos 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.

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

FuentesCódigos (compresores)

Definición de códigoTipos de códigosCódigos 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.

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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)).

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

X C0 C1 C2 C3

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

X C0 C1 C2 C3

x1 0 0 00 0

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

X C0 C1 C2 C3

x1 0 0 00 0x2 01 1 10 10

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

X C0 C1 C2 C3

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

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

X C0 C1 C2 C3

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

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

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′.

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

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

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

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.

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

FuentesCódigos (compresores)

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

Ejemplos de códigos

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.

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

FuentesCódigos (compresores)

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

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 ∈ Σ∗.

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

FuentesCódigos (compresores)

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

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 ∈ Σ∗.

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

FuentesCódigos (compresores)

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

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 ∈ Σ∗.

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

FuentesCódigos (compresores)

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

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 ∈ Σ∗.

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

FuentesCódigos (compresores)

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

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 ∈ Σ∗.

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

Σ∗ = {0,1}∗

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

FuentesCódigos (compresores)

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

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

Σ∗ = {0,1}∗

λ

0

0

00

0

00. . .

01

1

01. . .

1

1

10

0

10. . .

11

1

11. . .

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

FuentesCódigos (compresores)

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

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

Σ∗ = {α, β, γ}∗

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

FuentesCódigos (compresores)

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

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

Σ∗ = {α, β, γ}∗

λ

α

α

αα

α

αα . . .

αβ

β

αβ . . .

αγ

γ

αγ . . .

β

β

βα

α

βα . . .

ββ

β

ββ . . .

βγ

γ

βγ . . .

γ

γ

γα

α

γα . . .

γβ

β

γβ . . .

γγ

γ

γγ . . .

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

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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

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.

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

FuentesCódigos (compresores)

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

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

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.

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

FuentesCódigos (compresores)

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

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

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.

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

FuentesCódigos (compresores)

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

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

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.

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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 .

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

Códigos de Shannon (III)Ejemplo

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

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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′8554bits, cumpliéndose que 1′8554 < 2′1667 < 2′8554.

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

FuentesCódigos (compresores)

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

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′8554bits, cumpliéndose que 1′8554 < 2′1667 < 2′8554.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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.

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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

FuentesCódigos (compresores)

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

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

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