Mes: septiembre 2016

Demostrar que la información mutua es positiva \(I\left( X, Y \right) \geq 0\) y simétrica \(I \left( X, Y \right) = I \left( Y, X \right)\)

Para demostrar que la información mutua es positiva, tenemos que definir los valores de la información mutua entre dos símbolos. Para ello debemos tener en cuenta los valores extremos de \(P\left( x_i | y_j \right)\).

\(P\left( x_i | y_j \right) = 1\). Esta situación se da cuando tenemos un canal ideal sin ruido en el que si hemos recibido \(y_j\) es porque hemos enviado \(x_i\). De esta manera:
\[I \left( x_i, y_j \right) = \log{\frac{P \left( x_i | y_j \right)}{P\left( x_i \right)}} = \log{\frac{1}{P\left( x_i \right)}} = I \left( x_i \right)\]
En el otro extremo, tenemos cuando en el canal, la salida Y es independiente de X, por lo que es el peor canal que podemos tener. De esta manera, \(P\left( x_i | y_j \right) = P\left( x_i \right)\) por ser independientes.
\[I \left( x_i, y_j \right) = \log{\frac{P \left( x_i | y_j \right)}{P\left( x_i \right)}} = \log{\frac{P \left( x_i \right)}{P\left( x_i \right)}} = \log{1} = 0\]
 

Por tanto, queda demostrado que
\[0 \leq I \left( x_i, y_j \right) \leq I \left( x_i \right)\]
 

Por otra parte, queda demostrar que la información mutua es simétrica. Aplicando Bayes en la definición:
\[I \left( x_i, y_j \right) = \log{\frac{P \left( x_i | y_j \right)}{P\left( x_i \right)}} = \log{\frac{P \left( x_i , y_j \right)}{P\left( x_i \right) P\left( y_i \right)}} = \\ = \log{\frac{P \left( y_j | x_i \right) P\left( x_i \right)}{P\left( x_i \right) P\left( y_i \right)}} = \log{\frac{P \left( y_j | x_i \right) }{ P\left( y_i \right)}} = I \left( y_j, x_i \right)\]

Como hemos visto en la entrada anterior Concepto de la información, el término información nos da información sobre los posibles mensajes que una fuente puede producir. Sin embargo este término no es útil para describir a la fuente. Debido a que una fuente no está diseñada en torno a un solo mensaje, sino al conjunto de todos los mensajes que puede transmitir, podemos describir una fuente en términos de la información media producida. Esta información media transmitida se conoce como entropía de una fuente.

Si tenemos un alfabeto de longitud m \(X = \{ x_1, x_2, …, x_m \}\), la información del símbolo j es \(I_j = -\log{\frac{1}{P_j}}\). Si el número de símbolos enviados en el mensaje es \(N\), donde \(N >> 1\), el símbolo j se envía \(N \cdot P_j\) veces. Por tanto, la cantidad de información que se envía es:

\[ N P_1 I_1 + N P_2 I_2 + … + N P_m I_m = \sum_{i = 1}^{m}N P_i I_i~~~bits \]

La entropía de una fuente es el valor promedio de la información de cada uno de los símbolos de la fuente. Por tanto, si dividimos la expresion (\(\ref{eq:informacion_mensaje}\)) por el número de símbolos enviados \(N\), tenemos el valor medio en bits por símbolo:

\[ H\left(X \right) = E \{ X \} = \sum\limits_{i = 1}^{n} I_i \cdot P\left(x_i \right) = – \sum\limits_{i = 1}^{n} P\left(x_i \right) \cdot \log[P\left(x_i \right)] \]

con unas unidades de bits/símbolo.

Pero, ¿cuál es el significado de la entropía tal y como aparece en la ecuación de la entropía. Aunque no sepamos cuál es el siguiente símbolo que una fuente va a transmitir, en media podemos esperar conseguir \(H\) bits de información por símbolo o \(N\cdot H\) bits en un mensaje de N símbolos, si N es grande (mucho mayor que 1).

La entropía mide la cantidad de información que una fuente puede dar en un tiempo determinado

