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)
c. 0<=H<=log2 2
Ejercicio 03
Para la siguiente fuente<?b>
S = [P(A) = 0:4; P(B) = 0:3; P(C) = 0:2; P(D) = 0:1]<?b>
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.