Slides TD IV - clases (28)

Vista previa del material en texto

TD4 2022TD4 2022 3
Problema fundamental de la comunicación
Datos s Datos s
Codificador
x = g(s) DecodificadorCanal
señal x señal y
Ruido
▪ Reproducir en un punto (destino) el mensaje enviado en otro 
punto (fuente).
mensaje mensaje
TD4 2022TD4 2022 4
Codificación del mensaje
▪ Antes de ser transmitido, el mensaje original s puede ser 
codificado en una nueva secuencia x de longitud n, que 
eventualmente puede tener símbolos diferentes. 
▪ En este proceso se puede eliminar la redundancia natural en 
los datos (compresión con o sin pérdida) o sumar 
redundancia para ganar robustez frente al ruido. 
Codificador
x = g(s)
TD4 2022TD4 2022
Ejemplo: Canal Binario Simétrico (BSC)
▪ Supongamos un canal que transmite correctamente cada bit con 
una probabilidad (1-f) e incorrectamente con probabilidad f.
0 0
1 1
5
TD4 2022TD4 2022
Ejemplo: codificación del mensaje (BSC)
▪ Volvamos al desafío de detectar y corregir errores en BSC (f=0.1).
▪ Esquema simple: redundancia por repetición R3
s = 0 0 1 0 1 1 0 
g(s) = 000 000 111 000 111 111 000 
n = 000 001 000 000 101 000 000 ruido en el canal BSC
y = 000 001 111 000 010 111 000 
 0 0 1 0 0 1 0 errores corregidoserrores sin corregir
mensaje original
mensaje codificado
6
TD4 2022TD4 2022
Decodificando Hamming
s = 1 0 0 0 mensaje original
y = 1 1 0 0 1 0 1 Mensaje recibido 1 00
0
1
01
flip!
 1 0 0 0 1 0 1 Mensaje corregido 
