INTRODUCCIÓN

Retornar al Índice

En cualquier sistema de comunicaciones es necesario recibir de forma fiable y libre de errores la información transmitida desde la fuente. Para ello existen dos estrategias posibles:

En ambos casos, es necesario añadir cierta redundancia al mensaje a transmitir para detectar o corregir estos errores, y al proceso de añadir esta redundancia es a lo que se denomina codificación de canal.

La codificación convolucional y los códigos de bloques son dos de las principales técnicas empleadas en la codificación de canal. En concreto, la codificación convolucional con la decodificación de Viterbi es de las técnicas FEC más adecuadas en canales en los que la señal transmitida se ve corrompida principalmente por ruido gausiano blanco y aditivo (AWGN). Muchos canales de radio se pueden modelar como "canales AWGN", aunque también hay otros muchos, particularmente los canales de radio terrestres, en los que nos encontramos con otro tipo de deterioros en la señal, como pueden ser los causados por el multitrayecto, fading selectivo, interferencias y ruido atmosférico. Además, los propios transmisores y receptores pueden añadir espúreos y ruido de fase a la señal. Aunque la codificación convolucional con la decodificación de Viterbi puede resultar útil tratando este tipo de problemas, puede que no sea la técnica más óptima en estos casos.

Por todos estos motivos durante años la codificación convolucional junto con la decodificación de Viterbi ha sido la técnica FEC predominante usada en las comunicaciones espaciales, particularmente en las redes de comunicaciones de satélites geoestacionarios, como son por ejemplo las redes VSAT. Utilizando esta técnica de codificación de canal y simples modulaciones BPSK o QPSK se puede llegar a necesitar 5dB de potencia en transmisión de la que se necesitaría si no se utilizase codificación de canal para alcanzar la misma tasa de error de bit (BER: Bit Error Rate). Esto es una reducción en watios en más que un factor de 3, y es muy útil para reducir los costes del transmisor y de la antena o permitir mayores tasas de datos para la misma potencia de transmisión y tamaño de antena.

Para nuestro caso en concreto, hay que decir en la telefonía celular GSM también se emplea la convolucional con la decodificación de Viterbi, pero que por un lado no se aplica a todos los bits que forman la trama GSM y que además, no es la única codificación de canal empleada, sino que hay ciertos bits que, debido a su gran importancia dentro de la trama, se protegen adicionalmente mediante el empleo de un código CRC.

CODIFICACIÓN CONVOLUCIONAL

Retornar al Índice

Los códigos convolucionales se describen a partir de ciertos elementos como son la tasa del código, la longitud del código, la memoria del codificador y los polinomios generadores. La tasa del código, k/n, es la relación entre el número de bits que entran al codificador (k) y el número de bits que se obtienen a la salida del codificador (n). En cuanto a la longitud del código, K, denota en cuántos ciclos de codificación tiene influencia un bit que tengamos a la entrada del mismo a partir de un instante dado, ya que recordemos que este bit que tenemos a la entrada del codificador en un instante dado irá recorriendo la cadena de flip-flops que forman el registro de desplazamiento. Así, un parámetro muy relacionado con K es la memoria del codificador, m, que precisamente es el número de flip-flops que contiene el codificador. Por último, los polinomios generadores son también muy importantes a la hora de definir el funcionamiento de un codificador convolucional, y veremos mejor su significado mediante un ejemplo.

La codificación convolucional se realiza básicamente mediante el uso de un registro de desplazamiento y una lógica combinacional encargada de la realización de la suma en módulo 2. El registro de desplazamiento está implementado mediante la concatenación de una serie de flips-flops, de manera que cada vez que llega un ciclo de reloj, el dato que tenemos a la entrada de un flip-flop pasa a su salida y se sitúa por tanto en la entrada del siguiente flip-flop, que ha hecho lo propio con el dato que tenía en su entrada cuando llegó el ciclo de reloj. En cuanto a la lógica combinacional que realiza la suma en módulo 2, basta con utilizar puertas XOR.

