Algoritmo de Verhoeff

Forma de detectar errores en códigos decimales

El algoritmo de Verhoeff ^[1] es una suma de comprobació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 verificación de dígitos decimales 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 que en ese momento se creía imposible con un código de este tipo.

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

Objetivos

Verhoeff tenía como objetivo encontrar un código decimal (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 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 son erróneos; para aquellos con dos dígitos erróneos, hay transposiciones ( ab → ba ), gemelos ( aa → 'bb'), transposiciones de salto ( abc → cba ), fonéticos ( 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 sencillos y transposiciones.

Los errores fonéticos en particular mostraron efectos lingüísticos, porque en holandés los números normalmente se leen en pares; y además, aunque 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:

Descripción

La idea general del algoritmo es representar cada uno de los dígitos (del 0 al 9) como elementos del grupo diedro . Es decir, asignar dígitos a , manipularlos y luego asignarlos nuevamente a dígitos. Sea esta asignación ${\displaystyle D_{5}}$ ${\displaystyle D_{5}}$ ${\displaystyle m:[0,9]\to 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 el n-ésimo dígito y sea el número de dígitos . ${\displaystyle a_{n}}$ ${\displaystyle k}$

Por ejemplo, dado el código 248 entonces es 3 y . ${\displaystyle k}$ ${\displaystyle a_{3}=m(8)=r^{3}s}$

Ahora defina la permutación ${\displaystyle f:D_{5}\to D_{5}}$

${\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 . Otro ejemplo es que ${\displaystyle f(r^{3})=rs}$ ${\displaystyle f^{2}(r^{3})=r^{3}}$ ${\displaystyle f(f(r^{3}))=f(rs)=r^{3}}$

Usando la notación multiplicativa para la operación de grupo de , el dígito de verificación es entonces simplemente un valor tal que ${\displaystyle D_{5}}$ ${\displaystyle c}$

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

${\displaystyle c}$se da explícitamente por permutación inversa

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

Por ejemplo, el dígito de control para 248 es 5. Para verificarlo, use la asignación a e inserte en el LHS de la ecuación anterior. ${\displaystyle D_{5}}$

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

Para evaluar esta permutación rápidamente use eso

${\displaystyle f^{4}(s)=f^{3}(r^{3}s)=f^{2}(r^{4})=f(r^{2})=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. Use que las reflexiones son su propia inversa. ^[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 entender cómo generar esas tablas a partir del grupo subyacente y la teoría de permutaciones. Esto se considera más propiamente una familia de algoritmos, ya que también funcionan otras permutaciones. Verhoeff señala que la permutación particular, dada anteriormente, es especial ya que tiene la propiedad de detectar el 95,3% de los errores fonéticos. ^[8]

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 gemelos, de salto gemelo, de transposición de salto 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 , por ejemplo, se necesitan tablas de consulta para facilitar el cálculo. Un código similar es el algoritmo de Damm , que tiene cualidades similares. ${\displaystyle {\displaystyle \mathbb {Z} /10\mathbb {Z} }}$

Algoritmo basado en tablas

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 diedro 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 de forma iterativa; es decir, p ( i + j , n ) = p ( i , p ( j , n )).

El cálculo de la suma de comprobació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. Inicializa la suma de comprobación c a cero.
3. Para cada índice i de la matriz n, comenzando en cero, reemplace c con ⁠ ⁠ ${\displaystyle d(c,p(i{\bmod {8}},n_{i}))}$ .

El número original es válido si y sólo si ⁠ ⁠ ${\displaystyle c=0}$ .

Para generar un dígito de control, agregue un0 , realice el cálculo: el dígito de control correcto es ⁠ ⁠ ${\displaystyle inv(c)}$ .

Ejemplos

Véase también

• Algoritmo de Luhn , algoritmo de dígito de control anterior (1960)

Referencias

1. Verhoeff, J. (1969). "Error al detectar códigos decimales (tramo 29)". Zeitschrift Angewandte Mathematik und Mechanik . 51 (3). El Centro de Matemáticas, Ámsterdam: 240. Bibcode : 1971ZaMM...51..240N. doi :10.1002/zamm.19710510323.
2. Kirtland, Joseph (2001). "5. Teoría de grupos y esquema de dígitos de control de Verhoeff". Números de identificación y esquemas de dígitos de control . Asociación Matemática de Estados Unidos. pág. 153. ISBN 0-88385-720-0.
3. Salomon, David (2005). "§2.11 El método del dígito de control de Verhoeff". Codificación de datos y comunicaciones informáticas . Springer. págs. 56–58. ISBN 0-387-21245-0.
4. Haunsperger, Deanna; Kennedy, Stephen, eds. (2006). El borde del universo: Celebrando diez años de Math Horizons. Asociación Matemática de Estados Unidos. p. 38. ISBN 978-0-88385-555-3. Número de serie LCCN  2005937266.
5. Gumm, H. (enero de 1985). "Una nueva clase de métodos de dígitos de control para sistemas numéricos arbitrarios (Corresp.)". IEEE Transactions on Information Theory . 31 (1): 102–105. doi :10.1109/TIT.1985.1056991.
6. Sisson, Roger L. (mayo de 1958). "Una comprobación de redundancia decimal mejorada". Comunicaciones de la ACM . 1 (5): 10–12. doi : 10.1145/368819.368854 .
7. 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 . Dígito de control de Verhoeff.
8. Verhoeff 1969, pág. 95
9. Verhoeff 1969, pág. 83

Enlaces externos

• Descripción detallada del algoritmo de Verhoeff