Nombre: Jhaneth Paco Rios

Ci: 8359722

TEORÍA DE LA INFORMACIÓN Y CODIFICACIÓN

INF – 164

PRÁCTICA 2
1. Responder a las siguientes preguntas:

a) Codificar se refiere al proceso de asignar códigos a símbolos o mensajes según ciertas reglas o
algoritmos. En el contexto de la teoría de la información, la codificación implica representar la
información de manera eficiente utilizando secuencias de símbolos.

b) Decodificar: Decodificar es el proceso inverso a codificar. Implica la conversión de secuencias de

símbolos o códigos en el mensaje original o la información original. El decodificador interpreta las
secuencias de códigos para recuperar la información original.

c) Propiedades de los Códigos:

Unicidad: Cada mensaje tiene un único código asociado.

Instantaneidad: Ningún código es prefijo de otro código (código instantáneo).

Eficiencia: El código debe ser eficiente en términos de longitud, es decir, minimizar la longitud media
ponderada de las palabras de código.

d) Código Bloque: Un código bloque es un tipo de código donde cada palabra de código tiene la
misma longitud. En un código bloque, el mensaje se divide en bloques y cada bloque se asigna a una
palabra de código de igual longitud.

e) Extensión n-sima de un Código Bloque: La extensión n-sima de un código bloque implica tomar
bloques consecutivos de símbolos y asignarles las palabras de código correspondientes del código
bloque original. Esto permite codificar mensajes más largos de manera eficiente.

f) Código Unívocamente Decodificable: Un código unívocamente decodificable es aquel en el cual

ninguna secuencia de códigos puede ser interpretada de dos maneras diferentes. La decodificación
es única y sin ambigüedades.

g) Código Instantáneo: Un código instantáneo es un tipo especial de código unívocamente

decodificable en el cual ninguna palabra de código es prefijo de otra. La decodificación puede
realizarse de manera incremental, sin necesidad de esperar la llegada de más símbolos para
determinar una palabra de código.

h) Inecuación de Kraft: La inecuación de Kraft es una condición matemática que debe cumplir la
longitud de las palabras de código en un conjunto para garantizar la existencia de un código
instantáneo.

i) Teorema de McMillan: El Teorema de McMillan establece que si un conjunto de longitudes de

código satisface la inecuación de Kraft, entonces existe un código instantáneo con esas longitudes.
 q
j) Relación ∑ Li PI =1 Esta relación representa la condición de unicidad en un código
i=1
unívocamente decodificable, donde Li es la longitud de la i-ésima palabra de código y Pi es la
probabilidad de ocurrencia de esa palabra.

k) Código Compacto: Un código se considera compacto si tiene una longitud media mínima y se
acerca a la entropía de la fuente de información.

H r (s) 1
l) Relaciones ≤ L≤ H r ( s ) +
N n
Estas relaciones están relacionadas con la eficiencia de un código. Hr(S) es la entropía de la fuente
de información, L es la longitud media de las palabras de código, y n es la longitud máxima de las
palabras de código en un código bloque. Estas relaciones establecen límites para la eficiencia del
código.

2. Determinar que propiedades cumplen los siguientes códigos:

Fuente Código A Código B Código C Código D

s1 000 0 0 01
s2 001 10 10 011
s3 010 110 1100 10
s4 011 1110 1101 1000
s5 100 11110 1110 1100
s6 101 111110 1111 0111
a) Es no singular, pero no es unívocamente decodificable
b) Es no singular y unívocamente decodificable
c) es singular y es unívocamente decodificable
d) es no singular y es unívocamente decodificable

[Link] las longitudes de los siguientes códigos:

Código Longitudes
A 2, 2, 2, 4, 4, 4
B 2, 2, 2, 3, 1
C 1, 1, 2, 2, 2, 2
D 2, 1, 2, 4, 1
E 1, 1, 2, 3, 3
F 1, 4, 6

a) ¿Se puede construir un código instantáneo binario? De ser así de un ejemplo de ese
código.
b) ¿Se puede construir un código instantáneo trinario? De ser así de un ejemplo de ese
código.
Caso A:
Código Longitudes A:
2, 2, 4, 4, 4
Si ordenamos las longitudes de mayor a menor, obtenemos: 4, 4, 4, 2, 2. Ahora, al observar
si alguna longitud es prefijo de otra, vemos que no hay ningún problema. Entonces, sí se
puede construir un código instantáneo binario. Un ejemplo podría ser:
0 -> 4
10 -> 2
110 -> 2
111 -> 4
Caso B:
Código Longitudes B:
2, 2, 2, 3, 1
Ordenando de mayor a menor: 3, 2, 2, 2, 1. Verificando si hay algún prefijo, notamos que no
hay problemas. Entonces, sí se puede construir un código instantáneo binario. Un ejemplo
podría ser:
0 -> 3
10 -> 2
110 -> 2
111 -> 1
Construcción de un código instantáneo trinario:
Para construir un código instantáneo trinario, debemos verificar si las longitudes permiten
una asignación que cumple con la condición del prefijo único. Observemos el caso F:
Caso F:
Código Longitudes F:
1, 4, 6
Ordenando de mayor a menor: 6, 4, 1. Verificamos si hay algún prefijo, y vemos que no hay
problemas. Entonces, sí se puede construir un código instantáneo trinario. Un ejemplo
podría ser:
0 -> 6
10 -> 4
110 -> 1
 4 Se tiene una fuente de 29 símbolos y un alfabeto código de 4 símbolos. Si se han
escogido 2 palabras de longitud 1 y 3 de longitud 2.

a) ¿Cuántos prefijos de longitud 3 se pueden escoger (como máximo) si se quiere

formar un código instantáneo?
b) Construya el árbol de codificación.
c) Pruebe que es instantáneo.
a

raíz
/|\
/ | \
0 1 2
/\
0 1
/ \
0 1
En este ejemplo, las hojas representan las palabras codificadas. Por ejemplo, 00 podría
representar la primera palabra de longitud 2, 10 podría representar la segunda palabra de
longitud 2, y así sucesivamente.

C Prueba de que es instantáneo:

Para probar que el código es instantáneo, necesitamos verificar que ninguna palabra sea
prefijo de otra. En este árbol de codificación, esto se cumple ya que ninguna hoja es prefijo
de otra hoja. Cada palabra se puede identificar de manera única siguiendo el camino desde
la raíz hasta la hoja correspondiente. Por lo tanto, el código es instantáneo.
5 Demostrar la inecuación de Kraft:
q

 r li  1
i1
6 H r (S) , y la
Determinar Fuente P(si ) Código A Código B Código C Código D eficiencia
la 1/2 0 0 0 1010 de los
s1
s2 1/4 01 10 100 001 siguientes
códigos:
s3 1/16 011 110 101 101
s4 1/16 0111 1110 110 0001
s5 1/16 01111 1011 111 1101
s6 1/16 011111 1101 001 1011
longitud media, la
7 Demostrar la siguiente relación:

H (S)  L
8 Considere la siguiente fuente de información:

Símbolo s1 s2 s3 s4 s5 s6 s7
P(si ) 1/4 1/4 1/4 1/16 1/16 1/16 1/16

a. Calcular H (S ) y H 4 (S) .
b. Encontrar códigos compactos de H(S) cuando x=0,1 x=0,1,2,3
c. Calcular el valor de L en ambos casos.
9 Demostrar el primer Teorema de Shannon:

Hr (S)  L  Hr (S) 1