CÓDIGO HAMMING

 En informática, el código de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en solo un bit, pero no pueden corregirlo.

    Si se añaden junto al mensaje más bits detectores-correctores de error y si esos bits se pueden ordenar de modo que diferentes bits de error producen diferentes resultados, entonces los bits erróneos podrían ser identificados. En un conjunto de siete bits, hay solo siete posibles errores de bit, por lo que con tres bits de control de error se podría especificar, además de que ocurrió un error, en qué bit fue.  

 

    Hamming estudió los esquemas de codificación existentes, incluido el de dos entre cinco, y generalizó sus conclusiones. Para empezar, desarrolló una nomenclatura para describir el sistema, incluyendo el número de los bits de datos y el de los bits detectores-correctores de error en un bloque. Por ejemplo, la paridad incluye un solo bit para cualquier palabra de datos, así que las palabras del Código ASCII que son de siete bits, Hamming las describía como un código (8.7), esto es, un total de 8 bits de los cuales 7 son datos. Con base a la anterior repetición, sería un código (3.1), siguiendo la misma lógica. La relación de la información es el segundo número dividido por el primero, por nuestro ejemplo de la repetición, 1/3. 

 

    Hamming también estudió los problemas que surgían al cambiar dos o más bits a la vez y describió esto como "distancia" (ahora llamada distancia de Hamming en su honor). La paridad tiene una distancia de 2, dado que cualquier error en dos bits no será detectado. La repetición (3.1) tiene una distancia de 3, pues son necesarios el cambio simultáneo de tres bits para obtener otra palabra de código. La repetición (4.1) (cada bit se repite cuatro veces) tiene una distancia de 4, así que el cambio de dos bits en el mismo grupo quedará sin definir. 

 

    Hamming estaba interesado en solucionar simultáneamente dos problemas: aumentar la distancia tanto como sea posible, a la vez que se aumentan al máximo los bits de información. Durante los años 40 desarrolló varios esquemas de codificación que mejoraban notablemente los códigos existentes. La clave de todos sus sistemas era intercalar entre los bits de datos los de paridad. 

La expresión que relaciona la distancia mínima, detección y corrección de errores es: M - 1 = D + C para toda C <= D. Donde:

M = Distancia mínima

D = Bits erróneos que se detectan

C = Bits erróneos que se corrigen

La Tabla 1, muestra la relación para diferentes valores de M, D y C: