Somme de contrôle - Définition

Approche intuitive

Motivation

Voyager 2 est un des nombreux utilisateurs des codes de parité pour communiquer de manière fiable.

Les codes correcteurs ont leur source dans un problème très concret lié à la transmission de données. Dans certains cas, une transmission de données se fait en utilisant une voie de communication qui n'est pas entièrement fiable. Autrement dit, les données, lorsqu'elles circulent sur cette voie, sont susceptibles d'être altérées. L'objectif des sommes de contrôle est l'apport d'une redondance de l'information de telle manière à ce que l'erreur puisse être détectée.

Dans le cas d'une unique somme de contrôle, et à la différence d'autres codes correcteurs, comme par exemple les codes cycliques, l'objectif n'est pas la correction automatique des erreurs, mais la détection. La correction est alors réalisée par une nouvelle demande de la part du récepteur. Si les codes cycliques sont plus performants, leur complexité algorithmique grandit ainsi que leur taille.

Une simple somme de contrôle se contente de faire une somme des lettres du message. Elle ne peut pas détecter certains types d'erreurs. En particulier une telle somme de contrôle est invariante par :

• réorganisation des octets du message
• ajout ou suppression d'octets à zéro
• erreurs multiples se compensant.

Plusieurs sommes de contrôles sont alors nécessaires, et la multiplication quitte parfois le domaine des corps binaires pour d'autres structures de corps fini plus complexes. Le terme de somme de contrôle est toujours utilisé, même si celui de contrôle de redondance cyclique est plus approprié.

Ce type de code entre dans la famille des codes linéaires. Elle a été formalisée après la Seconde Guerre mondiale. Claude Shannon et formalise la théorie de l'information comme une branche des mathématiques. Richard Hamming travaille spécifiquement sur la question de la fiabilité des codes pour les laboratoires Bell. Il développe les fondements de la théorie des codes correcteurs et formalise le concept de somme de contrôle dans sa généralité.

Exemple : bit de parité

Supposons que l'objectif soit la transmission de sept bits auxquels s'ajoute le bit de parité. Les huit bits transmis sont d'abord la parité puis les sept bits du message.

On peut définir le bit de parité comme étant égal à zéro si la somme des autres bits est paire et à un dans le cas contraire. On parle de parité paire, c’est-à-dire la deuxième colonne du tableau intitulée pair = 0. Les messages envoyés sur huit bits ont toujours la parité zéro, ainsi si une erreur se produit, un zéro devient un un, ou l'inverse ; le récepteur sait qu'une altération a eu lieu. En effet la somme des bits devient impaire ce qui n'est pas possible sans erreur de transmission.

Une deuxième convention peut être prise, le bit de parité est alors défini comme étant égal à un si la somme des autres bits est paire et à zéro dans le cas contraire. Le résultat correspond à la troisième colonne, intitulée impair = 0.

Le bit de parité est en gras sur les deuxièmes et troisièmes colonnes.

Il ne faut pas confondre parité d'un nombre, et le fait qu'il soit pair ou impair (au sens mathématique du terme). Le nombre binaire 00000011 (3 en nombre décimal) est impair (non-divisible par 2) mais de parité paire (nombre pair de bits à 1).

Cette approche permet de détecter les nombres d'erreurs impaires dans le cas où les lettres sont soit zéro soit un. La somme de contrôle généralise le concept pour la détection d'erreurs plus nombreuses et pour d'autres alphabets.