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). Siempre que H(S) sea potencia de 2, sino el próximo valor entero.

a. H(S) = L(C) = log2(2) = 1

b. H(S) = L(C) = log2(4) = 2

c. H(S) = log2(6) L(C) = [log2(6)] = 3

d. H(S) = L(C) = log2(8) = 3

e. H(S) = log2(10) L(C) = [log2(10)] = 4

f. H(S) = log2(N) L(C) = [log2(N)]

Ejercicio 05

Considere una señal de video en escala de grises que transmite imágenes a una resolución 640 x 480 píxeles, de los cuales cada uno puede asumir 10 niveles diferentes de brillo. Supongamos que la tasa de transmisión es de 30 imágenes por segundo y que la relación señal a ruido es de 30 dB.

a. Calcular la entropía de la fuente si todas las imágenes fueran equiprobables.

b. ¿Cuántos bits son necesarios para codificar cada imagen de manera óptima e instantánea con un código que asigne el mismo largo a todas las imágenes?

c. Calcular el ancho de banda mínimo requerido para soportar la transmisión de la señal resultante.

Rta:

a.log2(#S) (fuente equiprobables), Donde #S = 10^(640 x 480), entonces log2(10^(640 x 480)) = (640 x 480) * log2(10) = 1,02

b. En esta fuente equiprobable, tenemos que H(S) = log2(n), no siendo n una potencia de 2. Esto implica que no podemos pensar en recurrir a un código (óptimo) que asigne log2(n) bits por imagen, pues por supuesto estos valores deben ser números enteros. No obstante, la aproximación más cercana a este valor es tomar exactamente [log2(n)](próximo número entero) bits por imagen. De esta forma podremos armar un código que sea instantáneo (cada imagen recibe una tira de bits distinta) y “localmente óptimo”, entendiendo por esto que todo otro código que mapee cada imagen a una tira de bits de igual largo debe necesariamente poseer una longitud media igual o mayor.

L(C) = 2

c.

Teorema de Shannon: C[bps] = B[Hz] * log2(1 + SNR[veces]) con SNR[veces] = 10SNR[dB]=10 y B el ancho de banda disponible. Velocidad de transmisión sin pérdida de información: Vtx[bps] <= C[bps], con V max tx = C

Para responder este ítem, hay que usar el teorema de Shannon: C = B * log2(1 + SNR). Primero, la relación señal-ruido hay que pasarla de decibeles a veces: SNR = 1030/10 = 1000. Luego, como se necesitan 30 imágenes por segundo, la capacidad de canal debe ser mayor o igual que L(C) * 30 bps. Entonces, B = 60 / log2(1001) = 6.02 Hz.

Vtx[bps] = 30 (imagenes x segundo) * 2 (L(C)) = 60 bps

Vtx[bps] <= C[bps]

B[Hz] = 60/log2(1+ 10^(30db/10)) = 6.02