Rango de valores de la entropía de una fuente

De acuerdo, ya tenemos un parámetro para caracterizar una fuente. Veamos qué valores puede tomar este parámetro.

El mínimo de entropía se da cuando una fuente no da información. La fuente no tiene libertad de elección y siempre envía el mismo mensaje. Por tanto, la entropía es 0.

Por otra parte, la máxima entropía de una fuente se da cuando la fuente tiene máxima incerteza o lo que es lo mismo, máxima libertad de elección. Cada símbolo es igual de probable que el resto, por lo que \(P_j = \frac{1}{m}\) siendo \( m \) el número de símbolos. Así, \(\sum_{i=1}^{m}P_i I_i\) \(= \frac{1}{m} \log{\frac{1}{\frac{1}{m}}} \cdot m\) \(= \log{\frac{1}{\frac{1}{m}}} = \log{m}\).

De esta manera:

\[ 0 \leq H \leq \log{m} \]

Tasa de entropía

Ahora imaginemos que introducimos la variable de tiempo en la situación. Supongamos que tenemos dos fuentes con la misma entropía pero una es más rápida que la otra (i.e. enviando más símbolos por unidad de tiempo). De esta forma, la entropía no nos da ninguna información acerca de la velocidad con la que transmite la fuente. Es por ello que necesitamos de otro parámetro llamado tasa de entropía en la que informa de los bits enviados por segundo.

\[ R = \frac{H}{\bar{\tau}} \]

donde \( \bar{ \tau }  \) es la duración media por símbolo que se define como

\[ \bar{\tau} = \sum_{j=1}^{m} P_i \tau_i \]

y que \( 1/ \bar{\tau}\) equivale al número medio de símbolos por unidad de tiempo.

Anteriormente hemos hablado del concepto de información y de entropía en una fuente de comunicaciones, parámetros necesarios para poder modelar matemáticamente una fuente de información en comunicaciones. Toda fuente quiere enviar información a un destino, el usuario y de manera obligatoria debe utilizar un canal mediante el cual enviar esta información. En comunicaciones móviles sería el aire, en comunicaciones ópticas la fibra óptica o en comunicaciones guiadas podrían ser cables coaxiales, multifilares, etc.

Por tanto, es necesario disponer de herramientas para modelar el canal, ya que usualmente suele ser un entorno hostil en el que está presente ruido, interferencias y demás impedimentos que dificultan la comunicación. Normalmente, los terminales de comunicación se consideran perfectos (sin ruido, sin distorsión, etc.) y es en el canal en el que se tienen en cuenta todas estas no idealidades. Por tanto el canal se considera el vehículo de transmisión al que se le suman todos los fenómenos que tienden a limitar la comunicación. El hecho de que haya límites físicos para el envío de información nos lleva a la noción de capacidad del canal.

Del mismo modo que la entropía mide la cantidad de información que una fuente puede dar en un tiempo determinado, la capacidad del canal mide la cantidad de información que un canal puede transmitir por unidad de tiempo.

Teniendo en cuenta la capacidad del canal, el teorema fundamental de la teoría de la información se puede reescribir como:
\(C\) y una fuente con una tasa de entropía \(R\), si \(R \leq C\), existe una técnica de codificación tal que la salida de la fuente puede ser transmitida a lo largo del canal con una frecuencia de errores arbitrariamente pequeña a pesar de la presencia de ruido. Si \(R > C\), no es posible transmitir sin errores.

Caracterización de un canal

Un canal se caracteriza estadísticamente. La caracterización de un canal supone conocer la probabilidad de tener a su salida todos los símbolos que la fuente puede transmitir.

En un canal discreto sin memoria (los símbolos son independientes), la función de verosimilitud es la que caracteriza el canal

\[ P\left(Y | X \right) = \{ P\left(y_j | x_i \right) \} \]

La ecuación nos dice cuál es la probabilidad de que a la salida del canal haya el símbolo Y habiendo transmitido X, pues el receptor debe adivinar cuál ha sido X (el valor realmente enviado por la fuente) habiendo recibido el símbolo Y.

