| Revisión actual |
Tu texto |
| Línea 40: |
Línea 40: |
| <b>a.</b> H(S) = p0 * I(s0) + (1 - p0) * I(s1) = p0 * -log2(p0) + (1 - p0) * -log2(1 - p0) | | <b>a.</b> H(S) = p0 * I(s0) + (1 - p0) * I(s1) = p0 * -log2(p0) + (1 - p0) * -log2(1 - p0) |
|
| |
|
| <b>b.</b>[[Image:entropia-grafica.jpg]] | | <b>b.</b>[[Image:https://upccommunications.files.wordpress.com/2011/01/entropia-grafica.jpg]] |
| | |
| <b>c. 0<=H<=log2 2</b>
| |
| | |
| ===Ejercicio 03===
| |
| | |
| <b>Para la siguiente fuente</b>
| |
| | |
| <b>S = [P(A) = 0:4; P(B) = 0:3; P(C) = 0:2; P(D) = 0:1]</b>
| |
| | |
| <b>se proponen 3 códigos posibles</b>
| |
| | |
| <b> 1. A = 00 ; B = 01 ; C = 11 ; D = 010</b>
| |
| | |
| <b> 2. A = 0 ; B = 01 ; C = 011; D = 111</b>
| |
| | |
| <b> 3. A = 1 ; B = 01 ; C = 001 ; D = 0001</b>
| |
| | |
| <b>a. ¿Cuáles son instantáneos?</b>
| |
| | |
| <b>b. ¿Cuáles son unívocamente decodificables?</b>
| |
| | |
| <b>c. ¿Cuál es más eficiente (H/L)?</b>
| |
| | |
| <b>d. ¿Alguno presenta pérdida de información?</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>a. Un código es instantáneo o libre de prefijos si no codifica ningún símbolo como prefijo de otro.</b>
| |
| | |
| 1.No, B es prefijo de D.
| |
| | |
| 2.No, A es prefijo de B.
| |
| | |
| 3.Si, bit 1 sirve como limitador.
| |
| | |
| <b>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.</b>
| |
| | |
| 1.Si.
| |
| | |
| 2.Si.
| |
| | |
| 3.Si. Instantaneo --> Unívocamente decodificable.
| |
| | |
| <b>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</b>
| |
| | |
| 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.
| |
| | |
| <b>d. Un código C sobre una fuente S codifica sin pérdida de información sii H(S) <= L(C)</b>
| |
| | |
| 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===
| |
| | |
| <b>¿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.</b>
| |
| | |
| <b>a. 2 símbolos equiprobables</b>
| |
| | |
| <b>b. 4 símbolos equiprobables</b>
| |
| | |
| <b>c. 6 símbolos equiprobables</b>
| |
| | |
| <b>d. 8 símbolos equiprobables</b>
| |
| | |
| <b>e. 10 símbolos equiprobables</b>
| |
| | |
| <b>f. N símbolos equiprobables</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| 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.
| |
| | |
| <b>a.</b>
| |
| H(S) = L(C) = log2(2) = 1
| |
| | |
| <b>b.</b>
| |
| H(S) = L(C) = log2(4) = 2
| |
| | |
| <b>c.</b>
| |
| H(S) = log2(6)
| |
| L(C) = [log2(6)] = 3
| |
| | |
| <b>d.</b>
| |
| H(S) = L(C) = log2(8) = 3
| |
| | |
| <b>e.</b>
| |
| H(S) = log2(10)
| |
| L(C) = [log2(10)] = 4
| |
| | |
| <b>f.</b>
| |
| H(S) = log2(N)
| |
| L(C) = [log2(N)]
| |
| | |
| ===Ejercicio 05===
| |
| | |
| <b>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.</b>
| |
| | |
| <b>a. Calcular la entropía de la fuente si todas las imágenes fueran equiprobables.</b>
| |
| | |
| <b>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?</b>
| |
| | |
| <b>c. Calcular el ancho de banda mínimo requerido para soportar la transmisión de la señal resultante.</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>a.</b>log2(#S) (fuente equiprobables), Donde #S = 10^(640 x 480), entonces log2(10^(640 x 480)) = (640 x 480) * log2(10) = 1,02049631 × 10^6
| |
| | |
| <b>b.</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) = 1020497
| |
| | |
| <b>c.</b>
| |
| | |
| <b>Teorema de Shannon: C[bps] = B[Hz] * log2(1 + SNR[veces]) con SNR[veces] = 10SNR[dB]=10 y B el ancho de banda disponible.</b>
| |
| <b>Velocidad de transmisión sin pérdida de información: Vtx[bps] <= C[bps], con V max tx = C</b>
| |
| | |
| 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
| |
| | |
| ===Ejercicio 06===
| |
| | |
| <b>Calcule la Capacidad de Volumen (cantidad de bits que entran simultáneamente) en cada uno de los
| |
| siguientes medios físicos de transmisión, asumiendo que se los utiliza a su máxima Capacidad de Transmisión
| |
| (es decir, sin pérdida de información):</b>
| |
| | |
| <b>a. D = 100km, Vprop = 200000km/s, SNR = 100dB, B = 400Hz</b>
| |
| | |
| <b>b. D = 100km, Vprop = 200000km/s, SNR = 10dB, B = 400kHz</b>
| |
| | |
| <b>c. D = 100km, Vprop = 300000km/s, SNR = 10dB, B = 400kHz</b>
| |
| | |
| <b>d. D = 100m, Vprop = 300000km/s, SNR = 10dB, B = 400kHz</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>Capacidad de Volumen de un canal (también "Producto Delay por Velocidad de Transimisión" o "Producto Delay por Ancho de Banda"): Cvol[bits] = Delay * Vtx
| |
| </b>
| |
| | |
| <b>Delay: Delay[Seg] = Ttx + Tprop
| |
| </b>
| |
| | |
| <b>Tiempo de Transmisión de un bit: Ttx[Seg] = 1/Vtx
| |
| </b>
| |
| | |
| <b>Velocidad de transmisión sin pérdida de información: Vtx[bps] <= C[bps] -> Vtx max [bps] = C[bps]
| |
| </b>
| |
| | |
| <b>Capacidad de un canal (limitado en potencia, en acho de banda y con ruido): C[bps] = B[Hz] * log2(1 + SNR[Veces]) con SNR[veces] = 10^(SNR[dB]/10) y B el ancho de banda disponible.</b>
| |
| | |
| <b>Tiempo de Propagación de un bit: Tprop[Seg] = D/V con D la distancia del enlace y V la velocidad de propagación de la forma de onda en el medio físico.</b>
| |
| | |
| Cvol[bits] = ( 1/C[bps] + D/V ) * C[bps] = 1 + (D*C[bps])/Vprop
| |
|
| |
| <b>a.</b>
| |
| | |
| C[bps] = 400Hz * log2(1 + 10^(100dB/10) = 13288 bps
| |
| | |
| D = 100km
| |
| | |
| V = Vprop = 200000km/s
| |
| | |
| Cvol[bits] = 1 + (13288 bps * 100Km)/200000km/s = 7 bits
| |
| | |
| <b>b.</b>
| |
| | |
| C[bps] = 400KHz * log2(1 + 10^(10dB/10) = 1383 kbps = 1383000 bps
| |
| | |
| D = 100km
| |
| | |
| V = Vprop = 200000km/s
| |
| | |
| Cvol[bits] = 1 + (100km*1383000 bps)/200000km/s = 692 bits
| |
| | |
| <b>c.</b>
| |
| | |
| C[bps] = 400KHz * log2(1 + 10^(10dB/10) = 1383 kbps = 1383000 bps
| |
| | |
| D = 100km
| |
| | |
| V = Vprop = 300000km/s
| |
| | |
| Cvol[bits] = 1 + (100km*1383000 bps)/300000km/s = 462 bits
| |
| | |
| <b>d.</b>
| |
| | |
| D = 100m = 0.1km
| |
| | |
| V = Vprop = 300000km/s
| |
| | |
| Cvol[bits] = 1 + (0.1km*1383000 bps)/300000km/s = 1 bit
| |
| | |
| ===Ejercicio 07===
| |
| | |
| <b>Un satélite orbita la tierra tomando muestras meteorológicas. Se desea establecer un enlace entre dicho
| |
| satélite y una base central en la superficie terrestre. Dicho medio de transmisión soporta una velocidad
| |
| de transmisión de 100 Mbps. Si la información viaja a una velocidad de propagación de 300000 km/s, ¿es
| |
| posible que haya una distancia para la que el tiempo total de enviar 30Mb sea menor que 0.04 segundos?</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>Vtx: 100 Mbps</b>
| |
| | |
| <b>Vprop: 300000 km/s</b>
| |
| | |
| <b>El delay representa el tiempo total que tardamos en enviar información de
| |
| un punto a otro: Delay = Ttx + Tprop</b>
| |
| | |
| <b>Ttx: tiempo de transmisión: Ttx = |datos|/Vtx</b>
| |
| | |
| <b>Tprop: tiempo de propagación: Tprop = D/Vprop</b>
| |
| | |
| Ttx[Seg] = 30Mb/100Mbps = 0.3 Seg
| |
| | |
| Delay[Seg] = 0.3 + (D/300000 km/s) <= 0.04 Seg -> (D/300000 km/s) <= -0.26 Seg -> D <= -78000 Km -> Por lo tanto, No es posible enviar en 30 Mb en menos de 0.04 Segundos.
| |
| | |
| ===Ejercicio 08===
| |
| | |
| <b>Suponga que se instala un enlace punto a punto de 100 Mbps entre la Tierra y una base en la Luna. La
| |
| distancia entre la Luna y la Tierra es de aproximadamente 385000 km, y la velocidad de propagación de los
| |
| datos es la velocidad de la luz (300000 km/s).</b>
| |
| | |
| <b>a. ¿Cuál es el Delay de ida de un bit? ¿Y el RTT de un bit del enlace?</b>
| |
| | |
| <b>b. ¿Cuántos bits entran simultáneamente en el canal?</b>
| |
| | |
| <b>c. Una cámara en la base lunar toma fotografías de la Tierra y las guarda en formato digital en un disco.
| |
| Suponga que el Control de Misión en la Tierra desea descargar la última imagen que es de 25 Mb. ¿Cuál
| |
| es el tiempo mínimo que puede transcurrir entre el momento en que se inicia el pedido del dato y finaliza
| |
| la recepción? (Asumir que el mensaje de pedido es de 2Kb)</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>Vtx: 100 Mbps = 100000000 bps</b>
| |
| | |
| <b>D: 385000 km</b>
| |
| | |
| <b>Vprop: 300000 km/s</b>
| |
| | |
| <b>a.</b>
| |
| Delay[Seg] = 1/100000000 bps + 385000 km/300000 km/s = 1.28 Seg
| |
| | |
| RTT = 2 * Delay = 2 * 1.28 Seg = 2.56 Seg.
| |
| | |
| <b>b.</b>
| |
| | |
| Cvol[bits] = Delay * Vtx = 1.28 Seg * 100 Mbps = 128 Mbits
| |
| | |
| <b>c.</b>
| |
| | |
| Mensaje de pedido es de 2Kb = 0,002 Mb
| |
| | |
| Descarga de datos es de 25 Mb
| |
| | |
| Enviar el pedido: Delay = 0,002Mb/100Mbs + 385000 km/300000 km/s = 1.28 Seg
| |
| | |
| Descarga de datos: Delay = 25Mb/100Mbs + 385000 km/300000 km/s = 1.53 Seg
| |
| | |
| Tiempo mínimo que puede transcurrir entre el momento en que se inicia el pedido del dato y finaliza
| |
| la recepción: 1.28 Seg + 1.53 Seg = 2.81 Seg
| |
| | |
| ===Ejercicio 09===
| |
| | |
| <b>Un robot helicóptero transmite la señal de su cámara de video sobre un enlace inalámbrico que tiene una
| |
| relación señal a ruido del orden de los 30dB, con un ancho de banda útil de 50kHz. Modelando la cámara
| |
| como una fuente de información se obtiene que su entropía es de 5Kb. Asumiendo que se desea transmitir
| |
| sin pérdida de información:</b>
| |
| | |
| <b>a. ¿Hasta cuántas imágenes por segundo es posible enviar?</b>
| |
| | |
| <b>b. Calcule el delay promedio de una imagen enviada por el robot a 2km de distancia (Vprop = 300000 km/s).</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>a.</b>
| |
| | |
| Vtx max = C[Kbps] = 50KHz * log2(1+10^(30db/10)) = 498,36 Kbps
| |
| | |
| Ttx = |DATOS|/Vtx = 1 Seg --> |DATOS| = Vtx = 498,36 kbps
| |
| | |
| H(S) <= L(C) = 5Kb --> |DATOS|/L(C) = 498.36Kb/5Kb = 99 Imagenes
| |
| | |
| <b>b.</b>
| |
| | |
| Delay[Seg] = Ttx + Tprop = 5Kb/498,36Kbps + 2km/300000km/s = 0.01004 Seg
| |
| | |
| ===Ejercicio 10===
| |
| | |
| <b>En el esquema de la figura hay 3 servidores haciendo broadcasting de video a través de un satélite. Cada
| |
| servidor envía video sin comprimir con una resolución de 4Mb por imagen y 25 imágenes por segundo. Cada
| |
| servidor está conectado al switch que se conecta a un satélite mediante un enlace satelital. El enlace satelital
| |
| tiene una relación señal-ruido de 30dB.</b>
| |
| | |
| servidor1 \
| |
| | |
| servidor2 - Switch - Satelite
| |
| | |
| servidor3 /
| |
| | |
| <b>a. ¿Cuánto ancho de banda (Hz) será necesario en el enlace
| |
| satelital para satisfacer el broadcasting de todos los
| |
| servidores sin pérdida de información?</b>
| |
| | |
| <b>b. Si se modelaran las señales de los servidores como fuentes
| |
| de memoria nula y la entropía de cada fuente fuera como
| |
| se indica en la tabla, ¿qué señal se podría comprimir
| |
| más? Explique.</b>
| |
| | |
| <b>Servidor1 Entropía 100</b>
| |
| | |
| <b>Servidor2 Entropía 180</b>
| |
| | |
| <b>Servidor3 Entropía 150</b>
| |
| | |
| <b>Rta:</b>
| |
| | |
| <b>a.</b>
| |
| | |
| Vtx (Servidores) = 4Mb (resolucion) * 25 (Imagenes) * 3 (Servidores) = 300 Mbps
| |
| | |
| Sin perdida de información -> Vtx = C
| |
| | |
| Remplazo en Shannon -> B[MHz] = C[Mbps]/log2(1+SNR) = 300 Mbps/log2(1+10^3) = 30.12 MHz
| |
| | |
| <b>b.</b>
| |
| | |
| <b>La codificación es sin pérdida de informacion si se cumple:</b>
| |
| | |
| <b>H(S) <= L(C(S))</b>
| |
| | |
| ===Ejercicio 11===
| |
| | |
| <b>Un ciclista recorre un circuito montañoso con una cámara de video en su casco. Esta cámara transmite
| |
| la señal capturada por un enlace inalámbrico cuya relación señal-a-ruido es de 20 dB, siendo además su ancho
| |
| de banda útil 60 kHz. La cámara, por otro lado, puede modelarse como una fuente de información S en la
| |
| que cada símbolo es cada una de las imágenes transmitidas.</b>
| |
| | |
| <b>a. Encontrar una cota superior para la cantidad media de imágenes que la cámara podrá enviar por segundo
| |
| por el enlace, expresada en términos de H(S).</b>
| |
| | |
| <b>b. Supongamos un código C sobre S que asigna n bits al símbolo más probable de S y m bits al símbolo
| |
| menos probable, siendo n > m. ¿Puede ser C un ¢odigo óptimo? Asumir que S no es equiprobable.</b>
| |
| | |
| <b>Rta:</b>
| |
