Corriger les erreurs

Le code de Hamming(7,4)

Détecter ne suffit pas toujours

Quand la retransmission est impossible (un CD rayé, un signal d'un satellite lointain), il faut corriger l'erreur sur place, sans redemander le message. Le code de Hamming(7,4), inventé en 1950, réalise cet exploit : il transmet 4 bits de données protégés par 3 bits de contrôle, et corrige automatiquement toute erreur d'un seul bit.

Trois bits de parité qui se recoupent

L'astuce : chaque bit de contrôle surveille un sous-ensemble différent des bits de données, et ces sous-ensembles se recoupent. On représente cela par trois cercles qui se chevauchent (diagramme de Venn) : les 4 bits de données au centre, chaque bit de parité couvrant un cercle.

Diagramme de Hamming(7,4) : 3 cercles qui se chevauchent

            ___________
           /  P1       \
          /    ___________
         |    /  d1   \    \
         |   |  ___________|
          \  | /  d4   \ | /
           \_|_|   d2  |_|/
             | \_______/ |
          P2 |    d3     | P3
              \_________/

(chaque bit de parite P1, P2, P3 rend pair le total de SON cercle)
(un seul bit fautif appartient a une combinaison unique de cercles : cela revele sa position exacte)

La correction, comme un jeu de piste

À la réception, on recalcule les trois parités. Si les trois sont bonnes, aucune erreur. Sinon, la combinaison des parités fausses désigne exactement le bit fautif : chaque position appartient à une combinaison unique de cercles. On retourne ce bit, et le message est réparé — sans avoir rien redemandé.

Le prix de la correction

Hamming(7,4) a une distance minimale de 3 : c'est le minimum pour corriger 1 erreur (2d+1 = 3 avec d=1). Il paie cette capacité par de la redondance : 7 bits transmis pour 4 bits utiles, soit environ 43 % de surcoût. Corriger coûte toujours plus cher que détecter.

Piège classique