Slides TD IV - clases (32)

Vista previa del material en texto

TD4 2022TD4 2022
Canales con ruido
52
TD4 2022TD4 2022 53
Problema fundamental de la comunicación
Datos s Datos s
Codificador
x = g(s) DecodificadorCanal
señal x señal y
▪ Reproducir en un punto (destino) el mensaje enviado en otro 
punto (fuente).
mensaje mensaje
TD4 2022TD4 2022 54
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 55
Ejemplo: transmisión con ruido
Alice
Bob
Envío un 2
Es un 1!!!
Alice envía a Bob 
el código del 2
▪ Enteros del 0 al 3: 
2
0
1
TD4 2022TD4 2022 56
Ejemplo: transmisión con ruido
▪ Del lado de Alice: ▪ Del lado de Bob:
Fu
en
te
Có
di
go
TD4 2022TD4 2022 57
Ejemplo: transmisión con ruido
▪ Del lado de Alice: ▪ Del lado de Bob:
Fu
en
te
Có
di
go
?
TD4 2022TD4 2022
Ejemplo: transmisión con ruido
58
▪ Pares de entrada/salida para 128 símbolos enviados por el 
canal:
Conteo de valores de entrada X y sus correspondientes 
salidas Y
TD4 2022TD4 2022
Distribuciones conjuntas
59
▪ Pares de entrada/salida para 128 símbolos enviados por el 
canal:
Conteo de valores de entrada X y sus correspondientes 
salidas Y
Distribución de probabilidad conjunta p(X,Y)
TD4 2022TD4 2022
Distribuciones conjuntas
60
▪ Pares de entrada/salida para 128 símbolos enviados por el 
canal:
Distribuciones marginales: p(X) y p(Y)
Conteo de valores de entrada X y sus correspondientes 
salidas Y
Distribución de probabilidad conjunta p(X,Y)
TD4 2022TD4 2022
Distribuciones conjuntas
61
Distribuciones marginales: p(X) y p(Y)
Distribución de probabilidad conjunta p(X,Y)
▪ Cálculo de distribuciones marginales:
TD4 2022TD4 2022
Distribuciones conjuntas
62
Distribuciones marginales: p(X) y p(Y)
Distribución de probabilidad conjunta p(X,Y)
▪ Cálculo de distribuciones marginales:
TD4 2022TD4 2022
Entropía de una distribución conjunta
63
▪ Generalización de la entropía para una distribución de 
probabilidad de una sola variable:
bits por 'par'
TD4 2022TD4 2022
Ejemplo: 2 dados
64
▪ Supongamos que tiramos dos dados.
▪ En cada tirada, el valor de cada dado no depende del 
resultado del otro.
TD4 2022TD4 2022
Ejemplo: 2 dados
65
▪ Supongamos que tiramos dos dados.
▪ En cada tirada, el valor de cada dado no depende del 
resultado del otro.
TD4 2022TD4 2022
Ejemplo: 2 dados
66
▪ Supongamos que tiramos dos dados.
▪ En cada tirada, el valor de cada dado no depende del 
resultado del otro.
▪ Entropía:
bits por 'par'
TD4 2022TD4 2022
Ejemplo: 2 dados
67
▪ Supongamos que tiramos dos dados.
▪ En cada tirada, el valor de cada dado no depende del 
resultado del otro.
▪ Entropía:
bits por 'par'
bits
bits
TD4 2022TD4 2022
Ejemplo: 2 dados
68
▪ Supongamos que tiramos dos dados.
▪ En cada tirada, el valor de cada dado no depende del 
resultado del otro.
▪ Entropía:
bits por 'par'
bits
bits
TD4 2022TD4 2022
Independencia estadística
69
▪ Si X e Y son independientes, conocer el valor de X no aporta 
ningún tipo de información sobre el valor de Y (y viceversa). 
▪ Implica que:
bits por 'par'
TD4 2022TD4 2022
Canales con ruido
70
▪ La distribución de salida depende de la entrada (no hay 
independencia).
▪ En un canal de comunicación con ruido, nos interesa conocer la 
proporción de entropía de la salida que refleja la información de 
entrada. 
▪ Idealmente queremos:
• Alta entropía en la entrada (comunicar la mayor cantidad de información posible)
• Alta entropía en la salida (comunicar la mayor cantidad de información posible)
• Baja entropía del ruido (bajo impacto del ruido )
TD4 2022TD4 2022
Entropía y conjuntos
71
Variables independientes
TD4 2022TD4 2022
Entropía y conjuntos
72
Variables con dependencia
TD4 2022TD4 2022
Información mutua
73
Variables con dependencia
▪ La cantidad de información que X e Y 
comparten: mide en cuánto el 
conocimiento de una variable reduce 
nuestra incertidumbre sobre la otra. 
TD4 2022TD4 2022
Información mutua
74
Variables con dependencia
▪ La cantidad de información que X e Y 
comparten: mide en cuánto el 
conocimiento de una variable reduce 
nuestra incertidumbre sobre la otra.
 
