En un sistema de comunicaciones, detectar un error es más sencillo que corregirlo. Si existen irregularidades, el receptor puede pedir una retransmisión del mensaje que contiene el error (ARQ: Automatic Repeat Request). Sin embargo, cuando el sistema no implementa esta técnica por no ser práctico o simplemente porque no es posible, debe aplicar redundancia en el código a través del método FEC (Forward Error Correction).

El método más sencillo de redundancia en el código consiste en repetir n veces el símbolo de mensaje. Cuando los símbolos son 1 y 0, cualquier error de transmisión en una palabra código recibida alterará el patrón de repetición cambiando un 1 a 0 (o viceversa). Si los errores de transmisión ocurren de forma aleatoria (e independiente) con probabilidad Pe, entonces se pudiera definir la probabilidad de que ocurran i errores en una palabra código de n bits como:

Figura 1

Por ejemplo, si se considera un código de repetición triple (3, 1) (1 bit de mensaje, dos bits de repetición, palabra código de tres bits), las palabras código serían 000 y 111. Cualquier mensaje recibido que no coincida con estas palabras código evidencian la presencia de errores. Pero, si los tres bits están errados (Se transmite 000 pero se recibe 111) entonces será imposible detectar el error:

Figura 2

Si se quiere corregir el error, asumimos que al menos dos de los tres bits son correctos. Entonces, 001 se decodifica como 000 y 101 se decodifica como 111. Esto corrige palabras con un solo error, pero para dos o tres errores la probabilidad de que una palabra esté errada resulta como:

Figura 3

Una palabra código de n bits puede ser representarse como un vector en un espacio de n dimensiones. Por ejemplo, el código 010 puede representarse como X=( 0 1 0 ). Tomemos el caso anterior de código de repetición (3, 1):

Figura 4: Vectores que representan palabras código de tres bits.

En total se grafican las 8 posibles combinaciones de palabras código y los puntos azules representan el código de repetición. La distancia que separa dos puntos cualesquiera se reconoce como la distancia Hamming, que está relacionada con el poder de control de errores del código (Fortaleza del código) y se define como el número de elementos diferentes entre dos puntos. Por ejemplo:

Figura 5

La distancia mínima de un código en particular es la distancia Hamming más pequeña entre dos vectores de código válidos. De esta forma, la detección de errores es posible siempre que se cumpla que el número de errores de transmisión en una palabra código sea menor a d_mín, por lo que la palabra errada no es un vector válido. Si es mayor o igual, la palabra errada puede corresponder a un vector válido y el error no podría ser detectado.

La capacidad de corrección y detección de un código se define como:

Figura 6

Para el ejemplo desarrollado, dmín= 3, por lo que el código de repetición es capaz de corregir hasta 1 error por palabra y detectar hasta 2 errores. Evidentemente, la fortaleza del código depende del número de bits que se le agregan al mensaje original. La distancia mínima de una codificación por bloque (repetición) se define como:

Figura 7

Un sistema FEC puede expresarse gráficamente como:

Figura 8

Los bits de entrada llegan con una tasa de r_b. El codificador toma bloques de k bits del mensaje y construye un código de bloques (n, k) con tasa Rc=k/n<1. La tasa de bits del canal será r= r_b/ Rc> r_b. La probabilidad de error tomará un valor de Pe<<1, que evidentemente dependerá de la energía de la señal y la densidad de potencia del ruido en el receptor (₀). Si Eb representa la energía promedio por bit de mensaje, entonces la energía promedio por bit de código es Rc.Eb. Entonces:

Figura 9

Es un código de bloques lineal (n,k) con 3 ó más bits de chequeo/redundancia (q) que cumple con estas ecuaciones:

Figura 19

Dado que su distancia mínima siempre es 3 (sin importar el valor de q), este tipo de código es capaz de corregir hasta un error y detectar dos, por lo que:

Figura 20

Supongamos el caso Hamming (7,4) (n=7, q=3, k=4). Para construir dicho código, tomamos la sub-matriz P de la matriz generadora G y la llenamos con todas las palabras de q bits que tengan dos o más 1’s, sin ningún orden en particular. Como son k=4 bits de mensaje original, entonces la matriz G tendrá cuatro filas. Entonces:

