Le bit de parité et la distance de Hamming

Un canal n'est jamais parfait

Quand des bits voyagent (câble, ondes, disque), certains se retournent : un 0 devient 1, un 1 devient 0. Sans précaution, on reçoit un message corrompu sans même le savoir. L'idée des codes correcteurs est d'ajouter de la redondance calculée, pour d'abord détecter, puis parfois corriger ces erreurs.

Le bit de parité

Le plus simple : ajouter un bit de parité à la fin d'un bloc, choisi pour que le nombre total de 1 soit pair. À la réception, on recompte : si le total est impair, c'est qu'un bit a été altéré.

donnee : 1 0 1 1  ->  nombre de 1 = 3 (impair)
bit de parite ajoute : 1   (pour rendre le total pair)
mot transmis : 1 0 1 1 1   ->  quatre 1, c'est pair (correct)

a la reception, si on compte un nombre impair de 1 -> une erreur detectee

Sa limite

Le bit de parité détecte tout nombre impair d'erreurs (1, 3, 5...), mais rate un nombre pair d'erreurs : si deux bits se retournent, la parité reste correcte et l'erreur passe inaperçue. Surtout, il détecte sans pouvoir corriger : il signale qu'une erreur existe, sans dire où.

La distance de Hamming

La distance de Hamming entre deux mots binaires est le nombre de positions où ils diffèrent. Par exemple, entre 1011 et 1110, elle vaut 2 (positions 2 et 3 différentes). C'est l'outil clé pour raisonner sur les codes.

  1 0 1 1
  1 1 1 0
  -------
  = . X . X    (2 positions differentes -> distance de Hamming = 2)

Pourquoi la distance minimale compte

Un code n'utilise pas tous les mots possibles, seulement certains, appelés mots valides. La plus petite distance entre deux mots valides s'appelle la distance minimale du code. Elle décide de tout : pour détecter jusqu'à d erreurs, il faut une distance minimale d'au moins d+1 ; pour corriger jusqu'à d erreurs, il en faut au moins 2d+1.

Piège classique

Détecter et corriger ne sont pas la même chose. Un simple bit de parité détecte une erreur mais ne peut pas la corriger, faute de savoir quel bit est fautif. Corriger exige plus de redondance : c'est tout l'objet du code de Hamming, à la leçon suivante.