Corrección de errores con código Hamming explicada (con matemáticas)

Codifica Hamming(7,4), calcula un síndrome, corrige cada posición de un solo bit, amplíalo a SECDED y verifica el decodificador sin exagerar sus límites.

Denny

7 de mayo de 20269 min de lectura

Chalkboard feature illustration for “Corrección de errores con código Hamming explicada (con matemáticas)”

En resumen: Hamming(7,4) asigna cuatro bits de datos a siete posiciones. Tres comprobaciones de paridad dan a cada posición una columna única de tres bits distinta de cero, de modo que un bit invertido produce un síndrome igual al índice binario de esa posición. El decodificador puede invertirlo. El Hamming(7,4) simple no puede distinguir un error de dos bits de determinados errores de un bit; un bit de paridad global lo extiende a SECDED bajo el límite de errores supuesto.

Un bit de paridad puede informar de que ha cambiado un número impar de posiciones, pero una sola comprobación no puede identificar cuál. La construcción de Hamming utiliza varias comprobaciones de paridad superpuestas. El patrón de comprobaciones que fallan —el síndrome— actúa como una dirección.

Esta idea es potente porque el codificador, el comprobador y el corrector se pueden construir con redes XOR y lógica de decodificación. También tiene un límite estricto: la regla de corrección conocida presupone como máximo un error en el bloque protegido, salvo que un código extendido añada otra comprobación.

Colocación de los bits

Numera las posiciones de la palabra de código a partir de 1. Las potencias de dos contienen paridad:

Posición	1	2	3	4	5	6	7
Función	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Índice binario	001	010	011	100	101	110	111

Cada comprobación de paridad corresponde a un bit de la posición binaria:

$P_1$ cubre las posiciones cuyo índice tiene activado el bit 0: 1, 3, 5, 7.
$P_2$ cubre las posiciones cuyo índice tiene activado el bit 1: 2, 3, 6, 7.
$P_4$ cubre las posiciones cuyo índice tiene activado el bit 2: 4, 5, 6, 7.

Cada posición tiene un patrón único de pertenencia distinto de cero. La posición 5, por ejemplo, pertenece a las comprobaciones 1 y 4 porque $5=101_2$ .

Esta convención basada en uno es práctica, no mística: las columnas de la matriz de comprobación de paridad son simplemente las etiquetas binarias del 1 al 7.

Codificación con paridad par

Elige cada bit de paridad de modo que la XOR de su conjunto completo de cobertura sea cero:

P_1=D_1\oplus D_2\oplus D_4

P_2=D_1\oplus D_3\oplus D_4

P_4=D_2\oplus D_3\oplus D_4

Estas ecuaciones hacen que el código sea sistemático: los datos originales aparecen sin cambios en las posiciones 3, 5, 6 y 7, mientras que la paridad ocupa las posiciones restantes.

Podría utilizarse paridad impar con cambios coherentes en los valores de comprobación esperados. La paridad par mantiene especialmente directa la forma de álgebra lineal porque toda palabra de código válida tiene un síndrome cero.

Codificación resuelta: datos 1011

Asigna:

D_1=1,\quad D_2=0,\quad D_3=1,\quad D_4=1

Entonces:

P_1=1\oplus0\oplus1=0

P_2=1\oplus1\oplus1=1

P_4=0\oplus1\oplus1=0

Coloca esos valores en las siete posiciones:

Posición	1	2	3	4	5	6	7
Función	$P_1$	$P_2$	$D_1$	$P_4$	$D_2$	$D_3$	$D_4$
Bit	0	1	1	0	0	1	1

Leyendo de la posición 1 a la posición 7, la palabra de código es:

Algunos textos imprimen las palabras de código en la dirección visual opuesta. La aritmética sigue siendo correcta si la convención de posiciones se declara y se usa de forma coherente.

Cálculo del síndrome

Sean las posiciones recibidas $R_1$ hasta $R_7$ . Vuelve a calcular las comprobaciones de paridad completas:

S_1=R_1\oplus R_3\oplus R_5\oplus R_7

S_2=R_2\oplus R_3\oplus R_6\oplus R_7

S_4=R_4\oplus R_5\oplus R_6\oplus R_7

Interpreta el síndrome como:

S=(S_4S_2S_1)_2

