6.6: Canal ruidoso

Si el canal introduce ruido entonces la salida no es una función única de la entrada. Modelaremos este caso diciendo que por cada entrada posible (que son estados mutuamente excluyentes indexados por\(i\)) puede haber más de un posible resultado de salida. Lo que realmente sucede es una cuestión de azar, y modelaremos el canal por el conjunto de probabilidades de que cada uno de los eventos de salida\(B_j\) ocurra cuando ocurra cada uno de los posibles eventos\(A_i\) de entrada. Estas probabilidades de transición\(c_{ji}\) son, por supuesto, probabilidades, pero son propiedades del canal y no dependen de la distribución\(p(A_i)\) de probabilidad de la entrada. Como todas las probabilidades, tienen valores entre 0 y 1

\(0 \leq c_{ji} \leq 1 \tag{6.15}\)

y puede pensarse que forma una matriz con tantas columnas como eventos de entrada haya, y tantas filas como eventos de salida. Debido a que cada evento de entrada debe conducir a exactamente un evento de salida,

\(1 = \displaystyle \sum_{j} c_{ji} \tag{6.16}\)

para cada uno\(i\). (Es decir, la suma de\(c_{ji}\) en cada columna\(i\) es 1.) Si el canal es sin ruido, por cada valor de\(i\) exactamente uno de los diversos\(c_{ji}\) es igual a 1 y todos los demás son 0.

Cuando el canal es conducido por una fuente con probabilidades\(p(A_i)\), las probabilidades condicionales de los eventos de salida, condicionadas a los eventos de entrada, son

\(p(B_j \; | \; A_i) = c_{ji} \tag{6.17}\)

La probabilidad incondicional de cada salida\(p(B_j)\) es

\(p(B_j) = \displaystyle \sum_{i} c_{ji} p(A_i) \tag{6.18}\)