▪ Podemos calcularla a partir de la 
ecuación:
TD4 2022TD4 2022
Información mutua: ejemplo
75
▪ Volvamos al ejemplo de transmisión de enteros del 0 al 3:
Distribución de probabilidad conjunta p(X,Y)
TD4 2022TD4 2022
Información mutua: ejemplo
76
▪ Volvamos al ejemplo de transmisión de enteros del 0 al 3:
Distribución de probabilidad conjunta p(X,Y)
bits
bits
bits
TD4 2022TD4 2022
Información mutua: ejemplo
77
▪ Volvamos al ejemplo de transmisión de enteros del 0 al 3:
Distribución de probabilidad conjunta p(X,Y)
bits
bits
bits
▪ Información mutua:
bits
bits
TD4 2022TD4 2022
Información mutua: ejemplo
78
▪ Si consideramos que la entropía de salida es:
bits
▪ Entonces, solo el ~25% de ese valor es información acerca de 
la entrada:
Eficiencia del canal
TD4 2022TD4 2022
Información mutua: ejemplo
79
▪ Si consideramos que la entropía de salida es:
▪ Entonces, solo el ~25% de ese valor es información acerca de 
la entrada:
¡el resto es entropía del ruido en el canal!
bits
Eficiencia del canal
TD4 2022TD4 2022
Entropía condicional
80
▪ Si la información mutua es la información sobre la entrada X 
provista por la salida Y, el resto es entropía del ruido η:
TD4 2022TD4 2022
Entropía condicional
81
▪ Si la información mutua es la información sobre la entrada X 
provista por la salida Y, el resto es entropía del ruido η:
TD4 2022TD4 2022
Entropía del ruido en el canal
82
▪ Si la información mutua es la información sobre la entrada X 
provista por la salida Y, el resto es entropía del ruido η:
TD4 2022TD4 2022
Resumiendo
83
▪ La información mutua es la reducción promedio en la 
incerteza acerca del valor de X provista por Y (y viceversa).
▪ Podemos calcular la información mutua como:
TD4 2022TD4 2022
Resumiendo
84
▪ Alternativamente:
TD4 2022TD4 2022
Resumiendo
85
▪ Alternativamente:
▪ En un canal de comunicación con entrada X y salida Y=X+η, 
la entropía condicional H(Y|X) es la entropía del ruido en el 
canal H(η) que se agregó a X.
TD4 2022TD4 2022 86
▪ 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
Segundo teorema de Shannon (1948)
TD4 2022TD4 2022
Capacidad de un canal con ruido
87
▪ La capacidad para cualquier canal discreto con ruido se 
puede calcular como:
TD4 2022TD4 2022
Capacidad de un canal con ruido
88
▪ La capacidad para cualquier canal discreto con ruido se 
puede calcular como:
▪ Esto significa que la capacidad C se alcanza con la 
distribución p(X) que maximiza información mutua I(X,Y) 
entre la entrada y la salida.
TD4 2022TD4 2022
Segundo teorema de Shannon (1948)
89
▪ Dado un canal con capacidad C y una fuente con entropía H: 
• Si H < C , existe una forma de codificación de la fuente con 
una frecuencia de error arbitrariamente pequeña (a pesar 
del ruido!)
• Si H > C , es posible codificar la fuente de manera que el 
error (por el ruido) sea como mínimo H - C + ε (con ε 
arbitrariamente pequeño).
TD4 2022TD4 2022
Segundo teorema de Shannon (1948)
90
▪ Dado un canal con capacidad C y una fuente con entropía H: 
• Si H < C , existe una forma de codificación de la fuente con 
una frecuencia de error arbitrariamente pequeña (a pesar 
del ruido!)
• Si H > C , es posible codificar la fuente de manera que el 
error (por el ruido) sea como mínimo H - C + ε (con ε 
arbitrariamente pequeño).
▪ En esencia, podemos usar un canal de comunicación para enviar 
informaciónsin errores con una tasa arbitrariamente cercana a 
C, pero no podemos enviar a una tasa mayor sin perder 
información.