Taller

16.36: Ingeniería de sistemas de comunicación Clase 5: Codificación de la fuente

Eytan Modiano

Eytan Modiano Slide 1

Codificación de la fuente

Alfabeto de fuente {a1..aN}

Codificar

Alfabeto de canal {c1..cN}

• • •

Símbolos de la fuente
– – – Letras del alfabeto, símbolos ASCII, diccionario de inglés, etc... Voz cuantificada En general puede tener un número arbitrario desímbolos de canal
Típicamente {0,1} para un canal binario

Símbolos del canal

Objetivos de la codificación de la fuente
– – Decodabilidad unívoca Compresión
Codificar el alfabeto utilizando el menor número posible de símbolos de canal

Eytan Modiano Slide 2

Compresión

•

Compresión sin pérdidas
– – Permite la decodificación sin errores Decodabilidad unívoca sin ambigüedad

•Compresión con pérdidas
– Tal vez el código no sea codificable unívocamente, pero hay una probabilidad enorme de que se codifique correctamente

Eytan Modiano Slide 3

Códigos (libres) prefijo

•

Un código prefijo es un código en el cual ninguna palabra se antepone a otra
– – Los códigos prefijo son decodificables unívocamente Los códigos prefijo son decodificables instantáneamente•

La siguiente desigualdad importante se aplica a códigos prefijo y en general a todos los códigos decodificables unívocamente

Desigualdad de Kraft
Sea n1…nk la longitud de palabras código en un código prefijo (o en cualquiera decodificable unívocamente). Entonces,

2 − ni ≤ 1 ∑
i =1
Eytan Modiano Slide 4

k

Demostración de la desigualdad de Kraft

• •

Demostración sólopara códigos prefijo
– Se puede ampliar a todos los códigos decodificables unívocamente

Aplicar palabras código a un árbol binario
– – Las palabras código deben ser las hojas del árbol Una palabra código de longitud n i es una hoja a profundidad ni

•

Sea n k ≥ nk-1 … ≥ n1 => profundidad del árbol = nk
– – – En un árbol binario de profundidad n k, son posibles hasta 2nk hojas (si todaslas hojas están a profundidad n k) Cada hoja a profundidad n i < nk elimina una fracción 1/2ni de las hojas a profundidad n k => elimina 2nk -ni de las hojas a profundidad nk De ahí que,

2 n k − ni ≤ 2 n k ⇒ ∑ 2 − ni ≤ 1 ∑
i =1 i =1
Eytan Modiano Slide 5

k

k

Desigualdad de Kraft - recíproca
•
Si un conjunto de números enteros {n1..nk} satisface la desigualdad de Kraft el códigoprefijo a se puede hallar con longitudes de palabras código {n1..nk}
– De ahí que la desigualdad de Kraft sea condición suficiente y necesaria para la existencia de un código decodificable unívocamente

•

La demostración se realiza mediante la construcción de un código
– Dado {n 1..nk}, comenzando con n1, asignar nodo al nivel ni para la palabra código de longitud n i. La desigualdad de Kraftgarantiza tal asignación

Ejemplo: n = {2,2,2,3,3}, (verificar que la desigualdad de Kraft se sostiene)

n3 n5 n4

n2

n1

Eytan Modiano Slide 6

Longitud media de una palabra código
•
La desigualdad de Kraft no nos dice nada sobre la longitud media de una palabra código. El siguiente teorema da una cota reducida estrecha

Teorema: dada una fuente con alfabeto {a1..ak},probabilidades {p1..pk}, y entropía H(X), la longitud media de un código binario decodificable unívocamente satisface: n ≥ H(X) Demostración:
i=k 1 i=k 2 − ni H ( X ) − n = ∑ pi log − ∑ pi ni = ∑ pi log pi i =1 pi i =1 i =1 i=k

log inequality => log( X ) ≤ X − 1 =>  2 − ni  i = k − ni − 1 = ∑ 2 − 1 ≤ 0 H ( X ) − n ≤ ∑ pi  i =1  pi  i =1
i=k
Eytan Modiano Slide 7

Longitud media de una palabracódigo
•
¿Podemos construir códigos próximos a H(X)?

Teorema: dada una fuente con alfabeto {a 1..ak}, probabilidades {p1..pk}, y entropía H(X), es posible construir un código prefijo (por tanto, unívocamente decodificable) de longitud media que satisfaga:

n < H(X) + 1
Demostración (Codigos Shannon - Fano):
 1  1 Sea ni = log( ) ⇒ ni ≥ log( ) ⇒ 2 − ni ≤ pi pi  pi  ⇒ ∑ 2 − ni ≤ ∑...