Las probabilidades condicionales hacia atrás\ (p (a_I\; |\; b_j) se pueden encontrar usando el Teorema de Bayes:

\[\begin{align*} p(A_i, \ B_j) \ &= \ p(B_j)p(A_i \; | \; B_j) \\ &= \ p(A_i)p(B_j \; | \; A_i) \\ &= \ p(A_i)c_{ji} \tag{6.19} \end{align*} \]

El canal ruidoso más simple es el canal binario simétrico, para el cual hay una probabilidad (ojalá pequeña)\(\epsilon\) de un error, entonces

Este canal binario se llama simétrico porque la probabilidad de un error para ambas entradas es la misma. Si\(\epsilon\) = 0 entonces este canal es silenciosa (también es silenciosa si\(\epsilon\) = 1, en cuyo caso se comporta como un inversor). La Figura 6.3 puede ser más útil para el canal ruidoso si se muestran las posibles transiciones de entrada a salida, como en la Figura 6.5.

Si\(B_j\) se observa que la salida está en uno de sus estados (mutuamente excluyentes), ¿se puede determinar la entrada\(A_i\) que la causó? En ausencia de ruido, sí; no hay incertidumbre sobre la entrada una vez que se conoce la salida. Sin embargo, con el ruido hay cierta incertidumbre residual. Calcularemos esta incertidumbre en términos de las probabilidades de transición\(c_{ji}\) y definiremos la información que hemos aprendido sobre la entrada como resultado de conocer la salida como la información mutua. A partir de eso definiremos la capacidad del canal\(C\).

Figura 6.5: Canal binario simétrico

Antes de conocer la salida, ¿cuál es nuestra incertidumbre\(U_{\text{before}}\) sobre la identidad del evento input? Esta es la entropía de la entrada:

\(U_{\text{before}} = \displaystyle \sum_{i} p(A_i)\log_2\Big(\dfrac{1}{p(A_i)}\Big) \tag{6.21}\)

Después de que se\(B_j\) haya observado algún evento de salida particular, ¿cuál es la incertidumbre residual\(U_{\text{after}}(B_j)\) sobre el evento de entrada? Se aplica una fórmula similar, con\(p(A_i)\) reemplazado por la probabilidad condicional hacia atrás\(p(A_i \;|\; B_j )\):

\(U_{\text{after}}(B_j) = \displaystyle \sum_{i} p(A_i \;|\; B_j)\log_2\Big(\dfrac{1}{p(A_i \;|\; B_j)}\Big) \tag{6.22}\)

La cantidad que aprendimos en el caso de este evento de salida en particular es la diferencia entre\(U_{\text{before}}\) y\(U_{\text{after}}(B_j )\). La información mutua\(M\) se define como el promedio, sobre todos los productos, de la cantidad así aprendida,

No es difícil demostrar que\(M\) ≥ 0, es decir, que nuestro conocimiento sobre la entrada no se hace, en promedio, más incierto al aprender el evento output. Para demostrarlo, se utiliza la desigualdad Gibbs, para cada uno\(j\):

\[\begin{align*} U_{\text{after}}(B_j) \ &= \ \displaystyle \sum_{i} p(A_i \;|\; B_j)\log_2\Big(\dfrac{1}{p(A_i \;|\; B_j)}\Big) \\ &\leq \ \displaystyle \sum_{i} p(A_i \;|\; B_j)\log_2\Big(\dfrac{1}{p(A_i)}\Big) \tag{6.24} \end{align*} \]

Este uso de la desigualdad Gibbs es válido porque, para cada uno\(j\),\(p(A_i \;|\; B_j )\) es una distribución de probabilidad sobre\(i\), y\(p(A_i)\) es otra distribución de probabilidad sobre\(i\), diferente a la que hace el promedio. Esta desigualdad se mantiene para cada valor de\(j\) y por lo tanto para el promedio sobre todos\(j\):

\ [\ begin {align*}
\ sum_ {j} p (B_ {j}) U_ {\ text {después}} (B_ {j})\ &\ leq\\ suma_ {j} p (B_ {j})\ sum_ {i} p (A_ {i}\; |\; B_ {j})\ log _ {2}\ izquierda (\ frac {1} {p\ izquierda (A_ {i}\ derecha)}\ derecha)\\
&=\\ sum_ {j i} p (B_ {j}) p (A_ {i}\; |\; B_ {j})\ log _ {2}\ Grande (\ frac {1} {p (A_ {i})}\ Grande)\\
&=\\ suma_ {i j} p (B_ {j}\; |\; A_ {i}) p (A_ {i})\ log _ {2}\ izquierda (\ frac {1} {p\ izquierda (A_ {i}\ derecha)}\ derecha)\\
&=\ sum_ {i} p\ izquierda (A_ {i}\ derecha)\ log {2}\ izquierda (\ frac {1} {p\ izquierda (A_ {i}\ derecha)}\ derecha)\\
&=\ U_ {\ texto {antes}}\ tag {6.25}
\ end {align*}\ nonumber\]

Ahora estamos en condiciones de encontrar\(M\) en términos de la distribución de probabilidad de entrada y las propiedades del canal. La sustitución en la Ecuación 6.23 y la simplificación conducen a

\[M=\sum_{j}\left(\sum_{i} p\left(A_{i}\right) c_{j i}\right) \log _{2}\left(\frac{1}{\sum_{i} p\left(A_{i}\right) c_{j i}}\right)-\sum_{i j} p\left(A_{i}\right) c_{j i} \log _{2}\left(\frac{1}{c_{j i}}\right) \tag{6.26 } \]

Obsérvese que la Ecuación 6.26 se derivó para el caso donde la entrada “causa” la salida. Al menos, así fue como fue la descripción. Sin embargo, tal relación de causa y efecto no es necesaria. El término información mutua sugiere (correctamente) que es igual de válido ver la salida como causar la entrada, o ignorar completamente la cuestión de qué causa qué. Dos fórmulas alternativas para\(M\) show que se\(M\) pueden interpretar en cualquier dirección:

\ [\ begin {align*}
M &=\ suma_ {i} p (A_ {i})\ log _ {2}\ Grande (\ frac {1} {p (A_ {i})}\ Grande) -\ suma_ {j} p (B_ {j})\ suma_ {i} p (A_ {i}\; |\; B_ {j})\ log _ {2}\ Grande (\ frac {1} {p (A_ {i}\; |\; B_ {j})}\ Grande)\\
&=\ suma_ {j} p (B_ {j})\ log _ {2}\ Grande (\ frac {1} {p (B_ {j})}\ Grande) -\ sum_ {i} p (A_ {j})\ Grande) -\ sum_ {i} p (A_ {j}) i})\ suma_ {j} p (B_ {j} \ mid A_ {i})\ log _ {2}\ Grande (\ frac {1} {p (B_ {j}\ mid A_ {i})}\ Grande)\ tag {6.27}
\ end {align*}\ nonumber\]

En lugar de dar una interpretación general de estas o fórmulas similares, simplemente veamos el canal binario simétrico. En este caso ambos\(p(A_i)\) y\(p(B_j)\) son iguales a 0.5 y así el primer término en la expresión para\(M\) en la Ecuación 6.26 es 1 y el segundo término se encuentra en términos de\(\epsilon\):

\[M=1-\varepsilon \log _{2}\left(\frac{1}{\varepsilon}\right)-(1-\varepsilon) \log _{2}\left(\frac{1}{(1-\varepsilon)}\right) \tag{6.28} \]

que pasa a ser 1 bit menos la entropía de una fuente binaria con probabilidades\(\epsilon\) y 1 −\(\epsilon\). Esta es una curva en forma de copa que va desde un valor de 1 cuando\(\epsilon\) = 0 abajo a 0 at\(\epsilon\) = 0.5 y luego retrocede hasta 1 cuando ε\(\epsilon\) = 1. Ver Figura 6.6. La interpretación de este resultado es sencilla. Cuando\(\epsilon\) = 0 (o cuando\(\epsilon\) = 1) la entrada se puede determinar exactamente cada vez que se conoce la salida, por lo que no hay pérdida de información. Por lo tanto, la información mutua es la misma que la información de entrada, 1 bit. Cuando\(\epsilon\) = 0.5 cada salida es igualmente probable, no importa cuál sea la entrada, así que aprender la salida no nos dice nada sobre la entrada. La información mutua es 0.