Otras definiciones que también se emplean son:
\[ P\left(X = x_i\right) = P\left( x_i\right)\]

La probabilidad a priori es propia de la fuente y nos dice cómo de probable es que un símbolo (\(x_i\)) se transmita.
\[ P\left(X | Y \right) = \{ P\left(x_i | y_j \right) \} \]
\[ P\left(X = x_i, Y = y_j \right) = P \left( x_i | y_j \right) P \left(y_j \right) = P \left(y_j | x_i \right) P \left( x_i \right)\]

La ecuación quiere decir que la probabilidad de enviar \(x_i\) y recibir \(y_j\) es la probabilidad a posteriori (enviar \(x_i\) habiendo recibido \(y_j\)) por la probabilidad de recibir \(y_j\) o del mismo modo, es la función de verosimilitud (probabilidad de recibir \(y_j\) habiendo enviado \(x_i\)) multiplicado por la probabilidad de enviar \(x_i\).

Dicho de otro modo más, ¿cuál es la probabilidad de tener \(x_i\) a la entrada e \(y_j\) a la salida? Si \(x_i\) fuese independiente de \(y_j\), la probabilidad debería ser \(P\left(x_i\right) \cdot P\left(y_j \right)\). Sin embargo, si tuviésemos un canal en el que su salida fuese independiente de su entrada sería una auténtica basura. Por eso es necesario tomar las probabilidades condicionadas. Probabilidad de tener \(y_j\) habiendo enviado \(x_i\) por la probabilidad de enviar \(x_i\).

Resumen

\(P\left( x_i\right)\) es la probabilidad de que la fuente seleccione el símbolo \(x_i\) para transmitir. (Probabilidad a priori)
\(P\left( y_j \right)\) es la probabilidad de que el símbolo \(y_j\) haya sido recibido en el destino (al otro lado del canal).
\(P\left( x_i, y_j \right)\) es la probabilidad conjunta de que \(x_i\) sea transmitido y \(y_j\) sea recibido.
\(P\left( x_i | y_j \right)\) es la probabilidad condicional de que \(x_i\) sea transmitido dado que \(y_j\) haya sido recibido. (Probabilidad a posteriori)
\(P\left( y_j | x_i \right)\) es la probabilidad condicional de que \(y_j\) sea recibido dado que \(x_i\) haya sido transmitido. Esta probabilidad incluye las probabilidades de error de símbolo. (Función de verosimilitud)

Ejemplo de canal discreto sín memoria

Canal binario borrador \(BEC(\epsilon)\)

	\(P\left(Y = 0 | X = 1\right) = 0\)
	\(P\left(Y = 1 | X= 1 \right) = 1 – \epsilon\)
	\(P\left(Y= ? | X = 1 \right) = \epsilon\)
	\(P\left(Y = 0 | X = 0 \right) = 1 – \epsilon\)
	\(P\left(Y = 1 | X = 0 \right) = 0\)
	\(P\left(Y = ? | X = 0 \right) = \epsilon\)

Información mutua \(I\left(X, Y \right)\)

En el ejemplo de arriba, tenemos una fuente con dos símbolos y un destino con tres símbolos. Si el sistema está diseñado para entregar \(y_j = y_1\) cuando \(x_i = x_1\) y \(y_j = y_2\) cuando \(x_i = x_2\), entonces la probabilidad de error de símbolo viene dada por \(P\left( y_j | x_i \right)\) para \(j \neq i\).

Una descripción cuantitativa de la información transferida en el canal es mediante la información mutua.
\[I\left(x_i, y_j \right) = \log_2{\frac{P\left( x_i | y_j \right)}{P\left( x_i \right)}}~~~bits\]
La información mutua mide la cantidad de información transferida cuando \(x_i\) es transmitido y \(y_j\) es recibido.

Rango de la información mutua

