Capacidad del canal gaussiano

En anteriores entradas hemos definido el canal gaussiano, que es el más comúnmente usado para modelar los efectos del canal. Ahora vamos a definir otro parámetro del canal gaussiano: su capacidad.

Para ello supongamos que utilizamos un código de repetición de n bits con una modulación BPSK.

Si queremos enviar el símbolo A, transmitiremos el valor \(\sqrt{P}\) es la amplitud de los símbolos en la modulación BPSK.

distance_detector
Diagrama de transmisión y recepción

Al enviar el símbolo de amplitud \(\sqrt{nP}\).

gaussian_repetitionPor el criterio de mínima distancia (definida como la distancia euclídea), se puede calcular la probabilidad de error como:
\[P_e = Q\left( \frac{\frac{|| x_A – x_B||}{2}}{ \sigma}\right) = Q\left( \sqrt{\frac{nP}{\sigma^2} } \right)\]
Por tanto, podemos hacer que la probabilidad de error en este canal sea tan pequeña como queramos simplemente aumentando el número de repeticiones. Sin embargo, esto es una mala estrategia ya que la velocidad de transmisión decrece con n. Si necesitamos n usos del canal para poder enviar 1 solo bit, nuestra codificación deja mucho que desear.

La manera de minimizar la probabilidad de error sin tener que aumentar el número de repeticiones es distribuyendo las palabras del código de forma eficiente a lo largo del espacio de la señal. En dos dimensiones (tal y como la figura anterior) equivaldría a separar tanto como pudieramos las dos gaussianas. Sin embargo, cuando nuestro código lo conforman n bits, el espacio de la señal deja de ser en 2 dimensiones y pasa a ser de n dimensiones.

Como vemos en el diagrama anterior, cuando el código c que enviamos pasa a través del canal se le añade un ruido w. De este modo, a la salida del canal tenemos la señal y que es igual a la suma del código y del ruido: y = c + w

Según la ley de los grandes números, cuando el número de bits del código n tiende a infinito, la potencia del ruido tiende valer su varianza \(\sqrt{P}\)

Por lo tanto, el código estará en un punto del hiperespacio Rn con distancia respecto al origen:
\[r_c = \sqrt{n P}\]
El ruido es aleatorio por lo que podría tener cualquier dirección del hiperespacio Rn y conforma una hiperesfera n-dimensional de radio:
\[r_w = \sqrt{n \sigma^2}\]
Así pues, cuando \(n \rightarrow \infty\), el vector y, que es la suma del código más el ruido del canal, estará en la superficie de una hiperesfera en Rn de radio ry:
\[r_y = \sqrt{n \left( P + \sigma^2 \right)}\]
Esta hiperesfera y con radio ry será la hiperesfera que englobe a todas las otras, ya que \(\sqrt{nP + \sigma^2}\) es la máxima amplitud que se puede enviar con la codificación de n repeticiones.

La comunicación será fiable siempre y cuando estas hiperesferas correspondientes para cada palabra código no se solapen. Teniendo esto en cuenta, el número máximo de palabras código que se podrán incluir dentro será la división entre el volumen de la mayor hiperesfera y el volumen de las hiperesferas de cada palabra codigo.