Figura 21

Dado un bloque de bits de mensaje M = (m₁ m₂ m₃ m₄), los bits de chequeo se calculan sustituyendo los elementos de la sub-matriz P en la ecuación C=MP, por lo que:

Figura 22

Para este ejemplo se pudiera construir un codificador Hamming de la siguiente forma:

Figura 23

Las palabras código correspondientes a este código Hamming (7,4) se observan en la tabla (Todas generadas a partir de C=MP):

A diferencia de la codificación por bloque, los códigos convolucionales trabajan bit por bit. Su estructura pudiera generalizarse de la siguiente forma:

Figura 24

Esta estructura genera V símbolos a la salida por cada símbolo de entrada. Su tasa de símbolos de salida será entonces Rc=1/V. Existen 4 métodos de representación de los códigos convolucionales:

Supongamos que se tiene el siguiente codificador convolucional:

Figura 25

Para que el código funcione correctamente, antes de que llegue el primer bit del mensaje el registro de desplazamiento está ‘limpio’ (Sólo contiene 0’s). Esto implica que la primera salida será U1=0 y U2=0. Supongamos que el mensaje de entrada es 101. Entonces, el codificador hará los siguientes pasos:

Figura 26: Diagrama de conexión con salidas U1 y U2 cuando se tiene como mensaje de entrada la secuencia 101. Se asume que inicialmente los registros están vacíos.

La secuencia de salida será:

El estado del codificador convolucional se define como los contenidos de los registros de desplazamiento de las k-1 etapas más a la derecha del codificador. Para el ejemplo actual:

Figura 27: Diagrama de estados.

La raíz representa el estado inicial (U1U2=00). Si el próximo bit es un 0, se toma la ramificación superior. Dado que la longitud del registro es igual a 3 (L=3), entonces el árbol será:

Figura 28

A través de él se puede observar la evolución del codificador por cada T que pase. El diagrama deberá tener 2^k-1 nodos que representen los posibles estados (a,b,c y d). Entonces:

Figura 29

Para la decodificación implementamos la máxima verosimilitud (maximum-likelihood), que busca maximizar P(Z/Um), siendo Um las posibles secuencias recibidas.

Figura 30

Esto puede verse a través del Algoritmo de Viterbi: Se basa en el Diagrama de Trellis. Asigna a cada rama una métrica que es igual a la distancia Hamming correspondiente a la rama recibida y todas las ramas de Trellis que intervienen en ese instante de tiempo. Supongamos el siguiente ejemplo:

Figura 31

Como se observa, se debe esperar hasta el instante T4 (que es cuando empiezan a cerrarse los lazos) para tomar una decisión sobre el camino más corto. Allí, se tendrán dos caminos para llegar a ese instante:

Figura 32

Partiendo del estado a, en el estado 4 convergen dos trayectorias dos métricas: la primera con un total de 4(la de arriba) y la segunda con un total de 3(la que va por debajo). Luego se analizan situaciones similares en T4. Por ejemplo, al estado b en T4 se llega por dos trayectorias: la de arriba con métrica 4 y la de abajo con métrica 3. Para T4 pero al estado c también se llega por dos caminos: el de arriba con métrica 5 y el de abajo con métrica 0. Para T4 pero al estado d los dos caminos tienen métricas 3 y 2 respectivamente. Al eliminar todas las trayectorias de métrica mayor, en este ejemplo se logra ya despejar el bit transmitido entre la transición T1-T2 y decidir que es un “1”.

Figura 33

Se repite el mismo procedimiento para el nodo T5 y luego para los demás nodos hasta que se vayan obteniendo cada uno de los bits transmitidos.

Se descartan entonces todos los caminos no viables. Este proceso debe repetirse hasta que se logre obtener la secuencia original.

Figura 34

Las pruebas para las codificaciones Hamming(7,4), Hamming(15,11) y Convolucional pueden realizarse descargando el VI del siguiente enlace: