Un código Hamming es un tipo particular de código de corrección de errores (ECC) que permite corregir los errores de un solo bit en las palabras de código. Estos códigos se utilizan en sistemas de transmisión o almacenamiento de datos en los que no es posible utilizar mecanismos de reintento para recuperar los datos cuando se detectan errores. Este tipo de recuperación de errores también se conoce como corrección de errores hacia adelante (FEC).
Construir un código Hamming para proteger, por ejemplo, una palabra de datos de 4 bits
Los códigos Hamming son relativamente fáciles de construir porque se basan en la lógica de la paridad. Cada bit de control es un bit de paridad para un subconjunto particular de los bits de datos, y están dispuestos de manera que el patrón de errores de paridad indica directamente la posición del error de bit.
Se necesitan tres bits de control para proteger cuatro bits de datos (la razón de esto se verá en breve), lo que da un total de 7 bits en la palabra codificada. Si se numeran las posiciones de los bits de una palabra de 8 bits en binario, se ve que hay una posición que no tiene ningún "1" en su columna, tres posiciones que tienen un solo "1" cada una, y cuatro posiciones que tienen dos o más "1".
Si los cuatro bits de datos se llaman A, B, C y D, y nuestros tres bits de comprobación son X, Y y Z, los colocamos en las columnas de forma que los bits de comprobación estén en las columnas con un "1" y los bits de datos estén en las columnas con más de un "1". El bit en la posición 0 no se utiliza.
Bit position: 7 6 5 4 3 2 1 0
in binary: 1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0
Bit: A B C X D Y Z -
El bit de comprobación X se activa o desactiva para que todos los bits con un "1" en la fila superior -A, B C y X- tengan paridad. Del mismo modo, el bit de control Y es el bit de paridad para todos los bits con un "1" en la segunda fila (A, B y D), y el bit de control Z es el bit de paridad para todos los bits con un "1" en la tercera fila (A, C y D).
Ahora se transmiten (o almacenan) los siete bits -la palabra clave-, normalmente reordenados para que los bits de datos aparezcan en su secuencia original: A B C D X Y Z. Cuando se reciben (o recuperan) más tarde, los bits de datos se someten al mismo proceso de codificación que antes, produciendo tres nuevos bits de control X', Y' y Z'. Si los nuevos bits de comprobación se XOR con los bits de comprobación recibidos, ocurre algo interesante. Si no hay ningún error en los bits recibidos, el resultado del XOR es todo ceros. Pero si hay un solo error de bit en cualquiera de los siete bits recibidos, el resultado del XOR es un número de tres bits distinto de cero llamado "síndrome" que indica directamente la posición del error de bit tal y como se define en la tabla anterior. Si se invierte el bit en esta posición, se reconstruye perfectamente la codificación original de 7 bits.
Un par de ejemplos lo ilustran. Supongamos que los bits de datos son todos cero, lo que significa que todos los bits de control son también cero. Si el bit "B" está activado en la palabra recibida, entonces los bits de comprobación recalculados X'Y'Z' (y el síndrome) serán 110, que es la posición del bit para B. Si el bit "Y" está activado en la palabra recibida, entonces los bits de comprobación recalculados serán "000", y el síndrome será "010", que es la posición del bit para Y.
Los códigos Hamming se vuelven más eficientes con palabras de código más grandes. Básicamente, se necesitan suficientes bits de control para enumerar todos los bits de datos más los bits de control más uno. Por lo tanto, cuatro bits de control pueden proteger hasta 11 bits de datos, cinco bits de control pueden proteger hasta 26 bits de datos, y así sucesivamente. Finalmente, se llega al punto de que si se tienen 8 bytes de datos (64 bits) con un bit de paridad en cada byte, se tienen suficientes bits de paridad para hacer ECC en los 64 bits de datos.
Códigos Hamming diferentes (pero equivalentes)
Dado un número específico N de bits de control, hay 2 N códigos Hamming equivalentes que pueden construirse eligiendo arbitrariamente que cada bit de comprobación tenga paridad "par" o "impar" dentro de su grupo de bits de datos. Siempre que el codificador y el descodificador utilicen las mismas definiciones para los bits de control, se conservan todas las propiedades del código Hamming.
A veces es útil definir los bits de comprobación para que una palabra codificada con todos los ceros o todos los tonos se detecte siempre como un error.
¿Qué ocurre cuando se invierten varios bits en una palabra de código Hamming?
Los errores de bits múltiples en un código Hamming causan problemas. Los errores de dos bits siempre se detectarán como un error, pero el bit equivocado será volteado por la lógica de corrección, resultando en un galimatías. Si hay más de dos bits de error, la codificación recibida puede parecer válida (pero diferente de la original), lo que significa que el error puede ser detectado o no.
En cualquier caso, la lógica de corrección de errores no puede distinguir entre errores de un solo bit y errores de varios bits, por lo que no se puede confiar en la salida corregida.
Ampliación de un código Hamming para detectar errores de doble bit
Cualquier código Hamming de corrección de un solo error puede ampliarse para detectar de forma fiable los errores de doble bit añadiendo un bit de paridad más sobre toda la palabra codificada. Este tipo de código se denomina código SECDED (single-error correcting, double-error detecting). Siempre puede distinguir un error de doble bit de un error de un solo bit, y detecta más tipos de errores de múltiples bits que un código Hamming desnudo.
Funciona así: Todas las palabras de código válidas tienen (como mínimo) una distancia Hamming de 3. La "distancia Hamming" entre dos palabras se define como el número de bits en posiciones correspondientes que son diferentes. Cualquier error de un solo bit está a una distancia de una palabra válida, y el algoritmo de corrección convierte la palabra recibida en la válida más cercana.
Si se produce un doble error, la paridad de la palabra no se ve afectada, pero el algoritmo de corrección sigue corrigiendo la palabra recibida, que está a distancia dos de la palabra válida original, pero a distancia uno de alguna otra palabra válida (pero errónea). Lo hace volteando un bit, que puede ser o no uno de los bits erróneos. Ahora la palabra tiene uno o tres bits volteados, y el doble error original es ahora detectado por el verificador de paridad.
Tenga en cuenta que esto funciona incluso cuando el propio bit de paridad está involucrado en un error de uno o dos bits. No es difícil calcular todas las combinaciones.