La superficie de una circunferencia es \(v_n = c_i r^n\). De este modo podemos definir esta relación de volumenes como:
\[\frac{V_y}{V_w} = \frac{r^n_y}{r^n_w} = \frac{\left( \sqrt{n\left( P + \sigma^2 \right)}\right)^n}{\left( \sqrt{n \sigma^2}\right)^n} = \left( 1+ \frac{P}{ \sigma^2} \right)^{\frac{n}{2}}\]
En consecuencia, si \(\left( 1+ \frac{P}{ \sigma^2} \right)^{\frac{n}{2}}\) es el número máximo de palabras código que caben en el espacio de la señal, el número máximo de bits por uso de canal que pueden ser transmitidos fielmente o con una probabilidad de error tan pequeña como se quiera por este canal será:
\[C = \underbrace{\frac{1}{n}}_{\text{cuantas veces uso el canal}} \underbrace{\log{ \left( 1+ \frac{P}{ \sigma^2} \right)^{\frac{n}{2}} }}_{\text{numero de bits necesarios para representar todos los simbolos}} = \frac{1}{n} \frac{n}{2} \log{ \left( 1+ \frac{P}{ \sigma^2} \right)} = \frac{1}{2} \log{ \left( 1+ \frac{P}{ \sigma^2} \right)}\]
Por lo que finalmente, la capacidad del canal AWGN es:
\[C =\frac{1}{2} \log{ \left( 1+ \frac{P}{ \sigma^2} \right) }\]
En el caso de canales complejos limitados en banda, podemos expresar la capacidad a partir del ancho de banda del canal B. El periodo del símbolo es el mismo que el tiempo de uso del canal, que equivale a \(\sigma^2 = N_0 B\). De esta manera, la expresión queda:
\[C =B \log{ \left(1 + \frac{P}{ \sigma^2 }\right) } = B \log{ \left( 1 + \frac{P}{N_0 B} \right) }= B \log{\left( 1 + SNR \right) }~~bits/s\]

Observaciones de la capacidad del canal gaussiano

  • Si la SNR es 0, la capacidad del canal también es 0.
  • La capacidad tiende a infinito si el ancho de banda B permanece constante y la SNR tiende a infinito, lo que significa que las comunicaciones sin ruido permiten tasas de transmisión infinitas.
  • Cuando el ancho de banda tiende a infinito:

\[C_{\infty} = \lim_{B \rightarrow \infty} \left[ B \log{ \left(1 + \frac{P}{ \sigma^2 } \right) } \right] \underbrace{=}_{\ln_e x = \frac{log_2 x}{log_2 e}} \\ = log_2 \left( e \right) \lim_{B \rightarrow \infty} \left[ B \ln{ \left( 1 + \frac{P}{ \sigma^2 } \right)} \right] \underbrace{=}_{l’H\hat{o}pital} \\ = \log_2{ \left( e \right) } \frac{P}{N_0} = 1.44 \frac{P}{N_0}\]
Por tanto, la máxima capacidad que podemos tener es \(C_\infty T_b = 1\),
\[C_\infty T_b = 1.44 \frac{P T_b}{N_0} = 1.44 \frac{E_b}{N_0} = 1 \Rightarrow \left. \frac{E_b}{N_0} \right|_{\text{min}} = \\ = \frac{1}{1.44} = 0.69 = -1.59~dB\]
que es el llamado límite de Shannon. Es la mínima relación entre la energía del bit y la densidad espectral de potencia del ruido a la que podemos transmitir.

coding_evolution

El canal gaussiano

El canal gaussiano se utiliza para modelar la amplia mayoría de casos reales en comunicaciones. A diferencia de los canales vistos anteriormente como el canal borrador o canal simétrico, el canal gaussiano es continuo. Este canal también es conocido como canal AWGN (Additive White Gaussian Noise Channel), en la que el ruido se modelo mediante una variable aleatoria gaussiana w, con media 0 y varianza \(\sigma^2\).

Una manera de poder detectar a la salida del canal los mensajes de la fuente, es mediante un detector por umbral.

threshold_detectorSi transmitimos símbolos BPSK de amplitudes ±A, las funciones de verosimilitud \(p_y \left( y | x = A \right)\) y \(p_y \left( y | x = -A \right)\) son gaussianas de media ±A y varianza \(\sigma^2\)

Para decidir si se ha enviado un 1 ó un 0, se utiliza el criterio de mínima distancia, de manera que si los símbolos equiprobables basta con saber si están a la derecha o izquierda del origen de coordenadas para decirdir si son un 1 ó un 0 respectivamente.

Función Q

La función Q es una función que calcula la integral de una gaussiana, de manera que la podemos aprovechar aquí para calcular el error de símbolo en la función de distribución de probabilidad.

gaussian

Si tenemos una función de probabilidad gaussiana con media \(\mu\), su expresión es:
\[p\left( x\right) = \frac{1}{\sigma \sqrt{2 \pi }}e^{-\frac{\left( x – \mu \right)^2}{2 \sigma^2}}\]
Si queremos saber la probabilidad que hay desde \(\mu + x_0\) hasta \(\infty\), la expresión utilizando la función Q es:
\[P\left( X > x_0 \right) = Q \left( \frac{ x_0 – \mu}{\sigma} \right)\]
De esta manera podemos calcular la probabilidad de error que se comete mediante el uso de detección por umbral:
\[P_e = Q \left( \frac{A}{\sigma} \right)\]

