El algoritmo de Verhoeff [1] es una fórmula de suma de control para la detección de errores desarrollada por el matemático holandés Jacobus Verhoeff y se publicó por primera vez en 1969. [2] [3] Fue el primer algoritmo de dígitos de control decimal que detecta todos los errores de un solo dígito, y todos los errores de transposición que implican dos dígitos adyacentes, [4] que en ese momento se pensó que era imposible con un código de este tipo.
Metas
Verhoeff tenía el objetivo de encontrar un código decimal, uno donde el dígito de control es un solo dígito decimal, que detecta todos los errores de un solo dígito y todas las transposiciones de dígitos adyacentes. En ese momento, las supuestas pruebas de la inexistencia [5] de estos códigos hicieron populares los códigos en base 11, por ejemplo en el dígito de control del ISBN .
Sus objetivos también eran prácticos, y basó la evaluación de diferentes códigos en datos en vivo del sistema postal holandés, utilizando un sistema de puntos ponderados para diferentes tipos de error. El análisis dividió los errores en varias categorías: primero, por cuántos dígitos hay en el error; para aquellos con dos dígitos erróneos, hay transposiciones ( ab → ba ), gemelos ( aa → 'bb'), transposiciones de salto ( abc → cba ), fonético ( 1a → a0 ) y gemelos de salto ( aba → cbc ). Además, hay dígitos omitidos y agregados. Aunque las frecuencias de algunos de estos tipos de errores pueden ser pequeñas, algunos códigos pueden ser inmunes a ellos además de los objetivos principales de detectar todos los singles y transposiciones.
Los errores fonéticos en particular mostraron efectos lingüísticos, porque en holandés, los números se leen típicamente en pares; y también, mientras que 50 suena similar a 15 en holandés, 80 no suena como 18.
Tomando números de seis dígitos como ejemplo, Verhoeff informó la siguiente clasificación de los errores :.
Dígitos erróneos | Clasificación | Contar | Frecuencia |
---|---|---|---|
1 | Transcripción | 9.574 | 79,05% |
2 | Transposiciones | 1.237 | 10,21% |
mellizos | 67 | 0,55% | |
Fonético | 59 | 0,49% | |
Otros adyacentes | 232 | 1,92% | |
Saltar transposiciones | 99 | 0,82% | |
Saltar gemelos | 35 | 0,29% | |
Otros errores de salto | 43 | 0,36% | |
Otro | 98 | 0,81% | |
3 | 169 | 1,40% | |
4 | 118 | 0,97% | |
5 | 219 | 1,81% | |
6 | 162 | 1,34% | |
Total | 12,112 |
Descripción
Verhoeff ideó su algoritmo utilizando las propiedades del grupo diedro de orden 10 (un sistema de operaciones no conmutativo en diez elementos, que corresponde a la rotación y reflexión de un pentágono regular), combinado con una permutación. Afirmó que era el primer uso práctico del grupo diedro, y confirmó el principio de que al final, todas las matemáticas hermosas encontrarán un uso, [6] aunque en la práctica el algoritmo se implementará usando tablas de búsqueda simples sin necesidad de comprender cómo generar esas tablas a partir del grupo subyacente y la teoría de permutación.
Esto se considera más apropiadamente una familia de algoritmos, ya que hay otras permutaciones posibles y se discuten en el tratamiento de Verhoeff. Señala que esta permutación particular,
es especial ya que tiene la propiedad de detectar el 95,3% de los errores fonéticos. [7]
Los puntos fuertes del algoritmo son que detecta todos los errores de transliteración y transposición y, además, la mayoría de los errores de gemelos, saltos gemelos, transposición de saltos y fonéticos.
La principal debilidad del algoritmo de Verhoeff es su complejidad. Los cálculos necesarios no se pueden expresar fácilmente como una fórmula. Se requieren tablas de búsqueda para facilitar el cálculo. Un código similar es el algoritmo Damm , que tiene cualidades similares.
Algoritmo basado en tablas
El algoritmo de Verhoeff se puede implementar usando tres tablas: una tabla de multiplicar d , una tabla inversa inv y una tabla de permutación p .
|
|
|
La primera tabla, d , se basa en la multiplicación en el grupo diedro D 5 . [9] y es simplemente la mesa Cayley del grupo. Tenga en cuenta que este grupo no es conmutativo , es decir, para algunos valores de j y k , d ( j , k ) ≠ d ( k , j ).
La tabla inversa inv representa el inverso multiplicativo de un dígito, es decir, el valor que satisface d ( j , inv ( j )) = 0.
La tabla de permutación p aplica una permutación a cada dígito en función de su posición en el número. En realidad, se trata de una única permutación (1 5 8 9 4 2 7 0) (3 6) aplicada iterativamente; es decir, p ( i + j , n ) = p ( i , p ( j , n )).
El cálculo de la suma de verificación de Verhoeff se realiza de la siguiente manera:
- Cree una matriz n a partir de los dígitos individuales del número, tomados de derecha a izquierda (el dígito más a la derecha es n 0 , etc.).
- Inicialice la suma de comprobación c a cero.
- Para cada índice i de la matriz n, comenzando en cero, reemplace c con d (c, p (i mod 8, n i )).
El número original es válido si y solo si c = 0 .
Para generar un dígito de control, agregue un 0 , realice el cálculo: el dígito de control correcto es inv (c) .
Ejemplos de
Genere un dígito de control para 236 :
c es 2, por lo que el dígito de control es inv (2), que es 3. | Valide el dígito de control 2363 :
c es cero, por lo que la comprobación es correcta. |
Referencias
- ^ Verhoeff, J. (1969). Error al detectar códigos decimales (sección 29) . El Centro Matemático, Amsterdam. doi : 10.1002 / zamm.19710510323 .
- ^ Kirtland, Joseph (2001). Números de identificación y esquemas de dígitos de control . Asociación Matemática de América. pag. 153. ISBN 0-88385-720-0. Consultado el 26 de agosto de 2011 .
- ^ Salomon, David (2005). Codificación de datos y comunicaciones informáticas . Saltador. pag. 56. ISBN 0-387-21245-0. Consultado el 26 de agosto de 2011 .
- ^ Haunsperger, Deanna; Kennedy, Stephen, eds. (2006). The Edge of the Universe: Celebrando diez años de horizontes matemáticos . Asociación Matemática de América. pag. 38. ISBN 978-0-88385-555-3. LCCN 2005937266 . Consultado el 26 de agosto de 2011 .
- ^ Sisson, Roger L., Una verificación de redundancia decimal mejorada, Comunicaciones del ACM Vol. 1, edición. 5, mayo de 1958, págs. 10-12, doi : 10.1145 / 368819.368854 .
- ^ Verhoeff, J. (1975). Error al detectar códigos decimales (sección 29), segunda impresión . El Centro Matemático, Amsterdam.
- ^ Verhoeff, 1969, p. 95
- ^ Verhoeff, 1969, p. 83
- ^ Gallian, Joseph A. (2010). Álgebra abstracta contemporánea (7ª ed.). Brooks / Cole. pag. 111 . ISBN 978-0-547-16509-7. LCCN 2008940386 . Consultado el 26 de agosto de 2011 .
Verhoeff dígito de control.