Código Hamming

En informática, el código de Hamming es un código detector y corrector de errores que lleva el nombre de su inventor, Richard Hamming. En los datos codificados en Hamming se pueden detectar errores en un bit y corregirlos, sin embargo no se distingue entre errores de dos bits y de un bit (para lo que se usa Hamming extendido). Esto representa una mejora respecto a los códigos con bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.


Códigos pre-Hamming

Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, como lo fueron el código linteing, pero ninguno llegó a ser tan eficaz como los de Hamming. A continuación se describen algunos de estos códigos.

Paridad

La paridad consiste en añadir un bit, denominado bit de paridad, que indique si el número de los bits de valor 1 en los datos precedentes es par o impar. Si un solo bit cambiara por error en la transmisión, el mensaje cambiará de paridad y el error se puede detectar (nótese que el bit donde se produzca el error puede ser el mismo bit de paridad). La convención más común es que un valor de paridad 1 indica que hay un número impar de unos en los datos, y un valor de paridad de 0 indica que hay un número par de unos en los datos.

La comprobación de paridad no es muy robusta, dado que si cambia de forma uniforme un número par de bits, el bit de paridad será válido y el error no será detectado. Se utiliza cuando se cumplen simultáneamente dos condiciones: que la probabilidad de que falle un bit es baja y que las fallas de bits son sucesos independientes. De esta forma la probabilidad de que fallen dos (o más) bits es muy baja, por lo que cuando no detecta error es altamente probable que el código sea efectivamente correcto. Cabe destacar que dichas condiciones se ajustan al caso de las memorias de las computadoras modernas pero no ocurre lo mismo con los dispositivos de almacenamiento que guardan la información en forma serial (un bit a continuación de otro) ni con los sistemas de transmisión de datos seriales ya que en estos casos el hecho que falle un bit está vinculado, en forma no despreciable, a la falla de otro adyacente.

Por otro lado, la paridad, aunque puede detectar que hay error, no indica en qué bit se cometió. Los datos se deben desechar por entero y volverse a transmitir. En un medio ruidoso, una transmisión correcta podría tardar mucho tiempo o incluso, en el peor de los casos, no darse nunca. El chequeo de paridad, aunque no es muy bueno, usa un único bit, por lo que produce muy poca sobrecarga, y además permite la corrección de ese bit si es conocida su posición.

Dos entre cinco

En los años 40, Bell utilizó un código algo más sofisticado conocido como dos-entre-cinco. Este código se basa en que cada bloque de cinco bits (conocido como penta-bit) tuviera exactamente dos unos, asegurando así que tenga una Distancia de Hamming igual a dos. De este modo, la computadora podría detectar posibles errores cuando en su entrada no había exactamente dos unos en cada penta-bit.

Este código seguía únicamente detectando errores por cambio en un solo bit; si en un mismo penta-bit un 0 cambiaba a 1 y un 1 cambiaba a 0, la regla de dos-entre-cinco se seguía cumpliendo y el error quedaba sin descubrir.

Repetición

Otro código utilizado, consistía en repetir cada bit de datos varias veces para asegurarse de que la transmisión era correcta. Por ejemplo, si el bit de datos que se envía fuera un 1, un código de repetición con n=3, enviaría "111". Si los tres bits recibidos no eran idénticos, había un error. En un ambiente sin demasiado ruido, la mayoría de las veces solamente cambiaría un bit en cada paquete de tres bits. Por lo tanto, datos del tipo 001, 010, y 100 se corresponden al bit 0, mientras que 110, 101, y 011 se corresponden con el bit 1. Un código con esta capacidad de reconstruir el mensaje original en la presencia de errores se conoce como código corrector de errores.

Sin embargo, este código no puede reparar correctamente todos los errores. En nuestro ejemplo, si el error en la transmisión provocara el cambio simultáneo de dos bits y el receptor recibiera "001", el sistema detectaría el error, pero considerando que el bit original era 0, lo cual es incorrecto. Si se aumenta el número de veces que se repite cada bit a cuatro (n=4), es posible detectar los errores en dos bits pero obviamente no se podrán corregir; con cinco, es posible corregir errores de dos bits, pero no lo podrá hacer en errores de tres bits.

Por otra parte, el código de la repetición es extremadamente ineficaz, pues reduce la velocidad de transmisión por tres en nuestro ejemplo original y su eficacia cae drásticamente al aumentar el número de veces que cada bit se repite para detectar y corregir más errores. El uso del código de bloques no lineales para detección de errores no es muy implementado por lo tanto emplearemos el código de errores lineales para la corrección de errores.

Other Languages
العربية: كود هامنج
čeština: Hammingův kód
Deutsch: Hamming-Code
English: Hamming code
euskara: Hamming kode
فارسی: کد همینگ
français: Code de Hamming
עברית: קוד המינג
한국어: 해밍 부호
македонски: Хамингов код
Nederlands: Hamming-code
polski: Kod Hamminga
português: Código de Hamming
русский: Код Хэмминга
Simple English: Hamming code
српски / srpski: Хамингов код
svenska: Hammingkod
Türkçe: Hamming kodu
українська: Коди Гемінга
Tiếng Việt: Mã Hamming
中文: 汉明码