Normalmente pensamos que, si un mensaje llega con un error, como mucho podremos detectar que algo falló. Pero hay códigos que hacen algo más elegante: señalan exactamente dónde está el fallo y lo corrigen.
El archivo que se corrige solo
Enunciado
Quieres enviar un mensaje de 4 bits, por ejemplo:
Durante la transmisión puede cambiarse accidentalmente un solo bit.
Puedes añadir algunos bits extra antes de enviar el mensaje.
¿Cuántos bits extra bastan para que quien reciba el mensaje pueda detectar y corregir cualquier error de un solo bit?
Ver solución
Solución
Bastan 3 bits extra. El resultado es el código de Hamming $(7,4)$.
Numera las siete posiciones del bloque:
Reserva las posiciones 1, 2 y 4 para los bits de control. Coloca los cuatro bits del mensaje en 3, 5, 6 y 7.
Cada bit de control vigila las posiciones cuyo número binario contiene un 1 en una coordenada concreta:
- el control 1 revisa $1,3,5,7$;
- el control 2 revisa $2,3,6,7$;
- el control 4 revisa $4,5,6,7$.
Los controles se eligen para que cada grupo tenga paridad par.
Supongamos que durante la transmisión cambia el bit de la posición 6. Al recibir el bloque:
- la comprobación 1 pasa;
- la comprobación 2 falla;
- la comprobación 4 falla.
Los controles que fallan suman:
Ese resultado identifica exactamente la posición dañada. Basta invertir el bit 6 para corregir el mensaje.
Si no falla ninguna comprobación, no hubo error. Como las siete posiciones tienen firmas binarias distintas, cualquier error de un solo bit produce un síndrome distinto.
También es mínimo: con $r$ bits de control hay que distinguir ocho estados, el caso sin error y siete posibles posiciones erróneas. Por eso se necesita:
y el menor valor es $r=3$.
Respuesta: bastan 3 bits extra.