Código de Hamming: corregir un bit localizando su posición

Pulsa Una inversión. El bit 5 se invierte en el canal, y los círculos 1 y 4 contienen ahora un número impar de unos mientras que el círculo 2 sigue siendo par: 1 + 4 = 5. No se ha elegido un caso especial para que funcione. El círculo k comprueba exactamente las posiciones cuyo número binario contiene k. Por eso, un bit erróneo en la posición i altera justo los círculos cuya suma es i: la posición de un bit en el diagrama es también su dirección. En 1950, Hamming buscaba precisamente esto, un «número de comprobación» que indicase la posición de cualquier error aislado, reservando el cero para la ausencia de errores. Tres comprobaciones ofrecen ocho resultados y una palabra de siete bits necesita exactamente ocho: sus siete posiciones y «sin error». No sobra ninguno. De las 128 palabras de siete bits, 16 son palabras de código; las otras 112 se obtienen invirtiendo un solo bit de una de ellas, y cada una dista una inversión de exactamente una palabra de código. La tabla situada bajo el gráfico decodifica correctamente las 112. Que los bits de paridad ocupen las posiciones 1, 2 y 4 es menos arbitrario de lo que parece. Esas posiciones tienen un único 1 en binario, por lo que cada bit de paridad pertenece a un solo círculo y puede fijarse mediante su propia comprobación. Esa fue la razón que dio Hamming.

Pulsa Dos inversiones. Los bits 3 y 5 cambian. El círculo 1 contiene ambos, sufre dos alteraciones y permanece par; los círculos 2 y 4 se vuelven impares, de modo que el síndrome indica 6, una posición perfectamente válida. El decodificador invierte el bit 6, que era correcto. Al llegar había dos bits de datos erróneos; después de la corrección hay tres. La cuadrícula muestra que todos los pares producen el mismo resultado: los 21 y, por tanto, las 336 inversiones dobles entre las 16 palabras de datos entregan información errónea sin aviso. Pulsa Solo bits de paridad: las posiciones 1 y 2 no contienen datos, los datos han llegado intactos y el síndrome 3 lleva al decodificador a estropear d₁. Pulsa ahora Extendido, dos cambios. El octavo bit hace par el conjunto de los ocho, así que una inversión siempre vuelve impar la paridad global y dos inversiones la dejan par. Al encontrar una paridad global par junto a un síndrome distinto de cero, el decodificador señala la palabra y no toca nada. Así ocurre con las 448 inversiones dobles. No puede repararlas, pues 3 y 5 producen el síndrome 6, igual que 1 y 7. Hamming partió precisamente de la necesidad de señalar el error. Su artículo de 1950 comienza con los dos ordenadores de relés que Bell Labs construyó para el campo de pruebas de Aberdeen. No dejaban pasar inadvertido ningún fallo de relé, unos dos o tres diarios entre 8.900 relés durante la primera época, pero cuando funcionaban sin supervisión por las noches y los fines de semana se detenían con frecuencia.

Repetir cada bit dos veces y usar el código extendido exige en ambos casos ocho bits para transmitir cuatro. Si las dos copias no coinciden, el receptor sabe que algo ha fallado, pero no cuál de ellas es correcta; solo puede señalar el bloque. Con p = 0,01, esto sucede en 7,69×10⁻² de los bloques, mientras que 3,77×10⁻⁴ pasan con errores cuando se invierten a la vez las dos copias de un bit. El código de Hamming extendido corrige cualquier inversión aislada, señala 2,64×10⁻³ y deja pasar 5,34×10⁻⁵: con el mismo presupuesto, produce 29 veces menos avisos y 7 veces menos bloques erróneos. Las líneas discontinuas y continuas muestran que aventaja a la repetición en ambos aspectos hasta que p supera 0,066, lo que corresponde a un canal que invierte un bit de cada quince. Repetir cada bit tres veces sí supera al código de siete bits por bloque para todos los valores de p del control: aquí, 1,19×10⁻³ frente a 2,03×10⁻³. Sin embargo, requiere 12 bits en lugar de 7; por eso la comparación justa es la de ocho.