Demostración de los límites de la información mutua

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)\]

Entropía de una fuente en comunicaciones

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.

Información mutua

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.

Sistema de comunicación
Sistema de comunicación tal y como aparece en el paper de Shannon en 1984

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.

Canal discreto sin memoria
Canal discreto sin memoria

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)\)

Canal probabilidad

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.

Decodificación MAP: algoritmo BCJR

La decodificación MAP es aquella en la que se decide qué símbolo ha sido transmitido en función de la probabilidad a posteriori, es decir \(P\left(x_i | y_j \right)\) o la probabilidad condicional de que si se ha recibido \(y_j\), se haya transmitido \(x_i\). Dicho de otro modo, ¿cuál es el símbolo más probable que la fuente haya podido enviar \(x_i\) si yo he recibido \(y_j\)? Aquel de todos los posibles símbolos que se hayan podido transmitir cuya probabilidad a posteriori sea máxima, será el que se decida como transmitido.

\[hat{x}_i = \max{ \{ P\left( x_i | y_j \right) \} }\]

Pero sin embargo, para poder determinar esta probabilidad, al decodificador se le tiene que pasar la información del canal. En lugar de recibir del canal directamente si se ha enviado un 1 ó un 0 (salida hard), el decodificador tiene como entrada la información del espacio de la señal, es decir, con el valor analógico de la salida del canal. De esta manera el decodificador dispone de mayor información para tomar la decisión de cuál ha sido el código transmitido. Este valor representa una medida de la fiabilidad con la que es tomado cada símbolo y se conoce como un codificador con entrada soft.

Un modo de calcular estas probabilidades a posteriori de manera computacionalmente eficiente, es mediante el algoritmo BCJR (ideado por Bahl, Cocke, Jelinek y Raviv en el 1974). El algoritmo BCJR permite la obtenención de las LLR a posteriori (Log Likelihood Ratio) por bit (\(x_i\) binario):
\[LLR \left( x_i | y \right) = \ln{\frac{P \left( x_i = 1 | y \right) }{P \left( x_i = 0 | y \right)}}\]

Mediante el uso de la LLR, si la probabilidad de haber transmitido \(x_i = 1\) habiendo recibido y es mayor que la de haber transmitido \(x_i = 0\), el valor del logaritmo es positivo y negativo al contrario. Por eso, es más sencillo mirar el signo de la operación, que comparar directamente el valor absoluto de los dos valores.

A diferencia del algoritmo de Viterbi, el BCJR calcula de manera diferente cuál ha sido el bit más probable que se ha podido transmitir. Viterbi calculaba decisiones hard a partir de la detección de la secuencia de símbolos más probable, es decir, aquella que supusiera un recorrido cuya distancia a través del Trellis fuera de menor distancia. Sin embargo, el algoritmo BCJR calcula información soft. Por tanto, mientras que el algoritmo de Viterbi produce la secuencia de símbolos más probable que minimiza la probabilidad de error por secuencia, el algoritmo BCJR minimiza la tasa de error media por símbolo. Esta sutil diferencia hace que la detección de códigos mediante BCJR sea más ventajosa que utilizando el algoritmo de Viterbi.

Ambos algoritmos comparten similitudes ya que ambos están basados en el mismo diagrama de Trellis, ambos asignan una métrica a cada transición y ambos recorren el diagrama de trellis recursivamente. Sin embargo, en lugar de pasar de principio a final como hace Viterbi, en el algoritmo BCJR se realizan dos pasadas: de izquierda a derecha y de derecha a izquierda.
Revisando el diagrama de trellis

Imaginemos que estamos en la etapa i de un diagrama de trellis cualquiera tal y como aparece en la figura. En el diagrama de trellis podemos definir el dato que entrega el canal como \(y_i\). El estado antes de la transición como \(S_{i-1}\) y el diagrama después de la transición como \(S_i\).

 

