Código Hamming

[gL.edu] Este artículo recoge contribuciones de Irene Salinero, Daniel Gracia Garallar, José María Díaz Nafría, elaboradas en el contexto de la Clarificación conceptual en torno a la "teoría de la información", bajo la supervisión de José María Díaz Nafría.

Un código Hamming es un tipo de código de bloque utilizado para detectar y corregir errores en la transmisión de datos, desarrollado por Richard Hamming en 1950 y es una de las primeras técnicas utilizadas para asegurar la integridad de la información en sistemas de comunicación digital.

Se dice que un código Hamming es un código lineal (concepto al que nos hemos referido al hablar de la codificación de bloque para el control de errores), cíclico y 1-perfecto, lo que implica, (i) que cualquier combinación lineal de palabras del código es también una palabra válida del código y, por otra, (ii) que cualquier rotación de un código válido es otro código válido; (iii) que es posible corregir errores de un bit, con independencia de su posición dentro del bloque de código, y sólo estos (debido a que las esferas de radio 1 centradas en las palabras de código son disjuntas y recubren de forma completa todo el espacio de códigos ${\mathcal {L}}_{n}$).

Dimensiones y estructura del código

Las dimensiones de este código pueden ser ${\mathcal {C}}[n,k]={\mathcal {C}}[2^{m}-1,2^{m}-1-m]\,\ \forall \,m\geq 2\in \mathbb {N}$, pero en cualquier caso, $d_{min}=3\rightarrow e=2;t=1$, lo que implica que según vamos aumentando la dimensión del código, su régimen de codificación va reduciéndose (y por tanto aumenta el rendimiento espectral), a la vez que la capacidad de error se mantiene. Sin embargo,debe tenerse en cuenta que al tratarse de bloques cada vez mayores ese error corregible tiene un peso relativo cada vez menor.

Figura 1: Distribución de los bits de paridad en un código Hamming (Fuente: Invarato, 2016)

Aunque es frecuente recurrir a versiones sistemáticas de los códigos Hamming (v. código sistemático), en las no sistemáticas, se insertan bits adicionales (de paridad) en posiciones específicas dentro de la secuencia de datos. Estos bits se calculan de manera que cada uno verifique la paridad (suma de bits 1 o 0) de ciertos conjuntos de bits en el mensaje, como se ilustra en la figura 1. En dicha figura se observa la distribución de hasta 5 bits de paridad en secciones de código cuyo tamaño se duplica, lo que explica la dimensión del código a la que nos referíamos antes. El código Hamming (7,4) usa 3 bits de paridad, el (15,11) usará 4 bits de paridad... La ilustración, aunque se limite a mostrarnos los bits de paridad hasta el Hamming(31,26), nos de forma inmediate prever cómo será su distribución para códigos de mayor longitud.

Funcionamiento básico del código de Hamming:

• Codificación: Se parte de un mensaje binario original al que se le añaden bits de paridad para formar un código que pueda detectar y corregir errores. Los bits de paridad se calculan de manera que cada uno cubre un conjunto diferente de bits de código, de manera que se garantice la paridad por cada subconjunto de bits de código. , y es la combinación de los bits de paridad la que permite identificar el lugar exacto en el que se ha producido el error dentro del bloque de código y corregirlo (siempre que no se haya producido más de un error de bit dentro del bloque).
• Detección y corrección: Cuando el mensaje codificado se recibe, se verifican los bits de paridad para determinar si hay errores. Si los bits de paridad indican un error, el código de Hamming puede identificar la posición del bit erróneo y corregirlo. Para ello la identificación de defectos de paridad en cada subconjunto de los bloques de código permiten identificar el lugar exacto en el que se ha producido el error dentro del bloque de código y corregirlo (siempre que no se haya producido más de un error de bit dentro del bloque).

Aplicaciones

Un ejemplo práctico de aplicación del código de Hamming podemos encontrarlo en la transmisión de datos en redes de computadoras, como en la comunicación de datos entre dispositivos electrónicos, discos duros o en la memoria RAM de una computadora.

También podemos encontrarla en las memorias RAM con corrección de errores, conocida como ECC RAM (Error-Correcting Code RAM), en la que se emplea códigos de Hamming para detectar y corregir errores de bits en tiempo real. En una computadora, los datos se almacenan y transfieren en forma de bits (0 y 1), y debido a varios factores (ruido electromagnético, radiación cósmica, errores de hardware, etc.), un bit puede cambiar su valor de 0 a 1.