Transmisión de información en canales sin ruido

Desigualdad de Kraft, primer teorema de Shannon

Jesús Martínez Mateo

[email protected]

Departamento de Matemática Aplicada a las TIC

E.T.S. Ingenieros Informáticos
Universidad Politécnica de Madrid

Grado en Ingeniería Informática

Curso 2023/24

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 1 / 13

Nociones básicas

Definiciones
Llamamos alfabeto a un conjunto finito de elementos
A = {a1 , a2 , . . . , aq } con |A| = q > 1.
Llamamos símbolos a los elementos de un alfabeto.
Llamamos palabras a n-tuplas o sucesiones de n elementos de un
alfabeto. Decimos que y ∈ An es una palabra de longitud n.
Llamamos código a un conjunto, no vacío, de palabras. A las
palabras que componen un código las llamamos palabras código.

Observación. Nótese que, a partir de la definición anterior, un código

puede tener palabras de distinta longitud.

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 2 / 13

Nociones básicas
Códigos

Definición
Sea A un alfabeto. Un n-código de bloque es un conjunto no vacío de
palabras de longitud n.

Es decir, todo subconjunto C ⊆ An con C ̸= ∅ es un n-código de bloque.

Definición
Sea C un código. El tamaño de C viene determinado por el número de
palabras código que contiene, y lo denotamos por |C|.

Puesto que C es un conjunto, el tamaño de un código coincide con el

cardinal de dicho conjunto.

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 3 / 13

Nociones básicas
Ejemplos de códigos

Observación. Sólo trabajaremos con códigos binarios donde 0 y 1 son los

únicos símbolos del alfabeto, es decir, A = {0, 1}. Una palabra es, por lo
tanto, una secuencia o tupla de ceros y unos.
Ejemplos
La tuplas (0, 1) y (1, 1, 0) son dos palabras de longitud 2 y 3 que
denotaremos por comodidad como 01 y 110, respectivamente.
El conjunto C = {00, 01, 100, 110} es un código binario de tamaño 4.
Las palabras 00, 01, 100 y 110 son palabras código.
El conjunto C = {0, 10, 110, 1110, 11110} es también un código
binario de tamaño 5.
El conjunto C = {0000, 0011, 1100} es un 4-código binario de bloque
de tamaño 3.

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 4 / 13

Codificación de información

Definición
Sea X una fuente de información con alfabeto X = {x1 , x2 , . . . , xn },
cuyos símbolos x1 , x2 , . . . , xn son generedos por la fuente conforme a una
determinada distribución de probabilidad p(x1 ), p(x2 ), . . . , p(xn ). Y sea C
un código de tamaño n definido a partir de un alfabeto
A = {a1 , a2 , . . . , aq }. Llamamos codificación de la fuente X mediante el
código C a una aplicación c que asocia cada símbolo de la fuente X con
una palabra código de C:

c: X → C
xi 7→ y ∈ A∗

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 5 / 13

Clasificación de códigos
Definiciones
Decimos que un código C es no singular si todas sus palabras son
distintas, es decir, ∀x, x′ ∈ X si x ̸= x′ ⇒ c(x) ̸= c(x′ ).
Decimos que un código C es unívocamente decodificable si su
extensión, c(x1 x2 ...xn ) = c(x1 )c(x2 )...c(xn ), es no singular.
Decimos que un código es instantáneo cuando ninguna palabra es
prefijo de otra palabra código.


