%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
8. Codificación de canal#
Hasta ahora hemos asumido que el canal está libre de ruido
El objetivo original de Shannon era
“Comunicación robusta a través de un canal ruidoso”
El ruido disminuye la capacidad del canal
Ejemplo: Un cisne navegando por un canal ruidoso
Imagemos que queremos transmitir una imagen binaria \(X\) por un canal con ruido.
Asumamos que el canal le cambia el valor a un 10% de los píxeles de forma aleatoria
Llamemos \(Y\) a la imagen que sale del canal.
Ver también
Este canal de comunicación se conoce como canal binario simétrico
fig, ax = plt.subplots(1, 2, figsize=(8, 3), tight_layout=True)
plt.rcParams['image.cmap'] = 'gray'
th_binary, p_noise = 0.5, 0.1
img_swan_gray = plt.imread('data/gray-swan.png')[:, :, 0]
img_swan = (img_swan_gray > th_binary).astype('uint8')
Npix = len(img_swan.ravel())
p = np.random.rand(img_swan.shape[0], img_swan.shape[1])
img_noisy_swan = img_swan.copy()
mask = p <= p_noise
img_noisy_swan[mask] = 1-img_noisy_swan[mask]
ax[0].imshow(img_swan)
ax[0].axis('off')
ax[0].set_title('X')
ax[1].imshow(img_noisy_swan)
ax[1].axis('off')
ax[1].set_title('Y');
Importante
Para cuantificar la información perdida por este error del canal necesitamos definir otro concepto de teoría de la información: La información mutua
8.1. Información Mutua#
La información mutua entre dos variables aleatorias \(X\) e \(Y\) se puede definir de varias maneras
que podemos resumir graficamente como:
donde
- Entropía conjunta, \(H(X,Y)\)
Cantidad de información promedio en bits de \(X\) e \(Y\)
- Entropía de \(X\) condicionada a \(Y\), \(H(X|Y)\)
Cantidad de información promedio en bits de \(X\) considerando que conocemos \(Y\) o también la “Incerteza de \(X\) dado que observamos \(Y\)”
- Información mutua
La información promedio en bits que ganamos sobre \(Y\) dado que observamos \(X\) (y viceverza). O también la incerteza promedio de \(Y\) que eliminamos al conocer \(X\) (y viceverza
Propiedades
Siempre se cumple que \(H(X)+H(Y) \geq H(X,Y)\) por lo tanto \(\text{MI}(X,Y) \geq 0\)
Además si \(X\) e \(Y\) son independientes entonces \(H(X|Y)=H(X)\) y \(H(X,Y) = H(X) + H(Y)\), por lo tanto \(\text{MI}(X,Y) = 0\)
Importante
La información mutua mide la información compartida por \(X\) e \(Y\), es decir que tan dependientes son entre sí
Ejemplo
Respondamos ahora para el ejemplo de los cisnes
¿Cuál es la entropía de cada imagen?
def entropy_binary_image(img):
p = np.count_nonzero(img.ravel())/len(img.ravel())
return -p*np.log2(p) - (1-p)*np.log2(1-p)
HX = entropy_binary_image(img_swan)
print(f"Entropía imagen limpia H(X): {HX:0.4f} [bits/pixel]")
Entropía imagen limpia H(X): 0.5767 [bits/pixel]
HY = entropy_binary_image(img_noisy_swan)
print(f"Entropía imagen sucia H(Y): {HY:0.4f} [bits/pixel]")
Entropía imagen sucia H(Y): 0.7406 [bits/pixel]
¿Cuál es la entropía conjunta?
Npix = len(img_swan.ravel())
p00 = np.count_nonzero((img_swan == 0) & (img_noisy_swan == 0))/Npix
p01 = np.count_nonzero((img_swan == 0) & (img_noisy_swan == 1))/Npix
p10 = np.count_nonzero((img_swan == 1) & (img_noisy_swan == 0))/Npix
p11 = np.count_nonzero((img_swan == 1) & (img_noisy_swan == 1))/Npix
print(np.array([p00, p01, p10, p11]))
HXY = -(p00*np.log2(p00) + p01*np.log2(p01) + p10*np.log2(p10) + p11*np.log2(p11))
print(f"Entropía conjunta H(X,Y): {HXY:0.6f} [bits/pixel]")
[0.12339301 0.01373794 0.0861537 0.77671535]
Entropía conjunta H(X,Y): 1.045327 [bits/pixel]
¿Cuáles son las entropía condicionales?
print(f"H(X|Y): {HXY-HY:0.6f} [bits/pixel]")
print(f"H(Y|X): {HXY-HX:0.6f} [bits/pixel]")
H(X|Y): 0.304712 [bits/pixel]
H(Y|X): 0.468652 [bits/pixel]
¿Cuál es la información mutua entre X e Y?
MIXY = HX + HY - HXY
print(f"Información mutua IM(X,Y): {MIXY:0.6f} [bits/pixel]")
Información mutua IM(X,Y): 0.271964 [bits/pixel]
¿Cuál es la entropía del ruido?
H_noise = -p_noise*np.log2(p_noise) - (1-p_noise)*np.log2(1-p_noise)
print(f"Entropía del ruido H(N): {H_noise:0.6f} [bits/pixel]")
Entropía del ruido H(N): 0.468996 [bits/pixel]
Consideremos que
Entonces
Nota
En un canal ruidoso la entropía condicional de la salida dada la entrada es equivalente a la entropía del ruido añadido a la entrada
Eficiencia
La eficiencia de la transmisión está dada por la proporción de entropía de \(Y\) que es compartida por \(X\)
Para este caso tenemos
MIXY/HY
0.3672128767865397
Es decir que un 37% de la entropía de la salida depende de la entrada
Reflexione: ¿Qué ocurre con la información mutua y con la eficiencia de transmisión cuando el canal se vuelve más o menos ruidoso?
8.2. Corrección de errores debidos al ruido#
Queremos ser capaces de recuperar X a partir de Y
Cuando el canal tiene ruido necesitamos robustecer el código de X
Esto se logra agregando redundancia a nuestro código, por ejemplo
Enviar el mensaje varias veces: repetition code
Agregar al código uno o más bits de paridad
Ejemplo 1: repetition code
Si queremos enviar 0110011 lo repetimos una cierta cantidad de veces
\(X\) = 000 111 111 000 000 111 111
\(N\) = 001 000 000 000 000 110 000
\(Y\) = 001 111 111 000 001 001 111
Si aplicamos decodificación por mayoría: 0 1 1 0 0 0 1
Reducimos la probabilidad de error por un factor de 3
Reducimos la tasa de transmisión en un factor de 3
La tasa de transmisión es \(R = k/n = 1/3\) donde \(k\) son los bits de información y \(n\) los bits transmitidos
Ejemplo 2: paridad
Sea una tira binaria de 16 bits \(s=[0,1,0,1,0,0,0,0,1,1,1,0, 0,1,1,0]\) Se ordena como una matriz de 4x4
Si el número de 1’s de una fila o columna es par se agrega un 0, de lo contrario se agrega un 1
Finalmente se crea una nueva tira de largo 24
\(s_p=[0,1,0,1,\textbf{0}, 0,0,0,0,\textbf{0}, 1,1,1,0, \textbf{1}, 0,1,1,0, \textbf{0}, \textbf{1}, \textbf{1}, \textbf{0}, \textbf{1}]\)
Al recibir este código se comprueba que las paridades estén bien
Si no lo están podriamos pedir nuevamente la tira binaria
Aumentamos el mensaje de 16 a 24 [bits], la tasa es \(R=16/24=0.666\)
Ejercicio propuesto:
Si tengo un string de NxN de largo y quiero proteger con bits de paridad ¿Cúantos bits agrego?
8.3. Teorema de codificación de canal de Shannon (Channel coding theorem)#
Se define la capacidad de un canal con entrada \(X\) y salida \(Y\) como
La distribución \(P^*(X)\) que maximiza la capacidad del canal es la distribución de entrada óptima para ese canal. Si el canal no tuviera ruido entonces \(Y=X\) y la capacidad está dada por la entropía de \(X\). El ruido disminuye la capacidad de un canal
Al respecto Shannon enunció el siguiente teorema
Theorem 8.1 (Teorema de codificación de canal)
Sea un canal con capacidad \(C\) y una fuente \(X\) que transmite a una tasa de \(R\)
Si \(R \leq C\) entonces existe un largo de codificación para \(X\) que puede transmitirse con error arbitrariamente pequeño
Para una probabilidad de error de bit aceptable \(p_e\), se puede alcanzar una tasa de transmisión
Para un cierto \(p_e\) no es posible alcanzar una tasa mayor a \(R(p_e)\)
Ejemplo: Canal binario simétrico
¿Cuál es la distribución de entrada que maximiza la información mutua del canal?
Respondamos en primer lugar usando Python
p_flip, tol = 0.1, 1e-2
np.random.seed(0)
seed_image = np.random.rand(img_swan_gray.shape[0], img_swan_gray.shape[1])
flip_mask = np.random.rand(img_swan_gray.shape[0], img_swan_gray.shape[1]) <= p_flip
binarization_threshold = np.linspace(0.01, 0.999, num=100)
MIXY = []
for th in binarization_threshold:
# Aplicamos el umbral de binarización
img_X = (img_swan_gray > th).astype('uint8')
img_Y = img_X.copy()
# Simulamos la perturbación del canal
img_Y[flip_mask] = 1 - img_Y[flip_mask]
# Calculamos las entropías y la IM
p00 = np.count_nonzero((img_X == 0) & (img_Y == 0))/Npix
p01 = np.count_nonzero((img_X == 0) & (img_Y == 1))/Npix
p10 = np.count_nonzero((img_X == 1) & (img_Y == 0))/Npix
p11 = np.count_nonzero((img_X == 1) & (img_Y == 1))/Npix
HX = -(p00 + p01)*np.log2(p00 + p01+tol) -(p10 + p11)*np.log2(p10 + p11+tol)
HY = -(p00 + p10)*np.log2(p00 + p10+tol) -(p01 + p11)*np.log2(p01 + p11+tol)
HXY= -(p00*np.log2(p00+tol) + p01*np.log2(p01+tol) + p10*np.log2(p10+tol) + p11*np.log2(p11+tol))
MIXY.append(HX + HY - HXY)
fig, ax = plt.subplots(figsize=(4, 3), tight_layout=True)
best_th = binarization_threshold[np.argmax(MIXY)]
ax.plot(binarization_threshold, MIXY);
ax.axhline(np.amax(MIXY), c='k', ls='--')
ax.axvline(binarization_threshold[np.argmax(MIXY)], c='k', ls='--')
ax.set_ylabel('Información mutua')
ax.set_xlabel('Umbral de binarización');
f"El mejor umbral es {binarization_threshold[np.argmax(MIXY)]:0.4f}"
'El mejor umbral es 0.6793'
f"La IM alcanzada es {np.amax(MIXY):0.4f}"
'La IM alcanzada es 0.5312'
La imagen resultante de aplicar el mejor umbral de binarización y la distribución de sus píxeles se muestra a continuación
best_binary_image = (img_swan_gray > binarization_threshold[np.argmax(MIXY)]).astype('uint8')
fig, ax = plt.subplots(1, 2, figsize=(8, 3), tight_layout=True)
ax[0].imshow(best_binary_image);
ax[0].axis('off');
ax[1].hist(best_binary_image.ravel(), align='mid', range=[-0.5, 1.5],
bins=2, density=True, histtype='bar', ec='black');
ax[1].set_xticks([0, 1])
ax[1].set_xlabel('Valor pixel binarizado');
Nota
Mientras más uniforme es una distribución mayor es su entropía
Veamos ahora si podemos llegar a la misma solución de forma teórica
Digamos que la imagen de entrada binaria se obtiene aplicando un umbral \(p\), es decir que si el pixel original en escala de grises es mayor que \(p\) entonces el resultado \(1\) de lo contrario es \(0\).
Con esto podemos escribir las probabilidades a priori de cada pixel como
\(P(X=0)=p\)
\(P(X=1)=(1-p)\)
Dijimos que el canal cambia un 10% de los pixeles de la entrada. Entonces las verosimilitudes son \(P(Y=1|X=1) = 0.9\), \(P(Y=1|X=0) = 0.1\), \(P(Y=0|X=1) = 0.1\), \(P(Y=0|X=0) = 0.9\)
Por ende las probabilidades marginales de la salida son:
\(P(Y=1) = \sum_x P(Y=1|X=x)P(X=x) = 0.9(1-p) + 0.1p = 0.9 - 0.8p \)
\(P(Y=0) = \sum_x P(Y=0|X=x)P(X=x) = 0.1(1-p) + 0.9p = 0.1 + 0.8p= 1 - P(Y=1) \)
y su entropía es
Por otro lado, la entropía condicional es
que no depende de \(p\).
Podemos calcular el máximo de la información mutua usando
de donde llegamos a que
Notemos que no importa que porcentaje de corrupción tenga el canal.
Finalmente la capacidad del canal es
Nota
Si usamos \(P^*\) podemos transmitir sin perdidas a una taza \(R=k/n \leq 0.531\), es decir que por \(k\) bits de información tenemos que transmitir al menos \(2k\) bits
El siguiente teorema relaciona la capacidad de un canal con la razón señal a ruido y el ancho de banda del canal:
Theorem 8.2 (Teorema de Shannon-Hartley)
Sea un canal con ancho de banda B [Hz] (rango de frecuencias que un canal puede transmitir) y potencia de señal S [W] y potencia del ruido N [W] (aditivo blanco gaussiano), entonces su capacidad es
Si la velocidad de transmisión de un canal es R [bits/s] y R < C entonces la probabilidad de errores de comunicación tiende a cero.
Las limitaciones de un sistema de comunicación son Ancho de banda y el ruido Ruido