Verhoeff algorithm

The Verhoeff algorithm is a checksum for error detection first published by Dutch mathematician Jacobus Verhoeff in 1969. It was the first decimal check digit algorithm that detects all single-digit errors, and all transposition errors involving two adjacent digits, which was at the time thought impossible with such a code.

The method was independently discovered by H. Peter Gumm in 1985, this time including a formal proof and an extension to any base.

The phonetic errors in particular showed linguistic effects, because in Dutch, numbers are typically read in pairs; and also while 50 sounds similar to 15 in Dutch, 80 does not sound like 18.

Taking six-digit numbers as an example, Verhoeff reported the following classification of the errors:.

The general idea of the algorithm is to represent each of the digits (0 through 9) as elements of the dihedral group D5. That is, map digits to D5, manipulate these, then map back into digits. Let this mapping be 5</sub>"}},"i":0}}]}'>m : [0, 9] → D5

f : D5 → D5

f2(r3)=r3 since c=(∏n=1kfn(ak+1−n))−1

For example the check digit for 942 is 7. To verify this, use the mapping to D5 and insert into the LHS of the previous equation

r2s⋅r2s⋅r2s⋅r2s=e

This is the same reflection being iteratively multiplied. Use that reflections are their own inverse.

d k 0 1 2 3 4 5 6 7 8 9 j 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 0 6 7 8 9 5 2 2 3 4 0 1 7 8 9 5 6 3 3 4 0 1 2 8 9 5 6 7 4 4 0 1 2 3 9 5 6 7 8 5 5 9 8 7 6 0 4 3 2 1 6 6 5 9 8 7 1 0 4 3 2 7 7 6 5 9 8 2 1 0 4 3 8 8 7 6 5 9 3 2 1 0 4 9 9 8 7 6 5 4 3 2 1 0

j inv(j) 0 0 1 4 2 3 3 2 4 1 5 5 6 6 7 7 8 8 9 9

p num 0 1 2 3 4 5 6 7 8 9 pos (mod 8) 0 0 1 2 3 4 5 6 7 8 9 1 1 5 7 6 2 8 3 0 9 4 2 5 8 0 3 7 9 6 1 4 2 3 8 9 1 6 0 4 3 5 2 7 4 9 4 5 3 1 2 6 8 7 0 5 4 2 8 6 5 7 3 9 0 1 6 2 7 9 3 8 0 6 4 1 5 7 7 0 4 6 9 1 3 2 5 8

The first table, d, is based on multiplication in the dihedral group D5. and is simply the Cayley table of the group. Note that this group is not commutative, that is, for some values of j and k, d(j, inv(j)) = 0.

The permutation table p applies a permutation to each digit based on its position in the number. This is actually a single permutation p(i + j, n) = p(i, p(j, n)).

The Verhoeff checksum calculation is performed as follows:

1. Create an array n out of the individual digits of the number, taken from right to left (rightmost digit is n0, etc.).
2. Initialize the checksum c to zero.
3. For each index i of the array n, starting at zero, replace c with c = 0.

   To generate a check digit, append a 0, perform the calculation: the correct check digit is inv(c).

   Examples

   edit
   i</sub>''\n! style=\"background:#ffc\" | ''p''(''i'', ''n_i'')\n! style=\"background:#ffc\" | ''c''\n|-\n|0||0||0||0\n|-\n|1||6||3||3\n|-\n|2||3||3||1\n|-\n|3||2||1||2\n|}\n''c'' is 2, so the check digit is inv(2), which is 3.\n",{"template":{"target":{"wt":"col-2","href":"./Template:Col-2"},"params":{},"i":2}},"\n'''Validate''' the check digit in 2363:\n{| class=\"wikitable\" style=\"text-align:center\"\n|-\n! style=\"background:#ffc\" | ''i''\n! style=\"background:#ffc\" | ''n_i''\n! style=\"background:#ffc\" | ''p''(''i'', ''n_i'')\n! style=\"background:#ffc\" | ''c''\n|-\n|0||3||3||3\n|-\n|1||6||3||1\n|-\n|2||3||3||4\n|-\n|3||2||1||0\n|}\n''c'' is zero, so the check is correct.\n",{"template":{"target":{"wt":"col-end","href":"./Template:Col-end"},"params":{},"i":3}}]}'>Kirtland, Joseph (2001). "5. Group Theory and the Verhoeff Check Digit Scheme". Identification Numbers and Check Digit Schemes. Mathematical Association of America. p. 153. ISBN 0-88385-720-0.
4. ↑ Gumm, H. (January 1985). "A new class of check-digit methods for arbitrary number systems (Corresp.)". IEEE Transactions on Information Theory. 31 (1): 102–105. doi:10.1109/TIT.1985.1056991.
5. ↑ "EIMI 2010 Proceedings" (PDF). Freudenthal Institute, Utrecht University. Lisbon, Portugal: Educational Interfaces between Mathematics and Industry. 2010. p. 128. doi:10.1007/978-3-319-02270-3. Archived from the original (PDF) on 16 May 2024. Retrieved 13 September 2025.
6. ↑ "Check digit computation". docs.snomed.org. SNOMED International. Archived from the original (Official Documentation) on 13 September 2025. Retrieved 13 September 2025.

External links