En la siguiente figura podemos apreciar un ejemplo de codificador convolucional, en el que la tasa del código es 1/2, K=3 y m=2. En este codificador, los bits de entrada llegan con una tasa de k bits por segundo y obtenemos una tasa a la salida del codificador de n=2k bits por segundo. El bit de entrada se mantiene estable durante el ciclo de codificación, el cual comienza cada vez que llega un ciclo de reloj. Cuando llega el ciclo de reloj, la salida del flip-flop izquierdo se introduce en el flip-flop derecho, es decir, pasa a la salida de éste, y el bit que teníamos a la entrada del codificador previamente pasa a la salida del primer flip-flop. Es entonces cuando el nuevo bit está disponible en la entrada. En cuanto al multiplexor que tenemos a la salida, conmuta durante el ciclo de reloj entre las dos posiciones, de manera que primero selecciona la salida del sumador superior y posteriormente selecciona la salida del sumador inferior, formando así el símbolo de dos bits. En cuanto a los polinomios generadores, en este caso se trata de un codificador (7,5). Estos dos números representan los polinomios generadores, ya que las representaciones binarias de estos números (111 y 101) se corresponden con las conexiones del registro de desplazamiento y los sumadores superior e inferior respectivamente. En este caso los polinomios generadores serían 1 + x + x2 y 1 + x2 respectivamente.

Veamos ahora el funcionamiento de la codificación convolucional mediante un ejemplo. Supongamos la secuencia de entrada 010111001010001. Supongamos también que las salidas de ambos flip-flops están inicialmente a 0. El primer ciclo de reloj hace que el primer bit a la entrada, 0, esté disponible a la entrada del codificador. Las salidas de los flip-flops son ceros y por tanto todas las entradas a ambos sumadores son también ceros, por los que la salida de ambos sumadores es 0, de manera que el símbolo de salida sería el 00.

El segundo ciclo de reloj hace que el segundo bit de entrada esté disponible para el codificador. Ambos flip-flops leen los bits que tenían en sus entradas previamente, que en ambos caso eran 0. Así, las entradas al sumador superior son 100, de manera que su salida es 1. Análogamente las entradas al sumador inferior son 10, por lo que su salida también es un 1. Por tanto, el símbolo codificado esta vez sería el 11.

El tercer ciclo de reloj hace que el tercer bit de entrada, un cero, esté disponible para el codificador. El primer flip-flop lee su entrada anterior, que era un 1, y el segundo flip-flop hace lo mismo leyendo el cero que tiene en este caso en su entrada, por lo que ahora las entradas a los sumadores son 010 y 00, lo que hace que el símbolo obtenido en esta ocasión sea el 10. Después de que todos los bits de entrada hayan pasado por el codificador, la secuencia de salida sería:

00 11 10 00 01 10 01 11 11 10 00 10 11 00 11.

En este ejemplo se puede ver claramente como cada bit de entrada tiene efecto en los 3 símbolos de salida siguientes, ya que se trata de un codificador con K=3. De hecho este es un punto extremadamente importante y es lo que le da a la codificación convolucional la potencia para corregir errores.

Por este motivo, si queremos que el último bit afecte a tres símbolos de salida se necesitan dos símbolos de salida adicionales. Esto se consigue introduciendo dos bits a cero en el codificador en los dos siguientes ciclos de reloj. Con esto conseguimos los dos símbolos adicionales que necesitamos y además "limpiamos" el registro de desplazamiento, de manera que para la próxima secuencia a codificar tendremos a las entradas de los flip-flops un 0, como supusimos inicialmente. En general, el número de ceros que tenemos que introducir es igual al número de flip-flops que contiene nuestro codificador.

De esta explicación se pueden extraer algunas conclusiones, y es que podemos ver el algoritmo de codificación convolucional como una máquina de estados. El codificador del ejemplo tiene dos bits de memoria, lo que significa que tenemos cuatro estados posibles. Podemos decir que el estado lo definen las entradas que tienen los flip-flops en un instante dado. Por ejemplo, si en ambas entradas tenemos un cero, estaremos en el estado 00, si la primera entrada es un cero y la segunda es un uno, estaremos en el estado 01 y así sucesivamente. Asimismo, si estando en el estado 00 (ambas entradas a cero) el bit que tenemos a la entrada cuando llega el siguiente ciclo de reloj es un cero, entonces permaneceremos en el estado 00. Sin embargo, si el siguiente bit a la entrada es un uno en lugar de un cero, pasaremos al estado 10. Análogamente, si estando en el estado 10 el siguiente bit a la entrada es un cero, pasaremos al estado 01 mientras que si el bit de entrada es un 1, pasaríamos al estado 11. Por tanto podemos completar la tabla 1 que nos indica cuál es el siguiente estado dependiendo del estado en el que estamos y del bit que nos llega a la entrada y la tabla 2, que nos indica cuál es el símbolo de salida en función de nuevo del estado en el que nos encontramos y del bit de entrada que nos llega.

