Algorithme Damm

En détection d'erreurs , l' algorithme de Damm est un algorithme de contrôle par chiffre qui détecte toutes les erreurs à un seul chiffre et toutes les erreurs de transposition adjacentes . Il a été présenté par H. Michael Damm en 2004, dans le cadre de sa thèse de doctorat intitulée Quasigroups totalement antisymétriques.

L'algorithme de Damm est similaire à l' algorithme de Verhoeff . Il détecte également toutes les occurrences des deux types d' erreurs de transcription les plus fréquentes , à savoir la modification d'un seul chiffre ou la transposition de deux chiffres adjacents (y compris la transposition du chiffre de contrôle de fin et du chiffre précédent). L'algorithme de Damm a l'avantage de ne pas disposer des permutations spécialement construites et des pouvoirs spécifiques à la position du schéma de Verhoeff . Une table d' inverses peut également être supprimée lorsque toutes les entrées diagonales principales de la table d'opérations sont nulles.

L'algorithme Damm génère seulement 10 valeurs possibles, évitant ainsi le recours à un caractère non numérique (comme le X dans le schéma de contrôle ISBN à 10 chiffres ).

L'ajout de zéros non significatifs n'affecte pas le chiffre de contrôle (une faiblesse pour les codes à longueur variable).

Il existe des quasi-groupes totalement antisymétriques qui détectent toutes les erreurs phonétiques associées à la langue anglaise ( 13 ↔ 30 , 14 ↔ 40 , ..., 19 ↔ 90 ). Le tableau utilisé dans l'exemple d'illustration est basé sur une instance de ce type.

Pour tous les algorithmes de somme de contrôle, y compris l'algorithme Damm, l'ajout de zéros au début n'affecte pas le chiffre de contrôle, donc 1, 01, 001, etc. produisent le même chiffre de contrôle. Par conséquent, les codes de longueur variable ne doivent pas être vérifiés ensemble.

Sa partie essentielle est un quasigroupe d' ordre 10 (c'est-à-dire ayant un carré latin 10 × 10 comme corps de sa table d'opération ) avec la particularité d'être faiblement totalement antisymétrique . Damm a révélé plusieurs méthodes pour créer des quasigroupes totalement antisymétriques d'ordre 10 et a donné quelques exemples dans sa thèse de doctorat. Avec cela, Damm a également réfuté une vieille conjecture selon laquelle les quasigroupes totalement antisymétriques d'ordre 10 n'existent pas.

Un quasigroupe ( Q , ∗) est dit totalement antisymétrique si pour tout c , x , y ∈ Q , les implications suivantes sont valables :

1. ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
2. x ∗ y = y ∗ x ⇒ x = y ,

et il est dit faible totalement antisymétrique si seule la première implication est vraie. Damm a prouvé que l'existence d'un quasigroupe totalement antisymétrique d'ordre n est équivalente à l'existence d'un quasigroupe faible totalement antisymétrique d'ordre n . Pour l'algorithme de Damm avec l'équation de vérification (...((0 ∗ x _m ) ∗ x _{m −1} ) ∗ ...) ∗ x ₀ = 0 , un quasigroupe faible totalement antisymétrique avec la propriété x ∗ x = 0 est nécessaire. Un tel quasigroupe peut être construit à partir de tout quasigroupe totalement antisymétrique en réorganisant les colonnes de telle sorte que tous les zéros se trouvent sur la diagonale. Et, d'autre part, à partir de tout quasigroupe faible totalement antisymétrique, un quasigroupe totalement antisymétrique peut être construit en réorganisant les colonnes de telle sorte que la première ligne soit dans l'ordre naturel.

La validité d'une séquence de chiffres contenant un chiffre de contrôle est définie sur un quasi-groupe. Un tableau de quasi-groupes prêt à l'emploi peut être extrait de la thèse de Damm (pages 98, 106, 111). Il est utile que chaque entrée diagonale principale soit 0 , car cela simplifie le calcul du chiffre de contrôle.

1. Configurez un chiffre intermédiaire et initialisez-le à 0 .
2. Traitez le nombre chiffre par chiffre : utilisez le chiffre du nombre comme index de colonne et le chiffre intermédiaire comme index de ligne, prenez l'entrée du tableau et remplacez le chiffre intermédiaire par celui-ci.
3. Le numéro est valide si et seulement si le chiffre intermédiaire résultant a la valeur 0.

Prérequis : Les entrées diagonales principales du tableau sont 0 .

1. Configurez un chiffre intermédiaire et initialisez-le à 0 .
2. Traitez le nombre chiffre par chiffre : utilisez le chiffre du nombre comme index de colonne et le chiffre intermédiaire comme index de ligne, prenez l'entrée du tableau et remplacez le chiffre intermédiaire par celui-ci.
3. Le chiffre intermédiaire résultant donne le chiffre de contrôle et sera ajouté comme chiffre de fin au numéro.

Le tableau d'opérations suivant sera utilisé. Il peut être obtenu à partir du quasigroupe totalement antisymétrique x ∗ y dans la thèse de doctorat de Damm page 111 en réorganisant les lignes et en modifiant les entrées avec la permutation φ = (1 2 9 5 4 8 6 7 3) et en définissant x ⋅ y = φ ⁻¹ ( φ ( x ) ∗ y ) .

Supposons que nous choisissions le nombre (séquence de chiffres) 572 .

Le chiffre intermédiaire obtenu est 4 . Il s'agit du chiffre de contrôle calculé. Nous l'ajoutons au nombre et obtenons 5724 .

Le chiffre intermédiaire résultant est 0 , le numéro est donc valide .

Voici l'exemple ci-dessus montrant le détail de l'algorithme générant le chiffre de contrôle (flèche bleue en pointillés) et vérifiant le nombre 572 avec le chiffre de contrôle.