Algorithme de Damm

L'algorithme de Damm est un système de calcul de chiffre de contrôle / checksum conçu pour détecter les erreurs de saisie dans les identifiants numériques décimaux (numéros de série, codes administratifs, etc.). Conçu pour être simple à mettre en œuvre à la main ou par programmation, cet algorithme permet de détecter toutes les erreurs de substitution simple, toutes les transpositions adjacentes de chiffres, ainsi qu'une partie des erreurs multiples.

Le calcul repose sur l'utilisation d'une table de substitution unique de type quasigroupe d'ordre 10, dite table de Damm.

Le calcul commence avec c = 0. Pour chaque chiffre du nombre, lu de gauche à droite, calculer c = table[c][chiffre].

Pour vérifier un nombre, ajouter le chiffre de contrôle à la fin, puis traiter tous les chiffres : le résultat final doit être 0.

L'algorithme garantit la détection des types d'erreurs suivants :

— Toutes les erreurs de substitution simple (remplacement d'un chiffre par un autre, ex. : $ 1234 \rightarrow 1239 $).

— Toutes les transpositions adjacentes (inversion de deux chiffres voisins, ex. : $ 1234 \rightarrow 1324 $).

— Une partie des erreurs multiples.

En revanche, certaines permutations complexes ne sont pas détectées, telles que les permutations circulaires (ex. : $ 1234 \rightarrow 4123 $) ou certaines transpositions non adjacentes.

La complexité temporelle est linéaire en $ O(n) $, où $ n $ représente le nombre de chiffres de la séquence, puisque chaque chiffre est examiné une unique fois.

La complexité spatiale est constante en $ O(1) $ : la table de Damm est de taille fixe ($ 10 \times 10 $), ce qui nécessite un espace mémoire minimal et indépendant de la longueur de la donnée traitée.

La table de Damm est construite à partir d'un quasigroupe d'ordre 10 qui possède des propriétés algébriques spécifiques garantissant la détection des erreurs de transposition et de substitution. Plus précisément, la diagonale principale de la table ne contient que des zéros ($ N(x, x) = 0 $), et la structure mathématique respecte des conditions d'antisymétrie stricte qui empêchent les collisions lors d'échanges de chiffres adjacents.

Dans la table de Damm, $ \text{table}[0][0] = 0 $. Comme l'accumulateur démarre à $ c = 0 $, tout zéro placé en tête de séquence laisse $ c $ inchangé à $ 0 $. Ainsi, 123, 0123 et 00123 produisent exactement le même chiffre de contrôle ($ 4 $).

Oui, la méthode s'étend à n'importe quelle base $ n $ dès lors qu'il existe un quasigroupe faiblement totalement antisymétrique d'ordre $ n $. H. Michael Damm a démontré l'existence de tels quasigroupes pour tous les ordres $ n \neq 2 $ et $ n \neq 6 $ (utilisation possible en base $ 16 $ hexadécimale, base $ 32 $ ou base $ 36 $ alphanumérique, mais exclusion de la base $ 2 $ binaire et de la base $ 6 $).

L'algorithme a été introduit en 2004 par le mathématicien allemand H. Michael Damm dans sa thèse de doctorat intitulée Totally Antisymmetric Quasigroups.