Corrección de errores de bit único y detección de errores de bit doble

Un código de Hamming es un tipo particular de código de corrección de errores (ECC) que permite corregir errores de un solo bit en palabras de código. Dichos códigos se utilizan en sistemas de transmisión o almacenamiento de datos en los que no es factible 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).

Construyendo un código de Hamming para proteger, digamos, una palabra de datos de 4 bits

Los códigos de Hamming son relativamente fáciles de construir porque se basan en la lógica de paridad. Cada bit de verificación es un bit de paridad para un subconjunto particular de bits de datos, y están dispuestos de modo que el patrón de errores de paridad indique directamente la posición del bit de error.

Se necesitan tres bits de verificación para proteger cuatro bits de datos (la razón de esto se hará evidente en breve), dando un total de 7 bits en la palabra codificada. Si numera las posiciones de bits de una palabra de 8 bits en binario, verá que hay una posición que no tiene "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 control son X, Y y Z, los colocamos en las columnas de manera que los bits de control estén en las columnas con un "1" y los datos los bits 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 control X se activa o desactiva para que todos los bits con un "1" en la fila superior (A, BC y X) tengan paridad uniforme. De manera similar, 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 los siete bits, la palabra clave, se transmiten (o almacenan), por lo general se reordenan para que los bits de datos aparezcan en su secuencia original: ABCDXY Z. Cuando se reciben (o recuperan) más tarde, los bits de datos pasan por el mismo proceso de codificación como antes, produciendo tres nuevos bits de control X', Y' y Z'. Si los nuevos bits de verificación se someten a XOR con los bits de verificación recibidos, ocurre algo interesante. Si no hay 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 como se define en la tabla anterior. Si se invierte el bit en esta posición, la palabra clave original de 7 bits se reconstruye perfectamente.

Un par de ejemplos ilustrarán esto. Supongamos que todos los bits de datos son cero, lo que también significa que todos los bits de verificación también son cero. Si se establece el bit "B" en la palabra recibida, entonces los bits de verificación recalculados X'Y'Z' (y el síndrome) serán 110, que es la posición de bit para B. Si se establece el bit "Y" en la palabra recibida palabra, entonces los bits de verificación recalculados serán "000" y el síndrome será "010", que es la posición del bit para Y.

Los códigos de Hamming se vuelven más eficientes con palabras de código más grandes. Básicamente, necesita suficientes bits de verificación para enumerar todos los bits de datos más los bits de verificación 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. Eventualmente, llega al punto en que si tiene 8 bytes de datos (64 bits) con un bit de paridad en cada byte, tiene suficientes bits de paridad para hacer ECC en los 64 bits de datos.

Códigos de Hamming diferentes (pero equivalentes)

Dado un número específico N de bits de verificación, hay 2 ^N códigos de Hamming equivalentes que se pueden construir eligiendo arbitrariamente cada bit de verificación para que tenga paridad "par" o "impar" dentro de su grupo de bits de datos. Siempre que el codificador y el decodificador 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 verificación para que una palabra codificada de todos ceros o todos unos siempre se detecte como un error.

¿Qué sucede cuando se invierten varios bits en una palabra clave de 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 la lógica de corrección cambiará el bit incorrecto, lo que dará como resultado un galimatías. Si hay más de dos bits erróneos, la palabra de código recibida puede parecer válida (pero diferente de la original), lo que significa que el error puede detectarse o no.

En cualquier caso, la lógica de corrección de errores no puede diferenciar entre errores de bit único y errores de bit múltiple, por lo que no se puede confiar en la salida corregida.

Ampliación de un código de Hamming para detectar errores de doble bit

Cualquier código Hamming de corrección de un solo error se puede ampliar para detectar de forma fiable 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 (corrección de un solo error, detección de doble error). 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 de Hamming simple.

Funciona así: todas las palabras de código válidas están separadas (como mínimo) por una distancia de Hamming de 3. La "distancia de 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 a la válida más cercana.

Si ocurre un doble error, la paridad de la palabra no se ve afectada, pero el algoritmo de corrección aún corrige la palabra recibida, que está a dos distancias de la palabra válida original, pero a una distancia de alguna otra palabra válida (pero incorrecta). Lo hace cambiando un bit, que puede ser o no uno de los bits erróneos. Ahora la palabra tiene uno o tres bits invertidos, y el verificador de paridad ahora detecta el doble error original.

Tenga en cuenta que esto funciona incluso cuando el bit de paridad en sí está involucrado en un error de un solo bit o de doble bit. No es difícil resolver todas las combinaciones.