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 tres longitudes medias es menor que la entropía de la fuente, lo cual garantiza que las tres codificaciones son sin pérdida de información.

Ejercicio 04

¿Cuánto vale la entropía y la longitud de la codificación de cada símbolo para las fuentes de información de los siguientes casos? Asumir que la codificación se da bajo el código óptimo.

a. 2 símbolos equiprobables

b. 4 símbolos equiprobables

c. 6 símbolos equiprobables

d. 8 símbolos equiprobables

e. 10 símbolos equiprobables

f. N símbolos equiprobables

Rta:

H(S) = SUMATORIA seS P(p0) * I(s0) = #S * (1/#S) * -log2(1/#S) = log2(#S)

C es óptimo sii L(C) es mínima (i.e., todo otro código sobre S tiene mayor o igual longitud promedio). --> H(S) = L(C).

a.log2(2) = 1

b.log2(4) = 2

c.log2(6)

d.log2(8) = 3

e.log2(10)

f.log2(N)