La clave del algoritmo BCJR es la descomposición de la probabilidad a posteriori para una transición en tres factores: el primero dependiendo de las observaciones pasadas, el segundo dependiendo de observaciones presentes y el tercero atendiendo a observaciones futuras. Cabe destacar que cuando se aplica el algoritmo BCJR el receptor ya dispone de la trama completa de datos, por lo que es posible separar entre pasado, presente y futuro. Es decir, dado un bit en la posición i, el algoritmo sí tiene acceso a los bits que se enviaron después de él. No es un algoritmo que se aplica al vuelo conforme llegan bits.

La decodificación de un símbolo mediante el criterio MAP viene dada por:
\[hat{x}_i = \max_{x_i \in \left \{ \text{M simbolos} \right \} }{ \{ P\left( x_i | y \right) \}} = \left \{ \text{Teorema de Bayes} \right \} = \\ \max_{x_i \in \left \{ \text{M simbolos} \right \} }{ \frac{ p \left( x_i, y \right) }{ p \left( y \right) } } = \left \{ p \left( y \right) \text{ constante} \right \} = \\ \max_{x_i \in \left \{ \text{M simbolos} \right \} }{ \{ p \left( x_i, y \right) \} } = \max_{l \in \left \{ 0, 1, …, M -1 \right \} }{\sum_{\left( S_{i-1}, S_i \right) \in S^l } p\left( S_{i-1}, S_i, y \right) } donde l \in \left \{ 0, 1, …, M -1 \right \}\]

son todos los posibles símbolos \(y \left( S_{i-1}, S_i \right) \in S^l\) son las posibles transiciones que salen de cada estado cuando se envía el símbolo l. Por ejemplo, en una comunicación binario los únicos símbolos son 0 y 1 (es decir \(l \in \left \{ 0, 1 \right \}\) que en este caso se llaman bits). Por tanto, de cada estado que tenga el decodificador saldrán dos posibles transiciones. Una debida a la recepción del bit 0 y otra al bit 1. El conjunto de transiciones que ocurren cuando se recibe un 0 se denominan \(S^0\) y las transiciones que ocurren cuando al decodificador entra un 1 se denominan \(S^1\).

Por tanto, de la ecuación \(\ref{eq:limite}\) podemos interpretar que para estimar el símbolo \(\hat{x}_i\) con mayor probabilidad de haber sido enviado, hay que encontrar la suma de las probabilidades conjuntas de estar en el estado \(S_{i-1}\), ir al estado \(S_i\) y haber recibido los datos y para cada uno de los símbolos. Aquel símbolo que de una suma mayor, será el elegido como \(\hat{x}_i\).

Como hemos dicho antes, podemos descomponer el diagrama de estados en tres: pasado, presente y futuro. De este modo, los datos recibidos y se pueden descomponer como los datos recibidos en el pasado, el bit recibido en el presente y los bits que me llegarán en el futuro.
\(\mathbf{y}=\left [ \left ( y_1~y_2~…~y_{i-1} \right ), y_i, \left (y_{i+1}~y_{i+2}~…~y_{N} \right ) \right ] = \left[ \mathbf{y}_1^{i-1}, y_i, \mathbf{y}_{i+1}^N \right] \) donde \(\mathbf{y}_1^{i-1}\) representa a los datos recibidos en el pasado, \(y_i\) es el dato que recibo en el presente y \(\mathbf{y}_{i+1}^N\) son los datos que recibiré en el futuro. El subíndice 1 indica pasado, el i indica presente y el i+1 indica futuro. Así mismo, el superíndice i-1 indica la dimensión del vector. En el caso de los datos pasados el vector tendrá una dimensión desde 1 hasta i-1 (por tanto dimensión i-1). Para el caso de los datos futuros, la dimensión va desde i+1 hasta N, que es el número de símbolos enviados (o bits si la señal es binaria).

Ahora, a partir de la interpretación que hemos hecho arriba de la función densidad de probabilidad \(p\left( S_{i-1}, S_i, y \right)\), podemos aplicar el teorema de Bayes repetidas veces para conseguir una función equivalente pero separada en varios trozos.

