Hispanopedia WikiEn la detección de errores , el algoritmo de 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.
Fortalezas y debilidades
Fortalezas
El algoritmo de Damm es similar al algoritmo de Verhoeff . También detectará todas las ocurrencias de los dos tipos de errores de transcripción más frecuentes : 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 precedente). [ 1 ] [ 2 ] El algoritmo de Damm tiene la ventaja de no tener las permutaciones construidas específicamente ni las capacidades específicas de posición del esquema de Verhoeff . También se puede prescindir de una tabla de inversos cuando todas las entradas de la diagonal principal de la tabla de operaciones son cero.
El algoritmo de Damm genera solo 10 valores posibles, evitando la necesidad de un carácter que no sea un dígito (como la X en el sistema de dígitos de control 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 un caso de este tipo.
Debilidades
Para todos los algoritmos de suma de verificación, incluido el algoritmo Damm, anteponer ceros no afecta al dígito de verificación, [ 1 ] por lo que 1, 01, 001, etc. producen el mismo dígito de verificación. En consecuencia, los códigos de longitud variable no deben verificarse juntos.
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 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 no existen cuasigrupos totalmente antisimétricos de orden 10. [ 5 ]
Un cuasigrupo ( Q , ∗) se denomina 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 denomina débil totalmente antisimétrico si solo 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 , se necesita un cuasigrupo débil totalmente antisimétrico con la propiedad x ∗ x = 0. Dicho cuasigrupo puede construirse a partir de cualquier cuasigrupo totalmente antisimétrico reordenando las columnas de tal manera que todos los ceros queden 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 reordenando 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. Una tabla de cuasigrupos lista para usar se puede obtener de la disertación 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.
Validar un número con respecto al dígito de control incluido.
- Establezca un dígito intermedio e inicialícelo a 0 .
- Procese el número dígito por dígito: utilice 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 ella.
- El número es válido si y solo si el dígito intermedio resultante tiene el valor de 0. [ 1 ]
Cálculo del dígito de control
Requisito previo: Las entradas de la diagonal principal de la tabla son 0 .
- Establezca un dígito intermedio e inicialícelo a 0 .
- Procese el número dígito por dígito: utilice 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 ella.
- 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 ] Se puede obtener del cuasigrupo totalmente antisimétrico x ∗ y en la página 111 de la tesis doctoral de Damm [ 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 .
Cálculo del dígito de control
El dígito intermedio resultante es 4. Este es el dígito de control calculado. Lo añadimos al número y obtenemos 5724 .
Validar un número con respecto al dígito de control incluido.
El dígito intermedio resultante es 0 , por lo tanto, 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
- 1 2 3 4 5 6 7 8 Fenwick, Peter (2014). «Sumas de verificación y control de errores». En Fenwick, Peter (ed.). Introducción a la representación de datos informáticos . Bentham Science Publishers. págs. 191–218 . doi : 10.2174/9781608058822114010013 . ISBN 978-1-60805-883-9.
- ↑ Para conocer los tipos de errores comunes y sus frecuencias, véase Salomon, David (2005). Coding for Data and Computer Communications . Springer Science+Business Media, Inc., pág. 36. ISBN 978-0387-21245-6.
- ^ Damm , H. Michael ( 2004) . Total anti-symmetrische Quasigruppen (PDF) (Dr. rer. nat.) (en alemán). Universidad Philipps de Marburg. urna:nbn:de:hebis:04-z2004-05162 .
- 1 2 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 4k + 2 ". Computing . 70 (4): 349–357 . doi : 10.1007/s00607-003-0017-3 . ISSN 0010-485X . S2CID 31659430 .
- 1 2 Beliavscaia, Galina; Izbaş, Vladimir; Şcerbacov, Victor (2003). "Check character systems over quasigroups and loops" (PDF) . Quasigroups and Related Systems . 10 (1): 1– 28. ISSN 1561-2848 . Ver página 23.
- ↑ Chen Jiannan (2009). "La NP-completitud de la completación de cuadrados latinos antisimétricos parciales" (PDF) . Actas del Taller Internacional de 2009 sobre Seguridad de la Información y Aplicaciones (IWISA 2009) . Academy Publisher. págs. 322–324 . ISBN 978-952-5726-06-0.Véase 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. Math. Tech. Sci., MANU/MASA . XXX ( 1–2 ): 75–93 . ISSN 0351-3246 . Ver página 78.
Enlaces externos
- Código de validación y generación de Damm en varios lenguajes de programación.
- Aplicación práctica en Singapur
- Cuasigrupos para el algoritmo de Damm hasta el orden 64
- En RosettaCode.org, implementaciones del algoritmo Damm en muchos lenguajes de programación.
- Algoritmos de suma de verificación
- Estructuras algebraicas
- cuadrados latinos
- teoría de grupos
- Presentaciones de 2004
