Somme de contrôle - Définition

Introduction

La somme de contrôle (en anglais : checksum), parfois appelé aussi « empreinte », est un concept de la théorie des codes utilisé pour les codes correcteurs, elle correspond à un cas particulier de contrôle par redondance. Elle est largement utilisée en informatique et en télécommunications numériques.

Exemple de calcul de l'empreinte de deux chaînes de caractères proches. Ceci est généralisable à n'importe quelle chaîne de caractère et n'importe quel fichier.

Utilisation

Les codes utilisant les sommes de contrôle permettent de valider un message. Si le nombre d'altérations durant la transmission est suffisamment petit, alors elles sont détectées. L'utilisation d'une unique somme de contrôle permet la détection mais non la correction des erreurs.

Une somme de contrôle est un moyen simple pour garantir l'intégrité de données en détectant les erreurs lors d'une transmission de données dans le temps (sur un support de données) ou dans l'espace (télécommunications). Le principe est d'ajouter aux données des éléments dépendant de ces dernières — on parle de redondance — et simples à calculer. Cette redondance accompagne les données lors d'une transmission ou bien lors du stockage sur un support quelconque. Plus tard, il est possible de réaliser la même opération sur les données et de comparer le résultat à la somme de contrôle originale, et ainsi conclure sur la corruption potentielle du message.

Un cas particulier répandu dans l'industrie est celui du bit de parité. C'est une somme de contrôle dans le cas où l'alphabet comporte deux lettres zéro et un.

Remarque : Le terme de somme de contrôle est aussi utilisé de manière générique pour décrire la redondance dans les codes correcteurs linéaires. Cette utilisation du mot est décrite dans le paragraphe Code systématique de l'article Matrice génératrice. Cette acception du mot est parfois considérée comme impropre.

Exemples d'utilisation

ASCII

Une utilisation célèbre est celle faite au début de l'utilisation du code ASCII : 7 bits étaient utilisés ; les ordinateurs utilisant couramment 8 bits, il en restait un de disponible. Ce dernier bit a donc été fréquemment utilisé pour une somme de contrôle : sa valeur était la somme, binaire, ou de manière équivalente le « ou exclusif » des 7 premiers bits. Tout changement d'un nombre impair de bits peut alors être détecté.

Protocole IP

Plus récemment, une telle somme est utilisée pour les octets numéro 11 et 12 de l'en-tête des paquets IP. Ces deux octets sont calculés de la manière suivante. Les octets sont numérotés de 1 à 10.

Les 16 bits constitués par les octets numéros i et i+1, pour i=1,3,5,7 et 9, sont considérés comme l'écriture binaire d'un entier. Les 5 entiers ainsi obtenus sont additionnés. On obtient alors un entier pouvant nécessiter plus de 16 bits. Ce dernier est alors coupé en deux, les 16 bits de poids faibles et les autres, on calcule la somme de ces deux moitiés et on itère ce procédé tant que l’on n’obtient pas un entier n'utilisant que 16 bits. Pour finir, chaque bit de ce dernier entier est changé. L'objectif derrière ce calcul est plus simple qu'il n'y paraît. Lorsque l'on répète l'opération en incluant la somme de contrôle, c'est-à-dire lorsque l'on vérifie la validité de l'en-tête, on obtient 16 bits à la valeur 1.

Ligne de commande Unix

Sous Unix il existe un utilitaire en ligne de commande, cksum, qui indique une somme de contrôle (checksum en anglais) basée sur un Contrôle de redondance cyclique en 32 bits ainsi que la taille (en octets) et le nom du ou des fichiers donné en entrée.

Communication

Pour transmettre à distance une suite de caractères, il est généralement fait appel à un UART (Universal Asynchronous Synchronous Receiver Transmitter) qui opère entre autres la conversion parallèle/série à l'émission et série/parallèle à la réception. De nombreux modèles d'UART permettent de calculer automatiquement et d'accoler aux bits des caractères le bit de parité ; à la réception, on contrôle la parité du caractère et on positionne un drapeau (flag) en cas d'erreur.

Carte mémoire

Les ordinateurs utilisent comme mémoire de travail des mémoires dynamiques (DRAM). Pendant de nombreuses années, les boîtiers de DRAM géraient des mots d'un bit ; il fallait donc placer sur la carte mémoire 8 boîtiers pour travailler avec des octets (8 bits). Pourtant, de nombreuses cartes comportaient non pas 8, mais 9 boîtiers ! Le neuvième boîtier était destiné à stocker un bit de parité lors de chaque mise en mémoire d'un octet. Lors de la lecture d'un octet, on vérifiait si, entre le moment de l'écriture et celui de la lecture, la parité n'avait pas été modifiée (suite à un parasite, par exemple).