▪ Las violaciones a la paridad de los círculos siguen un patrón y 
se pueden tabular en una “matriz de paridad”: 
7
TD4 2022TD4 2022
Codificación: resumen
▪ Trade-off entre la probabilidad de error y 
la tasa de transmisión, “no pain, no 
gain”. 
▪ ¿Podemos obtener métodos de 
codificación con una performance 
dentro del área roja? 
▪ ¿Cuál es la máxima performance que 
puede lograrse con el mejor algoritmo?
8
Codificaciones más 
eficientes
TD4 2022TD4 2022
Mejor performance posible
▪ Shannon demostró que el límite entre los 
puntos alcanzables y no alcanzables se 
encuentra con el eje x en un valor 
distinto de cero = C (Capacidad). 
▪ Existen códigos que hacen posible la 
comunicación con una probabilidad de 
error arbitrariamente chica a velocidades 
distintas de cero. alcanzable no alcanzable
TD4 2022TD4 2022
Capacidad de un canal
▪ Cantidad máxima de bits que puede comunicar un canal, 
expresado en bits/s ó bits/símbolo
▪ En un canal sin ruido, la capacidad es numéricamente igual a 
la cantidad de bits que puede comunicar por segundo
▪ Un canal puede transmitir menos que su capacidad, pero 
nunca más
TD4 2022TD4 2022
Capacidad de un canal
▪ Si cada dígito binario lleva menos de un bit de información, el 
canal se usa a una tasa R menor a su capacidad C
▪ En un canal con ruido, la capacidad está acotada por el ruido 
▪ Para alcanzar tasas similares a la 
capacidad de un canal, tenemos que 
usar sabiamente cada bit 
TD4 2022TD4 2022 12
Experimento aleatorio: tirar una moneda
▪ Supongamos que modelamos el experimento de tirar una 
moneda cargada con una variable aleatoria. 
▪ En 100 tiradas, la moneda cae 90 veces con la cruz hacia 
arriba y solo 10 con la cara hacia arriba. 
TD4 2022TD4 2022 13
Experimento aleatorio: tirar una moneda
moneda “cargada”
▪ Supongamos que modelamos el experimento de tirar una 
moneda cargada con una variable aleatoria. 
▪ En 100 tiradas, la moneda cae 90 veces con la cruz hacia 
arriba y solo 10 con la cara hacia arriba. 
TD4 2022TD4 2022 14
Cuantificando la “sorpresa”
▪ Cuando tiramos la moneda, esperamos que salga cruz, es 
decir que “nos sorprende menos” que si sale cara.
TD4 2022TD4 2022 15
Cuantificando la “sorpresa”
▪ Cuando tiramos la moneda, esperamos que salga cruz, es 
decir que “nos sorprende menos” que si sale cara.
▪ Cuanto más improbable la salida de la variable aleatoria, 
más sorprendidos estamos al observar el evento.
TD4 2022TD4 2022 16
Cuantificando la “sorpresa”
▪ Cuando tiramos la moneda, esperamos que salga cruz, es 
decir que “nos sorprende menos” que si sale cara.
▪ Cuanto más improbable la salida de la variable aleatoria, 
más sorprendidos estamos al observar el evento.
¿Cómo podríamos cuantificar la cantidad de sorpresa?
TD4 2022TD4 2022 17
Cuantificando la “sorpresa”
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
TD4 2022TD4 2022 18
Cuantificando la “sorpresa”
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
sorpresa baja
sorpresa alta
TD4 2022TD4 2022 19
Información de Shannon
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
TD4 2022TD4 2022 20
Información de Shannon
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
TD4 2022TD4 2022 21
Información de Shannon
▪ Una forma de expresar la sorpresa es cuantificándola en 
base a la probabilidad de la salida de la variable aleatoria.
▪ Es más informativo saber que ocurrió un evento improbable, 
que conocer la ocurrencia de uno probable. 
TD4 2022TD4 2022 22
Información y sorpresa 
▪ Es más informativo saber que ocurrió un evento improbable, 
que conocer la ocurrencia de uno probable. 
TD4 2022TD4 2022 23
Información y sorpresa 
▪ Es más informativo saber que ocurrió un evento improbable, 
que conocer la ocurrencia de uno probable. 
TD4 2022TD4 2022 24
Información y sorpresa 
▪ Es más informativo saber que ocurrió un evento improbable, 
que conocer la ocurrencia de uno probable. 
TD4 2022TD4 2022 25
Información y sorpresa 
▪ Podemos cuantificar la sorpresa utilizando la noción de 
información de Shannon.
▪ Necesitamos conocer las probabilidades de los eventos. 
▪ Ne
TD4 2022TD4 2022 26
Información y sorpresa 
▪ Podemos cuantificar la sorpresa utilizando la noción de 
información de Shannon.
▪ Necesitamos conocer las probabilidades de los eventos. 
▪ Ne
Información de Shannon:
TD4 2022TD4 2022 27
Información y sorpresa 
Información de Shannon:
▪ Dado que estamos cuantificando la información, podemos 
medirla en bits (unidad de información).
▪ También se conoce a esta unidad como shannon (Sh).
TD4 2022TD4 2022 28
Sorpresa promedio de una variable
▪ No estamos interesados en un solo evento o valor de una 
variable aleatoria. 
▪ En general, nos va a interesar saber cuánta sorpresa hay en 
promedio para todo el conjunto de valores de una variable 
aleatoria. 
TD4 2022TD4 2022
Sorpresa promedio de una variable
▪ Moneda justa:
TD4 2022TD4 2022
Sorpresa promedio de una variable
▪ Moneda justa:
bit por tirada
TD4 2022TD4 2022 31
Sorpresa promedio de una variable
▪ Moneda justa:
▪ Moneda cargada:
bits por tirada
bit por tirada
TD4 2022TD4 2022 32
Entropía de una variable aleatoria
▪ La entropía es una medida de la incerteza: sabemos menos 
de la moneda justa que de la sesgada.
TD4 2022TD4 2022 33
Entropía de una variable aleatoria
▪ La entropía es una medida de la incerteza: sabemos menos 
de la moneda justa que de la sesgada.
▪ Una entropía de 0.564 bits quiere decir que podríamos 
representar la información de, por ejemplo, 1000 tiradas 
usando tan solo 564 dígitos binarios (en vez de 1000!).
TD4 2022TD4 2022 34
Entropía de una variable aleatoria
▪ Calculamos la entropía como:
bits
Distribución de probabilidades
de la variable aleatoria X
TD4 2022TD4 2022 35
¡Ejercicio! 
¿Cuántas preguntas con respuesta 
sí/no tengo que hacer para adivinar 
la posición del peón en un tablero 
de ajedrez? 
Pensar una estrategia que minimice 
la cantidad de preguntas. 
TD4 2022TD4 2022 36
¡Ejercicio! 
1. ¿Está en la mitad izquierda?
TD4 2022TD4 2022 37
¡Ejercicio! 
1. ¿Está en la mitad izquierda?
2. ¿Está en la mitad superior?
TD4 2022TD4 2022 38
¡Ejercicio! 
1. ¿Estáen la mitad izquierda?
2. ¿Está en la mitad superior?
3. En ese cuadrante ¿Está en la 
mitad izquierda?
TD4 2022TD4 2022 39
¡Ejercicio! 
1. ¿Está en la mitad izquierda?
2. ¿Está en la mitad superior?
3. En ese cuadrante ¿Está en la 
mitad izquierda?
4. En ese cuadrante ¿Está en la 
mitad superior?
TD4 2022TD4 2022 40
¡Ejercicio! 
1. ¿Está en la mitad izquierda?
2. ¿Está en la mitad superior?
3. En ese cuadrante ¿Está en la 
mitad izquierda?
4. En ese cuadrante ¿Está en la 
mitad superior?
5. En ese cuadrante ¿Está en la 
mitad izquierda?
TD4 2022TD4 2022 41
¡Ejercicio! 
1. ¿Está en la mitad izquierda?
2. ¿Está en la mitad superior?
3. En ese cuadrante ¿Está en la 
mitad izquierda?
4. En ese cuadrante ¿Está en la 
mitad superior?
5. En ese cuadrante ¿Está en la 
mitad izquierda?
6. En ese cuadrante ¿Está en la 
mitad superior?
TD4 2022TD4 2022 42
¡Ejercicio! 
▪ Podemos modelar este problema 
mediante una variable aleatoria:
TD4 2022TD4 2022 43
¡Ejercicio! 
▪ Podemos modelar este problema 
mediante una variable aleatoria:
TD4 2022TD4 2022 44
¡Ejercicio! 
▪ Podemos modelar este problema 
mediante una variable aleatoria:
TD4 2022TD4 2022 45
Interpretando la Entropía
▪ Podemos pensar a la entropía como la cantidad mínima de 
preguntas binarias (si trabajamos con log en base 2) para 
identificar el valor de una variable aleatoria discreta. 
TD4 2022TD4 2022 46
Interpretando la Entropía
▪ Podemos pensar a la entropía como la cantidad mínima de 
preguntas binarias (si trabajamos con log en base 2) para 
identificar el valor de una variable aleatoria discreta. 
Espacio de posibilidades
Observación
= 1 bit de información
TD4 2022TD4 2022 47
Interpretando la Entropía
▪ Podemos pensar a la entropía como la cantidad mínima de 
preguntas binarias (si trabajamos con log en base 2) para 
identificar el valor de una variable aleatoria discreta. 
Espacio de posibilidades
Observación
+ 1 bit de información
= 1 bit de información
TD4 2022TD4 2022 48
Interpretando la Entropía
▪ Podemos pensar a la entropía como la cantidad mínima de 
preguntas binarias (si trabajamos con log en base 2) para 
identificar el valor de una variable aleatoria discreta. 
Espacio de posibilidades
Observación
+ 1 bit de información
= 1 bit de información
+ 1 bit de información
…
TD4 2022TD4 2022 49
Interpretando la Entropía
▪ ¿Cuánta información contiene la posición del peón en un 
tablero de ajedrez?
TD4 2022TD4 2022 50
Interpretando la Entropía
▪ ¿Cuánta información contiene la posición del peón en un 
tablero de ajedrez? → 6 bits
TD4 2022TD4 2022 51
Interpretando la Entropía
▪ ¿Cuánta información contiene la posición del peón en un 
tablero de ajedrez? → 6 bits
▪ El valor de entropía depende solo de la distribución de 
probabilidades, no de los símbolos de la variable aleatoria. 
▪ Si duplicamos la cantidad de casillas en el tablero de 
ajedrez, o en las caras de un dado, la entropía se incrementa 
en 1 bit. 
TD4 2022TD4 2022 52
Bits, Shannons y Bans
▪ La unidad de medición de información depende de la base del 
logaritmo que estemos utilizando. Es similar a lo que sucede 
cuando medimos agua en una receta y usamos litros o tazas. 
TD4 2022TD4 2022 53
Bits, Shannons y Bans
▪ La unidad de medición de información depende de la base del 
logaritmo que estemos utilizando. Es similar a lo que sucede 
cuando medimos agua en una receta y usamos litros o tazas. 
▪ Si medimos información usando logaritmo natural (base e = 
2.72), entonces las unidades se llaman nats en vez de bits 
(base 2). 
▪ Si usamos logaritmos en base 10, las unidades se llaman bans.
▪ Si usamos logaritmos en base 2, las unidades son los bits o 
Shannons (Sh)
TD4 2022TD4 2022 54
Primer teorema de Shannon (1948)
▪ Si deseamos comunicar muestras extraídas de alguna 
distribución, en promedio necesitaremos al menos tantos 
símbolos como la entropía de esa distribución para comunicar 
sin ambigüedades esas muestras. 
TD4 2022TD4 2022 55
Primer teorema de Shannon (1948)
▪ Si deseamos comunicar muestras extraídas de alguna 
distribución, en promedio necesitaremos al menos tantos 
símbolos como la entropía de esa distribución para comunicar 
sin ambigüedades esas muestras. 
▪ La entropía proporciona un límite inferior sobre cuánto 
podemos comprimir nuestra descripción de las muestras de la 
distribución antes de que inevitablemente perdamos 
información.
TD4 2022TD4 2022 56
▪ Dicho de otro modo:
“Es posible codificar una fuente de información con entropía H 
(bits por símbolo) y un canal de capacidad C (bits por segundo) 
de manera que se pueda transmitir a una tasa promedio de C/H-ε 
símbolos por segundo.” 
Primer teorema de Shannon (1948)
TD4 2022TD4 2022 57
Eficiencia en la codificación de datos
▪ Dado de 8 caras: 
Alice
Bob
Saqué un 2
Sacó un 2!!!
Alice envía a Bob 
el código del 2
TD4 2022TD4 2022 58
Fuente: dado de 8 caras
▪ Capacidad del canal
bits/s
TD4 2022TD4 2022 59
Fuente: dado de 8 caras
▪ Capacidad del canal
bits/s
bits/símbolo
▪ Entropía
TD4 2022TD4 2022 60
Fuente: dado de 8 caras
▪ Capacidad del canal
bits/s
bits/símbolo
▪ Entropía
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
bits/s
bits/símbolo
símbolo/s
TD4 2022TD4 2022 61
Fuente: dado de 8 caras
bits/s
bits/símbolo
símbolos/s
▪ Capacidad del canal
bits/s
bits/símbolo
▪ Entropía
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
TD4 2022TD4 2022 62
Fuente: dado de 8 caras
bits/s
bits/símbolo
símbolos/s
▪ Capacidad del canal
bits/s
bits/símbolo
▪ Entropía
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
Sabemos que cada símbolo 
equivale a 3 bits -> código 
eficiente!!!!
TD4 2022TD4 2022
▪ Calculamos la tasa de transmisión R como:
▪ Eficiencia de un código: ratio entre la cantidad promedio de 
dígitos binarios por palabra en el código L(X) y la entropía H(S) 
promedio de los símbolos del alfabeto:
63
Eficiencia en la codificación de datos
Capacidad del canal
Entropía
bits/símbolo
3 dígitos binarios/símbolo
bits/dígito binario
TD4 2022TD4 2022 64
Fuente: dado de 6 caras
▪ Dado de 6 caras: 
Alice
Bob
Saqué un 4
Sacó un 4!!!
Alice envía a Bob 
el código del 4
TD4 2022TD4 2022 65
Fuente: dado de 6 caras
▪ Capacidad del canal
bits/s
TD4 2022TD4 2022 66
Fuente: dado de 6 caras
▪ Capacidad del canal
▪ Entropía
bits/s
bits/símbolo
TD4 2022TD4 2022 67
Fuente: dado de 6 caras
▪ Capacidad del canal
▪ Entropía
bits/s
bits/símbolo
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
TD4 2022TD4 2022 68
Fuente: dado de 6 caras
▪ Capacidad del canal
▪ Entropía
bits/s
bits/símbolo
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
bits/s
bits/símbolo
símbolos/s
TD4 2022TD4 2022 69
Fuente: dado de 6 caras
▪ Capacidad del canal
▪ Entropía
bits/s
bits/símbolo bits/dígito binario
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
bits/s
bits/símbolo
símbolos/s
▪ Eficiencia:
TD4 2022TD4 2022
Fuente: dado de 6 caras
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
símbolos/s
bits/s
bits/símbolo
TD4 2022TD4 2022
Fuente: dado de 6 caras
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
¿Qué salió mal?
símbolos/s
bits/s
bits/símbolo
TD4 2022TD4 2022 72
Eficiencia en la codificación de datos
▪ No siempre que transmitimos un dígito binario estamos 
transmitiendo un bit de información.
Alice
Bob
Saqué un 4
Sacó un 4!!!
Alice envía a Bob 
el código del 4
TD4 2022TD4 2022 73
Eficiencia en la codificación de datos
▪ No siempre que transmitimos un dígito binario estamos 
transmitiendo un bit de información.
Alice
Bob
Saqué un 4
Sacó un 4!!!
Alice envía a Bobel código del 4
▪ Solo se alcanza la máxima 
capacidad de transmisión 
cuando cada dígito binario 
transporta la mayor cantidad 
de información posible.
TD4 2022TD4 2022
Bob
Saqué un 4, 
un 3 y un 1 Sacó un 4, 
un 3 y un 1
Alice envía a Bob 
el código del 4,3,1
74
Recodificación de la fuente
▪ Idea! Codificar más de un símbolo a la vez. Por ejemplo, 3 
símbolos seguidos:
Alice
TD4 2022TD4 2022 75
Recodificación de la fuente
bits/dígito binario
▪ Eficiencia:
TD4 2022TD4 2022 76
Recodificación de la fuente
bits/dígito binario
▪ Eficiencia:
▪ Según el Primer Teorema de 
Shannon, la tasa máxima de 
transmisión se puede calcular 
como:
TD4 2022TD4 2022
Recodificación de la fuente
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
símbolos/s
bits/s
bits/símbolo
símbolos/s
TD4 2022TD4 2022
Si los valores de la variable no 
representan un número entero de bits, se 
puede mejorar la codificación 
combinando varios símbolos en el código
Recodificación de la fuente
▪ Tasa máxima (teórica):
bits/s
bits/símbolo
símbolos/s
▪ Tasa efectiva:
símbolos/s
bits/s
bits/símbolo
símbolos/s
TD4 2022TD4 2022 79
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 80
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 81
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
TD4 2022TD4 2022 82
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
▪ Entropía:
bits/símbolo
TD4 2022TD4 2022 83
Compresión de datos
▪ Consideremos el caso en el que la variable no tiene una 
distribución uniforme. Por ejemplo, transmitir la suma de las 
caras de dos dados:
▪ Entropía:
bits/símbolo
▪ Eficiencia:
bits/dígito binario
TD4 2022TD4 2022 84
Código de Huffman (1952)
▪ Método de compresión sin pérdida 
▪ Idea! Asignar códigos más cortos a 
los símbolos más frecuentes (y 
viceversa). 
▪ Requiere conocer las probabilidades 
de ocurrencia. 
▪ Asume eventos independientes: los 
resultados de cada experimento 
aleatorio no están conectados entre 
sí de ninguna manera.