Codigo Hamming

En el proceso de transmision de la informacion, se puede presentar distorsion sobre las señales que llevan esa informacion, dando origen a multiples errores. Estas distorsiones en muchos casos son generados por variables externas en el medio de comunicacion. Entonces debido a que estas señales son alteradas en dicho proceso, existe la posibilidad de que la informacion en el receptor sea diferente a la informacion en el transmisor. Este problema se soluciona mediante la aplicacion de diferentes algoritmos, en donde la clave es adicionar redundancia a la cadena de transmision que permita analizar los datos en dicha cadena.

Los diseñadores de redes han desarrollado dos estrategias basicas para manejar los errores. Una es dividir la cadena de datos a transmitir en bloques e incluir suficiente informacion redundante en cada bloque de datos transmitido, para que el receptor con base en lo anterior pueda deducir la informacion transmitida. La otra estrategia es incluir suficiente redundancia para que el receptor pueda determinar que ha ocurrido un error y entonces solicite una retransmision. Asi la capacidad del codigo de detectar y corregir errores, esta determinada por la cantidad de simbolos redundantes.

Deteccion de errores

Para detectar un error, en el caso de un codigo binario, se debe agregar un simbolo binario (0 o 1) a cada cadena de datos de K simbolos de informacion de forma tal que la cantidad total de unos en la cadena codificada sea par, es decir, que la cadena tenga paridad par. La distorsion de algun simbolos traslada la palabra codificada permisible al conjunto de las palabras prohibidas, lo que se detecta en el extremo receptor, debido a la cantidad impar de unos.

La propiedades de deteccion y correccion de errores de un codigo depende de su distancia de Hamming. Esta representa la cantidad de simbolos en los que una cadena de datos se diferencia de otra cadena y se simboliza con la letra "d". Para determinar la cantidad de bits diferentes, en el caso de una cadena binaria, basta aplicar una operacion OR exclusivo a las dos cadenas y contar la cantidad de bits 1 en el resultado, por ejemplo:

d=3, N=8

10001001 OR 10110001 = 00111000

En el caso anterior, se muestra que la distancia de Hamming es: d=3 y la longitud de la cadena de datos es: N=8.

La manera de saber si una cadena recibida tiene errores es identificando si dicha cadena es un codigo permisible. Entonces si se tiene un codigo con longitud N=3, indica que se tiene el siguiente codigo binario:

[000, 001, 010, 011, 100, 101, 110, 111]

Del codigo anterior se puede aplicar una distancia d=2, esto indica que el codigo anterior se divide en un codigo permisible y un codigo prohibido.

[000, 011, 101, 110] Codigo permisible.

[001, 010, 100, 111] Codigo prohibido

El decodificador despues de la recepcion puede realizarse de forma tal que la palabra codificada recibida se identifique con aquella palabra permisible que se encuentre con ella. Si el receptor encuentra que el codigo que llego es una palabra prohibida, detecta que hubo un error y pide retransmision.

Interpretacion geometrica de los codigos correctores

Cualquier palabra codificada binaria de n posiciones puede ser interpretada como el vertice de una figura geometrica n-dimensional con una longitud de arista unitaria. Para N=2, las palabras codificadas se ubican en los vertices de un cuadrado. Para N=3, las palabras codificadas se ubican en los vertices de un cubo unitario. Para N=4 las palabras codificadas se ubican en los vertices de un cubo tetradimensional.

d=2

d=3

d=4

En general el cubo unitario n-dimensional tiene 2n vertices que es igual a la mayor cantidad posible de palabras del codigo. Este codigo brinda una interpretacion geometrica sencilla a la distancia entre diferentes palabras del codigo, que corresponde a la menor cantidad de aristas del cubo unitario por las que es necesario pasar para ir de una palabra a otra.

Correccion de errores

Hamming es un metodo de codificacion en el que la informacion se toma por bloques a los que se les añade bits redundantes. La cantidad de bits redundantes depende de la siguiente formula establecida por Hamming:

N=2^k-1

Donde N es el numero total de bits a transmitir, k es el numero de bits de redundancia y k-N el numero de bits de datos. Entonces con base en lo anterior, se tiene las siguientes combinaciones de codigos:

(7,4): Indica que se transmiten bloques de 7 bits en donde 4 son de datos y 3 de redundancia.

(15,11): Indica que se transmiten bloques de 15 bits en donde 11 son de datos y 4 de redundancia.

(31,26): Indica que se transmiten bloques de 31 bits en donde 26 son de datos y 5 de redundancia.

Suponiendo que se desea trabajar con el codigo (7,4). La informacion que se desea enviar son 4 bits (D₀, D_1, D_2, D₃), a los que se le añaden 3 bits redundantes. Hamming define una matriz generadora la cual esta conformada por la matriz identidad  Iy por la Matriz de Hamming H que tiene las siguientes caracteristicas:

• Cada Fila de la matriz debe tener paridad Par
• Cada columna de la matriz debe tener la cantidad de unos mayor que la de ceros. 

Con esta matriz se puede generar la palabra de codigo a transmitir, ya que esta palabra un vector resultante de la multiplicacion de la matriz generadora transpuesta y el vector de codigo de datos (D₀, D_1, D_2, D₃).

Donde los bits (P_0, P_1, P₂) son los bits de redundancia. Estos bits se calculan mediante la OR Exclusiva de los bits a la que corresponden como se indica en la matriz anterior.

La ubicacion de cada uno de estos bits corresponde a una potencia de 2

• P₀= 2⁰ = 1
• P₁= 2¹ = 2
• P₂= 2² = 4

Entonces, si se desea transmitir el codigo 1000, los bits de redundancia seran:

• P₀ =D₁ +D₂ +D₃ = 0+0+0 = 0  
• P₁ =D₀ +D₂ +D₃ = 1+0+0 = 1
• P₂ =D₀ +D₁ +D₃ = 1+0+0 = 1

Dando como resultado la siguiente cadena a transmitir:

P₀  P₁  D₀  P₂  D₁  D₂  D₃

0   1   1   1   0   0   0

En el receptor se debe construir la siguiente Matriz y realizar la OR Exclusiva entre los bits de las columnas:

Si se recibe correctamente la informacion transmitida, la matriz queda construida de la siguiente manera

El codigo resultante fue 000, lo cual indica que el codigo recibido no tubo errores.

Si se tiene el siguiente codigo transmitido y recibido:

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo transmitido

0   1   1   1   0   0   0

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo recibido

0   1   0   1   0   0   0

Se construye la siguiente matriz:

El codigo resultante es 011, lo que indica que el tercer bit de la cadena de recepcion tubo un error. Entonces el receptor corrige dicho bit, formando la cadena correcta.

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo recibido

0   1   0   1   0   0   0

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo corregido

0   1   1   1   0   0   0

El bloque de datos recibido despues de la decodificacion es:

D₀  D₁  D₂  D₃

1   0   0   0

Ahora, si se tiene el siguiente codigo transmitido y recibido:

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo transmitido

0   1   1   1   0   0   0

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo recibido

0   1   1   1   1   0   0

Se construye la siguiente matriz:

El codigo resultante es 101, lo que indica que el quinto bit de la cadena de recepcion tubo un error.

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo recibido

0   1   1   1   1   0   0

P₀  P₁  D₀  P₂  D₁  D₂  D₃ Codigo corregido

0   1   1   1   0   0   0

El bloque de datos recibido despues de la decodificacion es:

D₀  D₁  D₂  D₃

1   0   0   0

En un sistema de transmision de datos, la informacion es muy vulnerable y propensa a tener errores. Los metodos de deteccion de errores permiten conocer si hubo o no un error en la cadena de datos recibido, pero no esta en condiciones de corregir dichos errores. Cuando se detecta un error por medio de un metodo de deteccion de errores, la manera de corregir la informacion es que el receptor pida una retransmision de la informacion.

Por medio del codigo de correccion de errores de Hamming, es posible no solo detectar, sino tambien corregir los errores ocurridos sobre la cadena de informacion en el receptor.

La deteccion y correccion de errores en un sistema de transmision de informacion, depende de la inclusion de redundancia sobre la cadena de transmision, es decir, a los datos se le a–ade informacion que permiten dar una peque–a descripcion de los mismos datos.

La cantidad de errores a detectar o corregir en un sistema con codigo de Hamming, depende de la distancia de Hamming "d".