El máximo se consigue en el caso de tener un canal ideal sin ruido. Es decir, cuando se recibe \(y_j\) es porque se ha enviado \(x_i\). Por tanto \(P \left( x_i | y_j \right) = 1\) y \(I\left(x_i, y_j \right) = \log_2{\frac{P\left( x_i | y_j \right)}{P\left( x_i \right)}} = \log_2{\frac{1}{P\left(x_i\right)}} = I\left(x_i \right)\), en el que la información transmitida es la de \(x_i\).

El mínimo se da cuando el ruido del canal es tan grande que la salida del canal es independiente de la entrada, por lo que \(P \left( x_i | y_j \right) = P\left( x_i \right)\). En este caso\(I\left(x_i, y_j \right) = \log_2{\frac{P\left( x_i | y_j \right)}{P\left( x_i \right)}} = \log_2{\frac{P\left(x_i\right)}{P\left(x_i\right)}} = 0\)
\[0 \leq I\left(x_i, y_j\right) \leq I\left( x_i \right)\]
En la mayoría de los casos, los canales estan entre estos dos extremos. Para analizar el caso general, se define la información mutua media:
\[I\left(X, Y \right) = \sum_{i=1}^{N}\sum_{j=1}^{M} P\left(x_i, y_j\right) I\left( x_i, y_j\right)\]
\[ =\sum_{i=1}^{N}\sum_{j=1}^{M} P\left(x_i, y_j\right) \log_2{\frac{P\left( x_i | y_j \right)}{P\left( x_i \right)}}~~~bits/simbolo\]
\(I\left(X, Y \right)\) representa la cantidad información media ganada por símbolo recibido, que debe diferenciarse de la información media por símbolo de la fuente representado por \(H\left(X\right)\)

Equivocación o entropía condicional

Utilizando relaciones de probabilidad se puede llegar a expresiones equivalentes de la información mutua.
\[P\left(x_i, y_j \right) = P\left(x_i | y_j \right)P\left(y_j \right) = P\left( x_i | y_j \right)P\left( x_i \right)\]
\[P\left( x_i \right) = \sum_{j=1}^{N} P\left( x_i, y_j \right)~~~~P\left( y_j \right) = \sum_{i=1}^{N} P\left( x_i, y_j \right)\]
\[\log{\frac{a}{b}} = \log{\frac{1}{b}} – \log{\frac{1}{a}}\]
Si empleamos estas relaciones en , llegamos a:
\[I\left(X, Y\right) = \sum_{i=1}^{N}\sum_{j=1}^{M} P\left(x_i, y_j \right) \log_{2}{\frac{1}{P\left(x_i \right)}}\\-\sum_{i=1}^{N}\sum_{j=1}^{M}P\left(x_i, y_j \right)\log_{2}{\frac{1}{P\left(x_i | y_j\right)}}\]
De manera que el primer término se simplifica de la siguiente manera:
\[\sum_{i=1}^{N}\left[ \sum_{j=1}^{M} P\left( x_i, y_j \right)\right] \log_{2}\frac{1}{P\left(x_i \right)} = \sum_{i=1}^{N} P\left(x_i \right) \log_{2}\frac{1}{P\left(x_i \right)} = H\left(X \right)\]
Por lo tanto,
\[I\left(X, Y\right)= H\left(X\right)-H\left(X|Y\right)\]
En donde \(H\left(X|Y\right)\) es la equivocación o entropia condicionada, que representa la información perdida en el canal ruidoso.

La ecuación dice que la información media transferida por símbolo es la misma que la entropía de la fuente menos la equivocación.

Volviendo a la ecuación , debido a que \(P\left(x_i | y_j \right)P\left(y_j \right) = P\left( x_i | y_j \right)P\left( x_i \right)\), se demuestra que \(I\left(X, Y\right) = I \left(Y, X\right)\), y que por tanto,
\[I\left(X, Y\right)= H\left(Y\right)-H\left(Y|X\right)\]
En la ecuación se dice que la información transferida es igual a la entropia del destino \(H\left(Y\right)\) menos la entropía del ruido \(H\left(Y|X\right)\) añadido por el canal. La interpretación de \(H\left(Y|X\right)\) como entropía de ruido sigue la observación anterior de que \(P \left( y_j | x_i \right)\) incluye las probabilidades de error de símbolo.