Para una palabra de código válida sin cambios, $S=000$ . Si se invierte exactamente una posición $i$ , se conmuta cada comprobación que cubre $i$ . El síndrome resultante es la columna binaria asignada a la posición $i$ .

Corrección de una inversión en la posición 5

Invierte la posición 5 en el ejemplo codificado:

sent:     0 1 1 0 0 1 1
received: 0 1 1 0 1 1 1
position: 1 2 3 4 5 6 7

Ahora:

S_1=0\oplus1\oplus1\oplus1=1

S_2=1\oplus1\oplus1\oplus1=0

S_4=0\oplus1\oplus1\oplus1=1

Por tanto:

S_4S_2S_1=101_2=5

Bajo la hipótesis de un solo error, invierte la posición recibida 5. La palabra corregida vuelve a ser 0110011, y las posiciones 3, 5, 6 y 7 proporcionan los datos 1011.

Una inversión en una posición de paridad funciona del mismo modo. Si cambia la posición 2, el síndrome es 010 y el corrector invierte la posición 2.

Vista matricial

Usando el vector de palabra de código

\mathbf r=[R_1\ R_2\ R_3\ R_4\ R_5\ R_6\ R_7]^T

una matriz de comprobación de paridad es:

H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

El síndrome es:

\mathbf s=H\mathbf r\pmod 2

La columna $i$ de H es la representación binaria de $i$ , ordenada como $(S_1,S_2,S_4)^T$ . Por tanto, un vector de error de un solo bit con su 1 en la posición $i$ devuelve exactamente la columna $i$ .

Esta formulación escala con más limpieza que memorizar círculos superpuestos. También hace explícita la linealidad: aplicar XOR a dos palabras de código válidas produce otra palabra de código válida.

Por qué Hamming simple no puede corregir con seguridad dos errores

Hamming(7,4) tiene distancia de Hamming mínima:

d_{\min}=3

Un código con distancia mínima $d_{\min}$ puede:

detectar hasta $d_{\min}-1$ errores arbitrarios si solo decide entre válido e inválido; o
corregir hasta $\left\lfloor(d_{\min}-1)/2\right\rfloor$ errores eligiendo la palabra de código más cercana.

Por ello, Hamming(7,4) puede corregir un error. También puede detectar una corrupción de dos bits como «no es una palabra de código» si no se intenta corregir. Sin embargo, su síndrome de tres bits distinto de cero no puede indicar si proviene de un error o de un par concreto de errores.

Si un decodificador estándar de un solo error observa un error de dos bits, la XOR de las columnas de las dos posiciones con error equivale a una tercera columna distinta de cero. El decodificador invertirá esa tercera posición y creará una diferencia de tres bits con respecto a la palabra de código transmitida. Esto es una corrección errónea, no corrección de dos errores.

Declara siempre el modelo de error supuesto por el decodificador. «El síndrome no es cero, así que invierte esa posición» solo es válido cuando el sistema ha establecido que como máximo una posición protegida es errónea.

Hamming extendido y SECDED

Añade un bit de paridad global $P_0$ a la palabra Hamming de siete bits. El código extendido de ocho bits tiene $d_{\min}=4$ y permite corrección de un solo error y detección de dos errores (SECDED), suponiendo que no haya más de dos errores en una palabra de código.

Calcula:

el síndrome original de tres bits S a partir de las posiciones 1–7;
una comprobación de paridad global P sobre las ocho posiciones recibidas.

Para paridad global par:

Síndrome S	Comprobación global P	Interpretación con 0–2 errores	Acción
000	0	sin error	aceptar
distinto de cero	1	un error en las posiciones 1–7	corregir la posición S
000	1	error en la posición de paridad global	corregir o informar de error de bit de paridad
distinto de cero	0	dos errores	informar de que no se puede corregir; no corregir como error único

La salvedad importa. Tres o más errores pueden imitar otra fila de la tabla. SECDED no es un detector de errores ilimitado.

Los sistemas reales de memoria y comunicaciones pueden usar códigos Hamming acortados, entrelazado, códigos orientados a símbolos, códigos BCH o Reed–Solomon, códigos de comprobación de paridad de baja densidad, códigos producto o esquemas propietarios. No infieras la capacidad ECC de un sistema solo a partir de los anchos visibles de datos y bits de comprobación.

Dimensionamiento general del código Hamming

Para $m$ bits de datos y $r$ bits de paridad Hamming, debe haber suficientes patrones de síndrome para cada posición de la palabra de código más el caso sin error:

2^r\ge m+r+1

La familia Hamming binaria de longitud completa utiliza:

n=2^r-1

k=n-r=2^r-r-1

Bits de paridad r	Longitud de código n	Bits de datos k	Código completo
3	7	4	Hamming(7,4)
4	15	11	Hamming(15,11)
5	31	26	Hamming(31,26)
6	63	57	Hamming(63,57)

Las variantes acortadas omiten posiciones de datos seleccionadas mientras conservan la estructura de comprobación. Las variantes extendidas añaden el bit de paridad global y aumentan la distancia de 3 a 4.

La sobrecarga debe indicar su denominador. Hamming(7,4) añade 3 bits de comprobación por cada 4 bits de datos: una sobrecarga del 75% respecto a la carga útil, o 3/7 de la palabra transmitida. Hamming(63,57) añade 6/57, aproximadamente un 10.5% respecto a la carga útil, y los bits de comprobación ocupan 6/63, aproximadamente un 9.5% de la palabra de código.

Arquitectura de hardware

Una implementación sistemática directa tiene cuatro etapas:

data ─▶ parity generator ─▶ codeword
                              │
received word ─▶ check matrix ─▶ syndrome
                                      │
                       syndrome decoder ─▶ one-hot flip mask
received word ─────────────────────────── XOR ─▶ corrected word ─▶ extract data

Para Hamming(7,4):

el codificador calcula tres ecuaciones de paridad;
el comprobador calcula tres ecuaciones de síndrome;
un decodificador de 3 a 8 puede formar una máscara de posición one-hot, donde la salida 0 significa que no hay corrección;
siete puertas XOR aplican esa máscara;
el cableado extrae las posiciones 3, 5, 6 y 7.

El número exacto de puertas y la temporización dependen de la factorización del árbol XOR, de los términos compartidos, de las bibliotecas de celdas o del mapeo a FPGA. Un decodificador ancho puede canalizar el cálculo del síndrome y la corrección. Si un registro de banderas o estado informa «corregido» y «no corregible», alinea esas señales con la etapa de canalización de datos correspondiente.

Plan de verificación

Para el código de siete bits:

Codifica las 16 entradas de datos posibles.
Confirma que cada palabra codificada tiene síndrome cero.
Para cada palabra de código, invierte individualmente cada una de las siete posiciones.
Confirma que el síndrome es igual a la posición invertida.
Aplica la corrección y confirma que los 16×7 casos recuperan los datos originales.
Inyecta errores representativos de dos bits y demuestra por qué un decodificador simple de un solo error corrige erróneamente.

Para la versión extendida de ocho bits:

Repite cada prueba de posición individual, incluida la posición de paridad global.
Prueba los $\binom82=28$ patrones de dos posiciones para cada palabra de datos.
Confirma que cada par se informa como no corregible y que ninguno se corrige como error único.
Añade aserciones que habiliten la corrección solo para S != 0 y discrepancia de paridad global.

La simulación funcional demuestra la tabla de verdad implementada para los patrones de bits probados o enumerados exhaustivamente. No proporciona una tasa física de errores blandos, no establece la independencia de los fallos ni sustituye el análisis de fiabilidad a nivel de sistema.

Errores de diseño habituales

Numerar las posiciones desde cero y seguir interpretando el síndrome como una dirección basada en uno.
Imprimir la palabra en orden inverso sin documentar la convención.
Mezclar codificación de paridad par con comprobación de paridad impar.
Corregir cada síndrome distinto de cero sin acotar el número de errores.
Tratar SECDED como detección de todos los errores de peso tres o superior.
Olvidar que los bits de comprobación y el bit de paridad global pueden fallar.
Comparar «porcentajes de sobrecarga» que utilizan denominadores distintos.
Suponer que todos los productos etiquetados como ECC implementan el mismo código.

Hamming(7,4) es valioso porque todo el mecanismo es visible: las columnas únicas de comprobación de paridad convierten un fallo de un bit en una dirección. Una vez que esto está claro, la paridad simple parece una matriz de comprobación de una fila, mientras que los códigos de bloque más robustos se convierten en versiones mayores de la misma idea central: redundancia estructurada adaptada a un modelo de fallos explícito.

Referencia

R. W. Hamming, «Error Detecting and Error Correcting Codes», Bell System Technical Journal, 1950