singular


  (
instantaneo

 
Código unívocamente decodificable




 no singular no instantaneo
 


 unívocamente no decodificable

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 6 / 13

Clasificación de códigos

Ejemplo
Queremos codificar una fuente de información X con alfabeto
X = {x1 , x2 , x3 , x4 } mediante un código binario. Veamos un ejemplo de
distintos tipos de códigos que podemos utilizar para codificar dicha fuente.
Código singular: C = {0, 0, 0, 0}.
Código no singular, pero no unívocamente no decodificable:
C = {0, 01, 010, 10}.
Código unívocamente decodificable, pero no instantáneo:
C = {10, 00, 11, 110}.
Código instantaneo: C = {0, 10, 110, 111}.

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 7 / 13

Desigualdad de Kraft
Teorema
Todo código instantáneo definido sobre un alfabeto A de longitud |A|, con
palabras de longitud L1 , L2 , ..., Ln , debe satisfacer la desigualdad
n
|A|−Li ≤ 1
X

i=1

Recíprocamente, dado un conjunto de longitudes que satisface dicha

desigualdad, existe un código instantáneo con palabras de dicha longitud.

Demostración.
Construimos el árbol |A|-ario de altura Lmáx . Nótese que ninguna palabra
puede ser predecesora de otra palabra código. Una palabra en el nivel Li
tiene |A|Lmáx −Li descendientes en el nivel Lmáx . Por lo tanto

|A|Lmáx −Li ≤ |A|Lmáx

X

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 8 / 13

Desigualdad de Kraft

Ejemplo
Consideramos códigos instantaneos binarios, es decir, definidos sobre el
alfabeto A = {0, 1}, y por lo tanto |A| = 2, cuya longitud máxima de
palabra es Lmáx = 5.
Es evidente que un posible código es el formado por las 25 palabras
de longitud 5.
Si un código incluye una palabra de longitud inferior a 5, por ejemplo
1101, entonces las palabras 11010 y 11011 no pueden pertenecer al
código.
Análogamente, si un código incluye una palabra de longitud 2, por
ejemplo 01, entonces hay 23 palabras que no pueden perteneder al
código (todas las palabras de longitud 5 que empiezan por 01).

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 9 / 13

Longitud de código óptima (I)
Sea X una fuente de información con entropía
X 1
H(X) = p(xi ) log
i
p(xi )

Codificamos la fuente X mediante un código que asigna a casa símbolo xi

una palabra de longitud Li . La longitud promedio de la fuente codificada es
X
L= p(xi )Li
i

Si codificamos cada símbolo de la fuente mediante una palabra código de

longitud igual a la información aportada por el símbolo, tenemos entonces
que
1 
X 
H(X) = p(xi ) log 
p(xi ) 

i 1
Li = log ⇒ L = H(X)
L=
X
p(xi )Li


 p(xi )

i

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 10 / 13

Longitud de código óptima (II)

La longitud promedio de las palabras utilizadas para codificar la fuente

coincide entonces con la entropía de la fuente. Sin embargo, nótese que la
longitud de cada palabra Li = log p(x1 i ) puede no ser un entero, en cuyo
caso para satisfacer la desigualdad de Kraft debemos escoger el entero
inmediatamente superior
1
Li = ⌈log ⌉
p(xi )

En efecto,
1 1
X −⌈log ⌉ X − log X
|A| p(xi )
≤ |A| p(xi )
= p(xi ) = 1
i i i

Luego la entropía de una fuente nos proporciona una medida de la

longitud óptima en la codificación de dicha fuente.

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 11 / 13

Longitud de código óptima (III)
Tenemos también que la longitud de cada palabra código satisface
1 1
log ≤ Li < log +1
p(xi ) p(xi )

Podemos ahora multiplicar cada una de las longitudes por p(xi )

1 1
p(xi ) log ≤ p(xi )Li < p(xi ) log +1
p(xi ) p(xi )

y calcular la suma de todas ellas

X 1 X X 1
p(xi ) log ≤ p(xi )Li < p(xi ) log +1
i
p(xi ) i i
p(xi )

Luego, tenemos que

H(X) ≤ L < H(X) + 1

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 12 / 13

Longitud de código óptima (III)
Aplicando la extensión de orden n a la fuente original X tenemos que

H(X n ) ≤ L(n) < H(X n ) + 1

o equivalentemente

L(n) 1
H(X) ≤ < H(X) +
n n
De donde deducimos que las extensiones sucesivas de una fuente de
información permiten que la longitud promedia de la fuente codificada
alcance la longitud óptima y por lo tanto, la entropía de la fuente

L(n)
⇒ lı́m = H(X)
n→∞ n

Jesús Martínez Mateo (DMATIC) Compresión de datos GII - Curso 2023/24 13 / 13