Práctica 1: Transmisión de información (Teoría de las Comunicaciones)

Ejercicio 01

¿Qué cantidad de información se obtiene de la observación de los siguientes experimentos u objetos?

a. La tirada de una moneda equilibrada.

b. La tirada de un dado equilibrado.

c. Un codón (triplete de bases de ADN) en un genoma, donde cada base puede tomar 4 valores: A,T,C,G.

d. Una letra en un libro de Borges.

Rta:

Información de un evento: I(s) = -log2(P(s)) con P(s) la probabilidad del evento s

a. I(1/2) = -log2(1/2) = 1 bit

b. I(1/6) = -log2(1/6) = 2,58 bits

c. I( (1/4)^3 ) = -log2( (1/4)^3 ) = -log2(1/64) = 6 bits

d. I(#Cantidad Aparicion de letra "?"/ #Cantidad total de letras del libro)

Ejercicio 02

Una fuente de información binaria con memoria nula produce el símbolo s0 con probabilidad p0 y el símbolo s1 con probabilidad p1 = 1 - p0.

a. Formular la entropía de la fuente como función de p0.

b. Graficar H(p0).

c. Dar una interpretación de los puntos de la gráfica que considere interesantes.

Rta:

Entropía de una fuente: H(S) = SUMATORIAseS P(s) I(s)

a. H(S) = p0 * I(s0) + (1 - p0) * I(s1) = p0 * -log2(p0) + (1 - p0) * -log2(1 - p0)

b.

c. 0<=H<=log2 2

Ejercicio 03

Para la siguiente fuente

S = [P(A) = 0:4; P(B) = 0:3; P(C) = 0:2; P(D) = 0:1]

se proponen 3 códigos posibles

1. A = 00 ; B = 01 ; C = 11 ; D = 010

2. A = 0 ; B = 01 ; C = 011; D = 111

3. A = 1 ; B = 01 ; C = 001 ; D = 0001

a. ¿Cuáles son instantáneos?

b. ¿Cuáles son unívocamente decodificables?

c. ¿Cuál es más eficiente (H/L)?

d. ¿Alguno presenta pérdida de información?

Rta:

a. Un código es instantáneo o libre de prefijos si no codifica ningún símbolo como prefijo de otro.

1.No, B es prefijo de D.

2.No, A es prefijo de B.

3.Si, bit 1 sirve como limitador.

b. Un código es unívocamente decodificable si ninguna tira de símbolos del alfabeto código admite más de una única decodificación.

1.Si.

2.Si.

3.Si. Instantaneo --> Unívocamente decodificable.

c. Largo promedio de un código: L(C) = SUMATORIAseS P(s) l(C(s)) con l(C(s)) el largo de la codificación del símbolo s

L(C1) = P(A) * l(C(A)) + P(B) * l(C(B)) + P(C) * l(C(C)) + P(D) * l(C(D)) = 0.4 * 2 + 0.3 * 2 + 0.2 * 2 + 0.1 * 3 = 2.1

L(C2) = 1.9

L(C3) = 2

Dado que las probabilidades no cambian, la entropía de S es siempre igual (puntualmente, su valor es H(S) = 1,85). Luego, ofrecerá mejor rendimiento aquél código que minimice su longitud media. A simple vista queda claro que el código buscado es C2, cuya longitud media es L(C2) = 1,9.

d. Un código C sobre una fuente S codifica sin pérdida de información sii H(S) <= L(C)

Tenemos que H(S) < L(C2) < L(C3) < L(C1). Luego, ninguna de las dos longitudes medias es menor que la entropía de la fuente, lo cual garantiza que ambas codificaciones son sin pérdida de información.