Algoritmo de Verhoeff

El algoritmo de Verhoeff ^{[ 1 ]} es una suma de verificación para la detección de errores publicada por primera vez por el matemático holandés Jacobus Verhoeff en 1969. ^{[ 2 ] [ 3 ]} Fue el primer algoritmo de dígito de control decimal que detecta todos los errores de un solo dígito y todos los errores de transposición que involucran dos dígitos adyacentes, ^{[ 4 ]} lo cual en ese momento se pensaba imposible con un código de este tipo.

El método fue descubierto independientemente por H. Peter Gumm en 1985, esta vez incluyendo una demostración formal y una extensión a cualquier base. ^{[ 5 ]}

Verhoeff tenía el objetivo de encontrar un código decimal —uno en el que el dígito de control fuera un solo dígito decimal— que detectara 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 ^{[ 6 ]} de estos códigos hicieron que los códigos de base 11 se popularizaran, 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 reales del sistema postal holandés, utilizando un sistema de puntos ponderados para distintos tipos de errores. El análisis desglosó los errores en varias categorías: primero, según la cantidad de dígitos erróneos; para aquellos con dos dígitos erróneos, hay transposiciones ( ab → ba ), gemelos ( aa → bb ), transposiciones con salto ( abc → cba ), fonéticas ( 1a → a0 ) y gemelos con salto ( aba → cbc ). Además, hay dígitos omitidos y añadidos. Aunque la frecuencia de algunos de estos tipos de errores puede ser pequeña, algunos códigos pueden ser inmunes a ellos, además de los objetivos principales de detectar todos los errores simples y transposiciones.

Los errores fonéticos, en particular, mostraron efectos lingüísticos, ya que en neerlandés los números se leen normalmente en pares; y además, aunque 50 suena parecido a 15 en neerlandés, 80 no suena como 18.

Tomando como ejemplo los números de seis dígitos, Verhoeff informó la siguiente clasificación de los errores:

La idea general del algoritmo es representar cada uno de los dígitos (del 0 al 9) como elementos del grupo diedral D ₅ . Es decir, mapear los dígitos a D ₅ , manipularlos y luego volver a mapearlos a dígitos. Sea esta función m  : [0, 9] → D _{5 .}

${\displaystyle m={\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmatrix}}}$

Sea a el n _- ésimo dígito y sea k el número de dígitos .

Por ejemplo, dado el código 942, entonces k es 3 y a ₃ = m (2) = r ² .

Ahora definimos la permutación f  : D ₅ → D ₅

${\displaystyle f={\begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^{3}s&r^{3}&e&r^{4}s&r^{4}\end{pmatrix}}}$

Por ejemplo,${\displaystyle f(r^{3})=rs}$Otro ejemplo es${\displaystyle f^{2}(r^{3})=r^{3}}$desde${\displaystyle f(f(r^{3}))=f(rs)=r^{3}}$.

Utilizando la notación multiplicativa para la operación de grupo de D ₅ , el dígito de control es entonces simplemente un valor c tal que

${\displaystyle f^{0}(c)\cdot f^{1}(a_{k})\cdot \ldots \cdot f^{k-1}(a_{2})\cdot f^{k}(a_{1})=e}$

c viene dada explícitamente por el inverso multiplicativo:

${\displaystyle c=\left(\prod _{n=1}^{k}f^{n}(a_{k+1-n})\right)^{-1}}$

Por ejemplo, el dígito de control para 942 es 7. Para verificar esto, use la asignación a D ₅ e insértela en el lado izquierdo de la ecuación anterior.

${\displaystyle f^{0}(r^{2}s)\cdot f^{1}(r^{2})\cdot f^{2}(r^{4})\cdot f^{3}(r^{4}s)=e}$

Para evaluar esta permutación rápidamente, utilice eso.

${\displaystyle f^{3}(r^{4}s)=f^{2}(r^{4})=f^{1}(r^{2})=f^{0}(r^{2}s)=r^{2}s}$

para conseguir eso

${\displaystyle r^{2}s\cdot r^{2}s\cdot r^{2}s\cdot r^{2}s=e}$

Esta es la misma reflexión que se multiplica iterativamente. Utilice el hecho de que las reflexiones son su propio inverso. ^{[ 7 ]}

${\displaystyle (r^{2}s\cdot r^{2}s)\cdot (r^{2}s\cdot r^{2}s)=e^{2}=e}$

En la práctica, el algoritmo se implementa utilizando tablas de búsqueda simples sin necesidad de comprender cómo generarlas a partir de la teoría de grupos y permutaciones subyacente. Esto se considera más propiamente una familia de algoritmos, ya que otras permutaciones también funcionan. Verhoeff señala que la permutación particular, dada anteriormente, es especial porque tiene la propiedad de detectar el 95,3 % de los errores fonéticos. ^{[ 8 ]}

Las ventajas del algoritmo radican en que detecta todos los errores de transliteración y transposición, y además la mayoría de los errores de doble transposición, doble transposición con salto y errores fonéticos.

La principal debilidad del algoritmo de Verhoeff radica en su complejidad. Los cálculos necesarios no pueden expresarse fácilmente mediante una fórmula como Z / 10 Z. Se requieren tablas de consulta para facilitar el cálculo. Un algoritmo similar es el de Damm , que presenta características parecidas.

El algoritmo de Verhoeff se puede implementar utilizando tres tablas: una tabla de multiplicación 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 diedral D ₅ . ^{[ 7 ]} y es simplemente la tabla de Cayley del grupo. Nótese 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 permutaciones 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:

1. Crea 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 ₀ , etc.).
2. Inicialice la suma de verificación c a cero.
3. Para cada índice i del arreglo 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 ).

El algoritmo de Verhoeff se utiliza en una variedad de sistemas, entre ellos:

• Billetes de marco alemán ^{[ 10 ]}
• Números Aadhaar de la India ^{[ 11 ]}
• Operador del Sistema de Registro de Medidores de Irlanda ^{[ 12 ]}
• El diccionario de términos clínicos SNOMED ^{[ 13 ]}

• Algoritmo de Luhn : fórmula de suma de verificación simple 
• Algoritmo de Damm – Algoritmo del dígito de control 

• Descripción detallada del algoritmo de Verhoeff. Archivado el 26 de abril de 2006 en la Wayback Machine.