Código Hamming de corrección automática de errores

Este sistema inventado por Richard W. Hamming (1950) asocia bits de paridad par con combinaciones únicas de bits de datos. Este método permite detectar y corregir con seguridad hasta un bit por cada bloque de información transmitida.

A cada n bits de datos se le añaden k bits de paridad de tal forma que el carácter transmitido tiene n+k bits de longitud. Los bits se numeran de izquierda a derecha (el 1º bit es el más significativo). Todo bit cuyo número sea potencia de 2 es un bit de paridad, los restantes serán bits de datos. Los bits de dato se acomodan en sus posiciones y los bits de paridad se calculan de modo que tengan una paridad par sobre los bits cuyo número de bit formen, por ejemplo: El bit 1 (paridad) es determinado por los bits de datos: 3 (1+2=3), 5 (1+4=5), 7 (1+2+4=7), 9 (1+8=9), etc...

De esta forma cada bit está verificado por una combinación única de bits de paridad, de modo que analizando los errores de paridad se puede determinar que bit es el que ha invertido su estado. A continuación se dan algunos ejemplos que muestran cómo se pueden localizar los bits alterados:

En el caso que exista más de un error en el bloque de información se llegan a producir varias situaciones que pueden llevar a la "corrección" de un bit no alterado (Ej: si cambian los bits 1 y 2 llevan a la corrección del bit sano 3), entre muchas otras situaciones.

Una variante del código Hamming es adicionarle 1 bit de paridad global. De esta forma es posible tener la seguridad de detección de 2 errores, manteniendo la capacidad de corrección si se produce sólo 1 error.

Desventajas del código Hamming

La cantidad de bits de paridad empleados en la transmisión de la información le restan eficiencia al proceso. Se define la eficiencia de transmisión con la siguiente fórmula:

Suponiendo que se desea transmitir bloques de 8 bits de información, se necesitan 4 bits de paridad para ello, con lo que se tiene un total de 12 bits. La eficiencia sería:

La eficiencia de este tipo de transmisión resulta de 66.66% debida solamente al plan de codificación. Además, dependiendo del método de transmisión puede decaer todavía más.

Distancia de Hamming.

       La primera subdivisión que se efectúa entre códigos es la siguiente. 

• códigos de bloque: la longitud de sus palabras es constante. Son los más utilizados, y para entenderlos resulta fundamental el concepto de distancia.
• códigos sin bloque: la longitud es variable.

       La distancia de Hamming entre dos palabras es el número de bits en que difieren una de la otra. Por ejemplo: 
 

       El peso de una palabra se define como el número de 1s que tiene. Utilizando este concepto podemos decir que la distancia entre dos palabras como el peso de la suma en módulo 2 del peso de las mismas. 
 
 

       Dos palabras serán tanto más fáciles de distinguir cuanto mayor sea su distancia Hamming, ya que si la distancia es d será necesario que se produzcan d errores para que una palabra pase a ser la otra. De este análisis se desprende que la eficacia de un código será función de su distancia Hamming, que se define como la mínima distancia que puede encontrarse entre dos palabras que pertenezcan a ese código. En general: 

• Un código de distancia mínima de Hamming d será capaz de detectar d-1 errores.
• Un código de distancia mínima de Hamming d será capaz de corregir (d-1)/2 errores.
  Un código que corrija t errores y detecte d (d>t) debe tener una distancia mínima igual a dm, siendo dm = t + d +1.

Códigos de Hamming.

Son un subconjunto de los códigos de control de paridad. En ellos se disponen los dígitos de paridad de tal manera que localicen la presencia de errores dentro del mensaje. Estos códigos tienen como muy poco distancia mínima 3. 

Supongamos palabras de L dígitos. Para detectar un error en una de los L bits, o la ausencia de error, necesitaremos al menos R de esos L bits,

cumpliendo la relación: 

de donde se deduce que el código Hamming más sencillo tendrá 2 bits de paridad y 1 de información. A los códigos que cumplen la relación anterior se le denomina código óptimo, en el sentido en que contienen el número máximo posible de bits de información, para una longitud de palabra L y una distancia mínima determinada (en nuestro caso 3). 

Las principales reglas relativas al control de paridad en los códigos de Hamming son: 

• Dos dígitos no pueden controlar la paridad de un mismo conjunto de dígitos de información.
• No se puede incluir en el conjunto de dígitos controlado por uno, otros dígitos de paridad.
• Un error en un bit de información debe afectar a dos o más bits de paridad.

Veamos un ejemplo: 

            p = 3 bits de paridad: p0, p1, p2. 
            L = 7. 
            i = 7 -3 = 4 bits de información: i0, i1, i2, i3. 

     L = i0 i1 i2 i3 p0 p1 p2. 
 

      Se obtienen las ecuaciones: 
 

      de manera que si se recibe una palabra se comprueban las tres ecuaciones, y, en función de las que no se cumplen, se detectará la situación de error o la ausencia. Así por ejemplo, si no se verifican la primera y la tercera, el error estará en i2, que es el único que no interviene en la segunda pero sí en las otras dos. 

       La probabilidad de no detectar error en este código depende de como se utilice. Si se utiliza como corrector existirá la probabilidad de que existan al menos dos errores (es decir, el código sólo puede corregir uno, si hay más no son corregibles), en un canal BSC con probabilidad de error p: 

       Si se utiliza como corrector, la probabilidad de no detección será la de que al menos haya tres errores, es decir: 

       Sin embargo, si una palabra contiene más errores de los que es capaz de detectar un código el decodificador entrega una palabra errónea. Debido a esto se utilizan muchas veces códigos con función doble: primero detectan los errores, después tratan de corregirlos, y si no es posible solucionar todos se pide la retransmisión.