A modo de recordatorio:
\[p\left( a, b \right) = p \left(a | b\right) p \left( b \right)\]
\[p\left( a, b, c \right) = p \left(a | b, c\right) p \left( b, c \right)\]
\[p\left( a, b, c, d \right) = p \left(a, b | c, d\right) p \left(c, d \right)\]

Teniendo en cuenta esto, podemos reescribir la función \(p\left( S_{i-1}, S_i, y \right)\) como, \(p\left( S_{i-1}, S_i, \mathbf{y} \right) = p \left( S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i, \mathbf{y}_{i+1}^N \right)= p \left(\mathbf{y}_{i+1}^N | S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) p \left( S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) \)

En \(\ref{eq:prob_states_1}\) hemos descompuesto los datos recibidos en pasado, presente y futuro. Después hemos escrito la misma función utilizando la probabilidad condicionada de los datos futuros \(\mathbf{y}_{i+1}^N\). Ahora volvemos a aplicar la probabilidad condicionada en el factor \(p \left( S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right)\) pero esta vez evaluando la expresión a llegar al estado \(S_i\) y que el dato sea \(y_i\) si estábamos en el estado \(S_{i-1}\) y los datos pasados son \(y_1^{i-1}\). \(p \left(\mathbf{y}_{i+1}^N | S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) p \left( S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) = \\ p \left(\mathbf{y}_{i+1}^N | S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) p \left(S_i, y_i | S_{i-1}, \mathbf{y}_1^{i-1} \right)p \left(S_{i-1}, \mathbf{y}_1^{i-1} \right)\)

Ahora fijémonos en cada término: \(p \left(S_{i-1}, \mathbf{y}_1^{i-1} \right)\): es la probabilidad conjunta de haber estado en el estado \(S_{i-1}\) y que los datos anteriores fueran \(\mathbf{y}_1^{i-1}\). A esta expresión la vamos a llamar \(\alpha_{i-1} \left( S_{i-1} \right)\).

\(p \left(S_i, y_i | S_{i-1}, \mathbf{y}_1^{i-1} \right)\): es la probabilidad de llegar al estado \(S_i\) con el símbolo \(y_i\) sabiendo que estábamos en el estado \(S_{i-1}\) y que se habían enviado anteriormente \(y_1^{i-1}\). Obviamente, los datos que se habían enviado anteriormente no van a afectar en dónde estaré posteriormente si ya sé que estaba en \(S_{i-1}\). Una analogía fácil para visualizar este hecho es el siguiente: yo estoy en el punto A. Desde este punto tengo dos caminos que puedo elegir: el camino 1 y el camino 0. Para determinar si voy a terminar en el punto B o no, me da exactamente igual saber qué camino escogí para llegar al punto A. Solo me importa donde estoy, dónde voy y qué caminos tengo para elegir en ese momento. Por tanto, la expresión \(p \left(S_i, y_i | S_{i-1}, \mathbf{y}_1^{i-1} \right)\) se puede simplificar como \(p \left(S_i, y_i | S_{i-1}\right)\). A esta expresión la vamos a llamar \(\gamma_{i} \left( S_{i-1}, S_i \right)\).
\(p \left(\mathbf{y}_{i+1}^N | S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right)\): siguiendo la analogía anterior, esta expresión representa cuál es la probabilidad de que escoja en el futuro una serie de caminos si ya sé dónde estoy, dónde estuve anteriormente, los caminos que escogí en el pasado y el camino que he cogido para llegar a dónde estoy ahora mismo. En este caso, poco importa saber dónde estuve hace tiempo, saber cómo llegué allí o cómo he llegado a donde estoy, ya que solo saber dónde estoy ahora mismo (\(S_i\)) me da información de adónde puedo ir \(\mathbf{y}_{i+1}^N\), cuáles serán los bits que me pueden llegar en el futuro). Por tanto, esta expresión la podemos simplificar como \(p \left(\mathbf{y}_{i+1}^N | S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right) = p \left(\mathbf{y}_{i+1}^N | S_i, y_i \right)\). A esta expresión la vamos a llamar \( \beta_{i} \left( S_{i} \right)\).

