En la detección de errores , el algoritmo Damm es un algoritmo de dígitos 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]
Fortalezas y debilidades
Fortalezas
El algoritmo Damm es similar al algoritmo Verhoeff . También detectará todas las apariciones de los dos tipos de errores de transcripción que aparecen con más frecuencia , a saber, la alteración de un solo dígito y 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] Pero el algoritmo Damm tiene la ventaja de que se las arregla sin que las permutaciones construidas con dedicación y sus poderes específicos de posición sean inherentes al esquema de Verhoeff . Además, se puede prescindir de una tabla de inversas siempre que todas las entradas diagonales principales de la tabla de operaciones sean cero.
El algoritmo Damm no sufre de exceder el número de 10 valores posibles, lo que resulta en la necesidad de utilizar 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 el dígito de control. [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.
Debilidades
Dado que anteponer ceros a la izquierda no afecta el dígito de control, [1] los códigos de longitud variable no deben verificarse juntos ya que, por ejemplo, 0, 01 y 001, etc. producen el mismo dígito de control. Sin embargo, todos los algoritmos de suma de comprobación son vulnerables a esto.
Diseño
Su parte esencial es un cuasigrupo de orden 10 (es decir, que tiene un cuadrado latino de 10 × 10 como cuerpo de su mesa 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 vieja conjetura de que no existen cuasigrupos de orden 10 totalmente antisimétricos. [5]
Un cuasigrupo ( Q , ∗) se llama totalmente antisimétrico si para todo c , x , y ∈ Q , se cumplen las siguientes implicaciones: [4]
- ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y ,
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 débil totalmente antisimétrico de orden n . Para el algoritmo de Damm con la ecuación de verificación (... ((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 un cuasigrupo débil totalmente antisimétrico con la propiedad x ∗ x = 0 es necesario. Dicho cuasigrupo se puede construir a partir de cualquier cuasigrupo totalmente antisimétrico reordenando las columnas de tal manera que todos los ceros estén en la diagonal. Y, por otro lado, a partir de cualquier cuasigrupo débil totalmente antisimétrico se puede construir un cuasigrupo totalmente antisimétrico reorganizando las columnas de tal manera que la primera fila esté en orden natural. [3]
Algoritmo
La validez de una secuencia de dígitos que contiene un dígito de control se define sobre un cuasigrupo. Se puede tomar una mesa de cuasigrupos lista para usar de la disertación de Damm (páginas 98, 106, 111). [3] Es útil si cada entrada de la diagonal principal es 0, [1] porque simplifica el cálculo del dígito de control.
Validación de un número con el dígito de control incluido
- Configure un dígito intermedio e inicialícelo en 0.
- Procese el número dígito por dígito: use el dígito del número como índice de columna y el dígito intermedio como índice de fila, tome la entrada de la tabla y reemplace el dígito intermedio con él.
- El número es válido si y solo si el dígito intermedio resultante tiene el valor 0. [1]
Calcular el dígito de control
Requisito previo: Las entradas diagonales principales de la tabla son 0.
- Configure un dígito intermedio e inicialícelo en 0.
- Procese el número dígito por dígito: use el dígito del número como índice de columna y el dígito intermedio como índice de fila, tome la entrada de la tabla y reemplace el dígito intermedio con él.
- El dígito intermedio resultante proporciona el dígito de control y se agregará como dígito final al número. [1]
Ejemplo
Se utilizará la siguiente tabla de operaciones. [1] Puede obtenerse del cuasigrupo x ∗ y totalmente antisimétrico 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 ) .
⋅ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
0 | 0 | 3 | 1 | 7 | 5 | 9 | 8 | 6 | 4 | 2 |
1 | 7 | 0 | 9 | 2 | 1 | 5 | 4 | 8 | 6 | 3 |
2 | 4 | 2 | 0 | 6 | 8 | 7 | 1 | 3 | 5 | 9 |
3 | 1 | 7 | 5 | 0 | 9 | 8 | 3 | 4 | 2 | 6 |
4 | 6 | 1 | 2 | 3 | 0 | 4 | 5 | 9 | 7 | 8 |
5 | 3 | 6 | 7 | 4 | 2 | 0 | 9 | 5 | 8 | 1 |
6 | 5 | 8 | 6 | 9 | 7 | 2 | 0 | 1 | 3 | 4 |
7 | 8 | 9 | 4 | 5 | 3 | 6 | 2 | 0 | 1 | 7 |
8 | 9 | 4 | 3 | 8 | 6 | 1 | 7 | 2 | 0 | 5 |
9 | 2 | 5 | 8 | 1 | 4 | 3 | 6 | 7 | 9 | 0 |
Supongamos que elegimos el número (secuencia de dígitos) 572 .
Calcular el dígito de control
dígito a procesar → índice de columna | 5 | 7 | 2 |
---|---|---|---|
antiguo dígito intermedio → índice de fila | 0 | 9 | 7 |
entrada de tabla → nuevo dígito intermedio | 9 | 7 | 4 |
El dígito intermedio resultante es 4 . Este es el dígito de control calculado. Lo agregamos al número y obtenemos 5724 .
Validación de un número con el dígito de control incluido
dígito a procesar → índice de columna | 5 | 7 | 2 | 4 |
---|---|---|---|---|
antiguo dígito intermedio → índice de fila | 0 | 9 | 7 | 4 |
entrada de tabla → nuevo dígito intermedio | 9 | 7 | 4 | 0 |
El dígito intermedio resultante es 0 , por lo que el número es válido .
Ilustración gráfica
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.
Referencias
- ↑ a b c d e f g h Fenwick, Peter (2014). "Sumas de comprobación y control de errores". Introducción a la representación de datos informáticos . Editores de ciencia de Bentham. págs. 191–218 . doi : 10.2174 / 9781608058822114010013 . ISBN 978-1-60805-883-9.
- ^ Para conocer los tipos de errores comunes y sus frecuencias, consulte Salomon, David (2005). Codificación de datos y comunicaciones informáticas . Springer Science + Business Media, Inc. p. 36. ISBN 978-0387-21245-6.
- ^ a b c d e Damm, H. Michael (2004). Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. Nat.) (En alemán). Philipps-Universität Marburg. urn: nbn: de: hebis: 04-z2004-05162 .
- ^ a b Damm, H. Michael (2007). "Cuasigrupos totalmente antisimétricos para todos los órdenes n ≠ 2,6" . Matemáticas discretas . 307 (6): 715–729. doi : 10.1016 / j.disc.2006.05.033 . ISSN 0012-365X .
- ^ Damm, H. Michael (2003). "Sobre la existencia de cuasigrupos totalmente antisimétricos de orden 4 k + 2". Computación . 70 (4): 349–357. doi : 10.1007 / s00607-003-0017-3 . ISSN 0010-485X .
- ^ a b Beliavscaia Galina ; Izbaş Vladimir ; Şcerbacov Victor (2003). "Compruebe los sistemas de caracteres sobre cuasigrupos y bucles" (PDF) . Cuasigrupos y sistemas relacionados . 10 ( 1 ): 1–28 . ISSN 1561-2848 . Consulte la página 23.
- ^ Chen Jiannan (2009). "La NP-completitud de completar cuadrados latinos antisimétricos parciales" (PDF) . Actas del Taller internacional de 2009 sobre seguridad y aplicación de la información (IWISA 2009) . Editorial de la Academia. págs. 322–324 . ISBN 978-952-5726-06-0. Consulte la página 324.
- ^ Mileva, A .; Dimitrova, V. (2009). "Cuasigrupos construidos a partir de mapeos completos de un grupo (Z 2 n , ⊕)" (PDF) . Contribuciones, Sec. Matemáticas. Tech. Sci., MANU / MASA . XXX (1–2): 75–93. ISSN 0351-3246 . Consulte la página 78.
enlaces externos
- Validación y generación de código Damm en varios lenguajes de programación
- Aplicación práctica en Singapur
- Cuasigrupos para el algoritmo Damm hasta el pedido 64