Definición de Código de Hamming

Consideremos un mensaje de N bits. La idea básica consiste en añadir un cierto número de P bits, cada uno de los cuales asegura un cierto subconjunto de los N+P dígitos totales mediante un control de paridad. Se considera la posibilidad de que exista, a lo sumo, una alteración en uno de los N+P bits y deseamos conocer si ha habido o no perturbación y, en caso afirmativo, cual de los N+P bits ha sido alterado. Puesto que el mensaje debe codificarse en los N bits, la información sobre el estado de perturbación debe cifrarse en los P bits, para poder así restablecerla.
Por tanto, conocido N, p debe ser la mínima cantidad de bits tal que los 2^P estados posibles de los P bits de paridad acepten al menos N + P + 1 estados distintos.
Por otra parte, los P conjuntos de bits deben elegirse de modo que el estado de los P bits de paridad asociados a esos conjuntos permita localizar con facilidad el bit alterado.
Un modo de conseguir el objetivo consiste en intercalar el bit I-ésimo en la posición 2^I-1, para I = 1, ..., P, siendo su conjunto asociado el de los dígitos cuyo número de posición, escrito en binario natural, tiene un 1 como cifra I-ésima.
Sea por ejemplo N = 4. Necesitamos P = 3 bits de paridad, que colocaremos en las posiciones 2^0, 2^1 y 2^2, es decir, en 1, 2 y 4:
Posición:
1____2____3____4____5____6____7
Id. en binario:
001__010__011__100__101__110__111
Ahora el bit 001 está asociado al conjunto de los bits del mensaje cuya posición acabe en 1 (1,3,5 y 7) o que tenga un 1 en la primer cifra; el bit 010 está asociado al conjunto de los bits del mensaje cuya posición tenga un 1 en la segunda cifra (2,3,6 y 7), y el bit 100 está asociado al conjunto de los bits del mensaje cuya cifra inicial sea un 1 (4,5,6 y 7) o que tenga un 1 en la tercer cifra.
CODIFICACIÓN
Sencillamente, se trata de ajustar los bits de paridad con respecto a sus conjuntos asociados. Por ejemplo, si se desea transmitir el mensaje 0110 bastará con ajustar el bit 1 con los 3, 5 y 7 (resultando un 1); el bit 2 con los 3, 6, y 7 (resultando un 1); y el bit 4 con los 5, 6 y 7 (resultando un 0):
Posición:
1__2__3__4__5__6__7
__ __0__ __1__1__0
1__1__0__0__1__1__0

DECODIFICACIÓN CON AUTOCORRECCIÓN
Para rectificar y descifrar un mensaje recibido, se detectan en primer lugar los bits de paridad que reflejan alguna alteración. Si no hay ninguno, el mensaje se ha mantenido intacto durante la transmisión; en caso contrario, la suma de las posiciones de los bits alterados señala el bit modificado.
Por ejemplo, si el mensaje anterior se recibe así:
Posición:
1__2__3__4__5__6__7
1__1__0__0__0__1__0
El control de paridad arroja el siguiente resultado:
bit 1 (3+5+7) = 1 (impar) -> bit 1 alterado;
bit 2 (3+6+7) = 2 (par) -> sin alterar;
bit 4 (5+6+7) = 1 (impar) -> bit 4 alterado;
Bits alterados: 4 y 5. Al ser 1+4 = 5, concluimos que el 5 bit es erróneo, por lo que el mensaje original era:
1__0__0__1__1__0