De esta forma podemos redefinir el diagrama de trellis como muestra la siguiente figura.

trellis_splited
Amarillo 0, azul 1

Así podemos calcular cuanto valdría P\left( x_i = 0 | \mathbf{y}\right):
\[P\left( x_i = 0 | \mathbf{y}\right) = \sum_{\left( S_{i-1}, S_i \right ) \in S^0}{p\left( S_{i-1}, S_i, \mathbf{y} \right )} = \\ = \sum_{\left( S_{i-1}, S_i \right ) \in S^0}{\alpha_{i-1}\left(S_{i-1} \right) \gamma_i \left(S_{i-1}, S_i \right ) \beta_i \left(S_i \right )} = \\ =\alpha_{i-1}\left(a \right ) \gamma_i \left(a, a \right ) \beta_i \left(a \right ) + \alpha_{i-1}\left(b \right ) \gamma_i \left(b, a \right ) \beta_i \left(a \right ) + \\ + \alpha_{i-1}\left(c \right ) \gamma_i \left(c, b \right ) \beta_i \left(b \right )+ \alpha_{i-1}\left(d \right ) \gamma_i \left(d, b \right ) \beta_i \left(b \right )\]

Para calcular \(P\left( x_i = 1 | \mathbf{y}\right)\) sería igual pero utilizando las otras transiciones. O también \(P\left( x_i = 1 | \mathbf{y}\right) = 1 – P\left( x_i = 0 | \mathbf{y}\right)\)
Cálculo de α
\[\alpha_i \left( S_i \right) = p \left(S_i, y_1^i \right ) =\sum_{S_{i-1}, S_i \in S}{p \left(S_{i-1}, S_i, \mathbf{y}_1^{i-1}, y_i \right)} = \\ = \sum_{S_{i-1}, S_i \in S}{p \left( S_i, y_i| S_{i-1}, \mathbf{y}_1^{i-1} \right)}p \left(S_{i-1}, \mathbf{y}_1^{i-1} \right) = \\ = \sum_{S_{i-1}, S_i \in S}{p \left( S_i, y_i| S_{i-1} \right )}\alpha_{i-1} \left(S_{i-1} \right) = \sum_{S_{i-1}, S_i \in S}{\alpha_{i-1} \left( S_i \right)}\gamma_{i} \left(S_{i-1}, S_i \right)\]

Donde \(1 \leq i \leq N\) y \(N\) el número de símbolos enviados. Como vemos es un cálculo recursivo, en el que necesitamos el valor del α anterior para calcular el siguiente.
Cálculo de β
\[\beta_{i-1} \left(S_{i-1} \right ) = p \left(\mathbf{y}_i^n |S_{i-1} \right ) = \sum_{S_{i-1}, S_i \in S}{p \left( y_i,\mathbf{y}_{i+1}^n, S_i |S_{i-1}\right )}= \\ =\sum_{S_{i-1}, S_i \in S}{p \left(\mathbf{y}_{i+1}^n | S_i, y_i, S_{i-1}\right ) p \left( S_i, y_i| S_{i-1}\right )} =\\=\sum_{S_{i-1}, S_i \in S}{p \left(\mathbf{y}_{i+1}^n | S_i\right ) p \left( S_i, y_i| S_{i-1}\right )} =\sum_{S_{i-1}, S_i \in S}{\beta \left(S_i\right ) \gamma_i\left( S_{i-1}, S_i\right )}\]
Cálculo de γ
\[\gamma_i \left(S_{i-1}, S_i \right ) = p \left(S_i, y_i | S_{i-1} \right ) =p \left(y_i | S_i, S_{i-1} \right ) p \left(S_i | S_{i-1} \right) = p \left(y_i | c_i \right ) p \left( x_i \right )\]

Como podemos ver y era de esperar, el parámetro \(\gamma\) depende del canal, ya que \(p \left(y_i | c_i \right )\) es la función de verosimilitud que caracteriza el canal. En caso de ser un canal gaussiano, la \(p \left(y_i | c_i \right ) = \frac{1}{\sigma^2 \sqrt{\pi}} \cdot e^{- \frac{\left| y_i – c_i \right|^2}{2\sigma^2} }\)