Código Hamming: definición, ejemplos y corrección de errores

Descubre el Código Hamming: definición clara, ejemplos y guía práctica para detectar y corregir errores en comunicaciones y señales digitales.

Un código Hamming es un código de bloques con capacidad de corrección de errores. Debe su nombre a Richard Hamming, que lo desarrolló en la década de 1950 cuando trabajaba con máquinas que empleaban relés y leían datos desde tarjetas perforadas. En aquel contexto, los errores de lectura eran frecuentes y se necesitaban métodos automáticos para detectarlos y, si era posible, corregirlos.

Qué hacen y dónde se usan

Los códigos Hamming se utilizan ampliamente en el procesamiento de señales digitales y en las telecomunicaciones, así como en memoria con corrección de errores (por ejemplo, RAM con ECC), almacenamiento y sistemas embebidos. Su objetivo es detectar errores de transmisión o de almacenamiento y, en su forma básica, corregir errores de un solo bit dentro de una palabra de código.

Concepto básico: bits de paridad y redundancia

Un código Hamming añade varios bits de paridad a los bits de datos. Un bit de paridad indica si el número de unos en un grupo determinado de bits es par o impar (normalmente se usa paridad par). En un código Hamming cada bit de datos está "cubierto" por varios bits de paridad; esa redundancia permite localizar el bit erróneo cuando sólo ha cambiado uno.

Para una cantidad k de bits de paridad, la longitud total de cada palabra de código en la forma básica cumple la relación 2^k − 1, porque con k bits de paridad se pueden controlar hasta 2^k − 1 posiciones distintas (datos + paridad). En el texto original aparece la misma expresión matemática representada de esta manera: 2 k - 1 {pantalla 2^{k}-1}. Por ejemplo, con k = 3 bits de paridad la longitud total es 2³ − 1 = 7; quedan 4 bits de datos útiles, y ese código se denota como (7,4).

Cómo se colocan los bits (regla práctica)

• Las posiciones que son potencias de dos (1, 2, 4, 8, ...) se reservan para los bits de paridad.
• Las demás posiciones contienen los bits de datos.
• Cada bit de paridad comprueba un conjunto específico de posiciones; en particular, el bit de paridad en la posición 2^i cubre todas las posiciones cuyo (i+1)-ésimo bit en su número binario es 1.

Ejemplo concreto: el código (7,4)

En (7,4) las posiciones son 1..7. Las posiciones de paridad son 1, 2 y 4; las posiciones de datos son 3, 5, 6 y 7. Denotando p1, p2 y p4 a las paridades y d3, d5, d6, d7 a los datos, la disposición es:

[p1, p2, d3, p4, d5, d6, d7]

Los conjuntos verificados por cada paridad (si usamos paridad par) son:

• p1 comprueba posiciones 1, 3, 5, 7 (bit menos significativo = 1)
• p2 comprueba posiciones 2, 3, 6, 7 (segundo bit = 1)
• p4 comprueba posiciones 4, 5, 6, 7 (tercer bit = 1)

Codificación: ejemplo numérico

Tomemos datos d3=1, d5=0, d6=1, d7=1. Calculamos las paridades para paridad par:

• p1 = paridad de (pos.3,5,7) = 1 + 0 + 1 = 2 → paridad par → p1 = 0
• p2 = paridad de (pos.3,6,7) = 1 + 1 + 1 = 3 → impar → p2 = 1
• p4 = paridad de (pos.5,6,7) = 0 + 1 + 1 = 2 → paridad par → p4 = 0

La palabra de código resultante es: [0, 1, 1, 0, 0, 1, 1] → 0110011.

Detección y corrección (síndrome)

Al recibir una palabra se recalculan las mismas paridades y se comparan con los bits de paridad recibidos. La diferencia se codifica en el síndrome, que es un número binario formado por los resultados de las comprobaciones (s4 s2 s1). Ese número indica la posición del bit erróneo (si es distinto de cero).

Ejemplo (continuación): supongamos que durante la transmisión se invierte el bit en la posición 6. El receptor recibe 0110001. Recalculamos:

• Chequeo p1 (pos.1,3,5,7): 1 + 0 + 1 = 2 → s1 = 0
• Chequeo p2 (pos.2,3,6,7): 1 + 1 + 0 + 1 = 3 → s2 = 1
• Chequeo p4 (pos.4,5,6,7): 0 + 0 + 0 + 1 = 1 → s4 = 1

El síndrome s4 s2 s1 = 110 (binario) = 6 (decimal), por tanto indica que el error está en la posición 6. Bastaría invertir ese bit para corregir la palabra.

Alcance y limitaciones

• El Hamming básico corrige errores de un solo bit (Single-Error Correction, SEC) y detecta (pero no siempre identifica) algunos errores de más bits.
• Con una paridad adicional global se obtiene la variante SECDED (Single-Error Correction, Double-Error Detection), que corrige errores de un bit y detecta errores de dos bits.
• Los códigos Hamming no son eficaces para ráfagas largas de errores (burst errors) sin modificaciones o esquemas adicionales.

Variantes y usos prácticos

Además del (7,4) existen familias de Hamming para distintos tamaños (p. ej. (15,11), (31,26)...) según la relación 2^k−1. Son muy usados en memorias con ECC, enlaces satelitales, controladores de disco y en sistemas embebidos donde la sobrecarga de bits de paridad es tolerable y la corrección de errores simple es deseable.

Ejemplo mínimo: (3,1)

El código Hamming más corto posible es (3,1): 2 bits de paridad y 1 bit de datos. Sus palabras válidas (con paridad par) son 000 y 111. Si durante la recepción aparecen 001, 010 o 100, esos patrones se interpretan como errores cuyo bit erróneo se corrige a volver a 000. De forma similar, 011, 101 y 110 se corregirán a 111.

Resumen

Los códigos Hamming son una solución sencilla y eficiente para corregir errores de un bit y detectar errores simples. Su implementación requiere colocar bits de paridad en posiciones concretas, calcular conjuntos de paridad y, en recepción, interpretar el síndrome para localizar errores. Para detección adicional de errores múltiples se emplean variantes como SECDED u otros códigos más fuertes cuando la aplicación lo exige.

Preguntas y respuestas

P: ¿Qué es un código Hamming?

P: ¿Cómo funciona un código Hamming?

P: ¿Quién inventó el Código Hamming?

P: ¿Para qué utilizó Richard Hamming su invento?

P: ¿Qué se escribe como (N,n) cuando se habla de un código hamming?

P: ¿Cuál es el código hamming más corto posible?

Búsqueda por letra