En la detección de errores , el algoritmo Damm es un algoritmo de dígito de control que detecta todos los errores de un solo dígito y todos los errores de transposición adyacentes . Fue presentado por H. Michael Damm en 2004, [1] como parte de su tesis doctoral titulada Cuasigrupos totalmente antisimétricos.
El algoritmo Damm es similar al algoritmo Verhoeff . También detectará todas las ocurrencias de los dos tipos de errores de transcripción que aparecen con más frecuencia , es decir, la alteración de un solo dígito o la transposición de dos dígitos adyacentes (incluida la transposición del dígito de control final y el dígito anterior). [1] [2] El algoritmo Damm tiene la ventaja de que no tiene las permutaciones construidas especialmente y sus potencias específicas de posición del esquema Verhoeff . También se puede prescindir de una tabla de inversas cuando todas las entradas de la diagonal principal de la tabla de operaciones son cero.
El algoritmo Damm genera sólo 10 valores posibles, evitando la necesidad de un carácter que no sea un dígito (como la X en el esquema de dígitos de control del ISBN de 10 dígitos ).
Anteponer ceros a la izquierda no afecta al dígito de control (una debilidad de los códigos de longitud variable). [1]
Existen cuasigrupos totalmente antisimétricos que detectan todos los errores fonéticos asociados al idioma inglés ( 13 ↔ 30 , 14 ↔ 40 , ..., 19 ↔ 90 ). La tabla utilizada en el ejemplo ilustrativo se basa en una instancia de este tipo.
En todos los algoritmos de suma de comprobación, incluido el algoritmo Damm, la adición de ceros a la izquierda no afecta al dígito de comprobación, [1] por lo que 1, 01, 001, etc. producen el mismo dígito de comprobación. En consecuencia, los códigos de longitud variable no se deben verificar juntos.
Su parte esencial es un cuasigrupo de orden 10 (es decir que tiene un cuadrado latino de 10 × 10 como cuerpo de su tabla de operaciones ) con la característica especial de ser débilmente totalmente antisimétrico . [3] [4] [i] [ii] [iii] Damm reveló varios métodos para crear cuasigrupos totalmente antisimétricos de orden 10 y dio algunos ejemplos en su tesis doctoral. [3] [i] Con esto, Damm también refutó una antigua conjetura de que los cuasigrupos totalmente antisimétricos de orden 10 no existen. [5]
Un cuasigrupo ( Q , ∗) se llama totalmente antisimétrico si para todo c , x , y ∈ Q , se cumplen las siguientes implicaciones: [4]
y se llama débil totalmente antisimétrico si sólo se cumple la primera implicación. Damm demostró que la existencia de un cuasigrupo totalmente antisimétrico de orden n es equivalente a la existencia de un cuasigrupo totalmente antisimétrico débil de orden n . Para el algoritmo de Damm con la ecuación de comprobación (...((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 , se necesita un cuasigrupo totalmente antisimétrico débil con la propiedad x ∗ x = 0 . Un cuasigrupo de este tipo se puede construir a partir de cualquier cuasigrupo totalmente antisimétrico reordenando las columnas de tal forma que todos los ceros queden en la diagonal. Y, por otra parte, a partir de cualquier cuasigrupo totalmente antisimétrico débil se puede construir un cuasigrupo totalmente antisimétrico reordenando las columnas de tal forma que la primera fila esté en orden natural. [3]
La validez de una secuencia de dígitos que contiene un dígito de control se define sobre un cuasigrupo. Se puede obtener una tabla de cuasigrupos lista para usar de la tesis de Damm (páginas 98, 106, 111). [3] Es útil que cada entrada de la diagonal principal sea 0 , [1] porque simplifica el cálculo del dígito de control.
Requisito: Las entradas diagonales principales de la tabla son 0 .
Se utilizará la siguiente tabla de operaciones. [1] Se puede obtener a partir del cuasigrupo totalmente antisimétrico x ∗ y en la tesis doctoral de Damm, página 111 [3] reorganizando las filas y cambiando las entradas con la permutación φ = (1 2 9 5 4 8 6 7 3) y definiendo x ⋅ y = φ −1 ( φ ( x ) ∗ y ) .
Supongamos que elegimos el número (secuencia de dígitos) 572 .
El dígito intermedio resultante es 4. Este es el dígito de control calculado. Lo agregamos al número y obtenemos 5724 .
El dígito provisional resultante es 0 , por lo tanto el número es válido .
Este es el ejemplo anterior que muestra el detalle del algoritmo que genera el dígito de control (flecha azul discontinua) y verifica el número 572 con el dígito de control.