Estado Actual Estado siguiente si...
Entrada = 0 Entrada = 1
00 00 10
01 00 10
10 01 11
11 01 11

Estado Actual Símbolo de salida si...
Entrada = 0 Entrada = 1
00 00 11
01 11 00
10 10 01
11 01 10

ALGORITMO DE VITERBI

Retornar al Índice

El algoritmo de Viterbi es uno de los dos tipos de decodificación que se pueden emplear con la codificación convolucional. El otro algoritmo es la decodificación secuencial, que tiene la ventaja que se puede ejecutar muy bien sobre códigos convolucionales con grandes longitudes (K), aunque el proceso de decodificación no tiene una duración fija sino variable. El algoritmo de Viterbi tiene la ventaja de que emplea un tiempo de decodificación fijo, lo que lo hace idóneo para implementarlo mediante hardware. Por otro lado, los recursos computacionales necesarios para su implementación crecen exponencialmente con K, por lo que usualmente en la práctica como máximo sólo se realizan implementaciones hasta K=9.

El algoritmo de decodificación de Viterbi basa su funcionamiento en el llamado diagrama de Trellis. En dicho diagrama se intentará ir reconstruyendo las transiciones que se produjeron al codificar una secuencia de entrada dada, de manera que así podamos en el decodificador cual fue dicha secuencia de entrada. En la siguiente figura podemos apreciar el diagrama de Trellis para el ejemplo anterior de tasa 1/2, K=3 y un mensaje de entrada de 15 bits (que se convertía en un mensaje de 17 bits con los dos últimos a cero).

Los cuatro posibles estados del codificador se representan como las cuatro filas de puntos horizontales. Hay una columna de cuatro puntos para el estado inicial del codificador y una columna de las mismas características para cada uno de los 17 instantes siguientes a ese instante inicial t=0. Las líneas sólidas representan las transiciones de estado cuando la entrada es un uno y las líneas discontinuas las transiciones cuando la entrada es un uno. Dichas transiciones se basan siempre en la tabla de transiciones que se utilizó en la codificación convolucional vista anteriormente.

Además de la transición entre estados, vimos en la explicación del algoritmo de codificación que dependiendo del estado actual y del bit de entrada se obtenía un símbolo codificado u otro. En la siguiente figura podemos ver los símbolos que se obtienen cuando se produce una determinada transición, donde de nuevo las líneas continuas corresponden a un bit de entrada '1' y las discontinuas a un bit de entrada '0'.

Una vez visto cuál es el funcionamiento del diagrama de Trellis pasemos a ver cómo funciona el algoritmo de Viterbi. En la siguiente figura podemos ver cuál sería la secuencia de transiciones en el diagrama de Trellis para codificar el mensaje visto en la explicación de la codificación convolucional. Dicho mensaje se puede ver también al pie del dibujo. asimismo, también vemos la secuencia de símbolos codificados correspondientes a dicha entrada. La siguiente línea de números se corresponde con la secuencia que hipotéticamente se ha recibido en el decodificador, que como vemos tiene ciertos errores con respecto a la secuencia de símbolos correcta.

Cada vez que se recibe un símbolo de canal compuesto por dos bits, vamos a calcular una distancia entre el símbolo recibido y todos los posibles símbolos de canal que podríamos haber recibido dependiendo del estado actual en el que nos encontramos o que nos podríamos encontrar. La distancia que vamos a utilizar es la distancia de Hamming, que consiste en contar el número de bits diferentes entre el símbolo recibido y los posibles símbolos recibidos. Por tanto las únicas posibles distancias son 0, 1 ó 2 puesto que los símbolos están compuestos por dos bits. Así, al pasar del instante t=0 al t=1 sólo hay dos posibles símbolos que podríamos haber recibido, 00 y 11, porque sabemos que el codificador comenzó su funcionamiento en el estado 00. Según podemos observar en la figura podemos ver que el símbolo recibido en t=1 es el 00. Por tanto, teniendo en cuenta que se podrían haber recibido los símbolos 00 y 11, las distancias de Hamming serían 0 y 2 respectivamente. Las distancias que calculamos en cada instante de tiempo para los caminos entre los estados en el instante previo y los estados en el instante actual se denominan "distancias de la rama". El proceso de decodificación se basará en seguir los posibles caminos compuestos por las transiciones entre estados guardando también cuál es la distancia acumulada de cada camino, siendo la distancia acumulada la suma de la "distancia de una rama" en el instante actual y la distancia acumulada de los instantes anteriores. Así, para el instante t=1, como las distancias acumuladas anteriores eran iguales a 0, las distancias acumuladas para los instantes 00 y 01 son 0 y 2, como queda representado en la siguiente figura.

