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ódigoscon bit de paridad, que pueden detectar errores en sólo un bit, pero no pueden corregirlo.
Hamming trabajó en los laboratorios Bell en los años 40 en la computadora del modelo V de Bell, un monstruo electromecánico basado en relés con velocidad de proceso de herz. La entrada se alimentaba con tarjetas perforadas en las que, con frecuencia, se cometían errores al ser leídas. En cada jornada, loserrores encontrados se indicaban mediante luces de destello para que los operadores pudieran corregir el problema. Fuera de las horas laborales y durante los fines de semana, cuando no había operadores, la máquina se dejaba preparada para el trabajo de la siguiente jornada. Hamming trabajando los fines de semana, se sentía frustrado cada vez que tenía que recomenzar sus programas debido a lafalta de fiabilidad del lector de tarjetas. Los siguientes años trabajó en el problema de error-corrección, desarrollando un arsenal de algoritmos cada vez más eficaces. En 1950 publicó lo que ahora se conoce como código de Hamming, que aún hoy sigue siendo utilizado.
Antes de los códigos Hamming se utilizaron ciertos códigos detectores de error, pero ninguno llegó a ser tan eficaz como los deHamming. 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 elmismo bit de paridad). La convención más común es que un valor de paridad de 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 más de un solo bit, el bit de paridad será válido y el error no será detectado. Por otro lado, laparidad, 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 deese bit si es conocida su posición.
Dos entre cinco [editar]
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 [editar]
Otro código utilizado, consistía en repetir cada bit de datos varias veces paraasegurarse 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. Es como si el bit original se obtuviera por mayoría en una «votación». 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…