Nótese que las líneas muestran dos posibles caminos desde el estado inicial, mostrando una relación de predecesor-sucesor que en la práctica deberá guardarse numéricamente para poder llegado el momento reconstruir el camino más probable en función de las distancias acumuladas obtenidas al final del algoritmo para cada estado.

Veamos lo que ocurre ahora en t=2. En ese instante recibimos el símbolo 11. Los posibles símbolos que podíamos haber recibido en ese instante de tiempo desde los diferente estados en los que nos podíamos encontrar en t=1 son 00 si estando en el estado 00 recibimos un 0 y nos quedamos en el estado 00, 11, si estando en el estado 00 pasamos al estado 10, 10 si vamos del estado 10 al 01 y 01 si vamos del estado 10 al 11. Las distancia Hamming entre 00 y 11 es dos, entre 11 y 11 es cero, y entre 10 o 01 y 11 es uno. Si añadimos estas "distancias de rama" a las distancias acumuladas asociadas con los estados desde los que venimos nos queda lo que se representa en la siguiente figura.

En t=1 sólo podíamos estar en el estado 00 o en el estado 10. Las distancias acumuladas de dichos estados eran 0 y 2 respectivamente. Los datos que tendríamos que tener almacenados para seguir con el algoritmo en t=3 serían las distancias acumuladas para cada uno de los estados en los que podríamos estar y cuál es el estado anterior para cada uno de los estados en t=2.

En la siguiente figura vemos lo que pasa para t=3. El proceso sería completamente análogo que el realizado en t=2, sólo que ahora a cada uno de los estados podemos llegar desde dos estados posibles. La manera de actuar es comparar la distancia acumulada que me produce el llegar desde ambos estados y descartar el origen que me produciría una distancia acumulada mayor. En caso de que ambas fuesen iguales, simplemente elegiríamos una de los dos. La rama que gana en dicha comparación recibe el nombre de "superviviente". Nótese que en t=3 se ha recibido un símbolo erróneo, y que precisamente la menor distancia acumulada es precisamente 1. También podemos ver que hay dos ramas que tienen este valor de distancia acumulada, pero cuando todo el proceso haya terminado, esto no será así. De hecho, en el siguiente instante de tiempo el camino asociado con aquel estado que aun con la elección de un estado erróneo tenía una distancia acumulada 1, ya tendrá una distancia acumulada mayor.

Una vez realizado este proceso hasta llegar al instante t=17 llegaríamos a una situación como la que se muestra en la figura, en la que se han eliminado por comodidad todos los posibles caminos y nos hemos quedado únicamente con el camino que terminaba con una distancia acumulada menor. Este es el camino con el que nos quedamos y a partir del cual se reconstruirá el mensaje enviado.

Teniendo en cuenta que hemos ido almacenando los estados predecesores en cada instante de tiempo, ahora sólo tendríamos que ir recorriendo el camino hacia atrás y extrayendo los bits de entrada que nos harían ir en cada instante de tiempo de un estado a otro en el camino elegido, consultando la tabla que se empleó para codificar.

CODIFICADOR CONVOLUCIONAL EMPLEADO EN GSM

Retornar al Índice

El codificador convolucional que emplea GSM es un codificador de tasa 1/2 y de longitud K = 5, por lo que es similar al que hemos desarrollado en el ejemplo pero un poco más complejo, ya que tiene algo más de memoria (m=4).

En la siguiente figura se representa el diagrama de bloques del codificador convolucional de GSM. Podemos observar que como en el ejemplo anterior tenemos dos caminos, ya que la tasa es de 1/2, y el multiplexor es de 2 a 1. Como m = 4, tenemos cuatro flip-flops.

De la propia identificación gráfica del diagrama de la figura, podemos obtener los dos polinomios generadores que para GSM son 1 + x3 + x4 y 1 + x + x3 +x4.

Retornar al Índice