TheVerhoeff algorithm^[1] is achecksum forerror detection first published by Dutch mathematicianJacobus Verhoeff in 1969.^[2][3] It was the first decimalcheck digit algorithm that detects all single-digit errors, and all transposition errors involving two adjacent digits,^[4] 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 aformal proof and an extension to any base.^[5]

Verhoeff had the goal of finding a decimal code—one where the check digit is a single decimal digit—which detected all single-digit errors and all transpositions of adjacent digits. At the time, supposed proofs of the nonexistence^[6] of these codes made base-11 codes popular, for example in theISBN check digit.

His goals were also practical, and he based the evaluation of different codes on live data from the Dutch postal system, using a weighted points system for different kinds of error. The analysis broke the errors down into a number of categories: first, by how many digits are in error; for those with two digits in error, there aretranspositions (ab →ba),twins (aa →bb),jump transpositions (abc →cba),phonetic (1a →a0), andjump twins (aba →cbc). Additionally there are omitted and added digits. Although the frequencies of some of these kinds of errors might be small, some codes might be immune to them in addition to the primary goals of detecting all singles and transpositions.

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 thedihedral group D₅. That is, map digits to D₅, manipulate these, then map back into digits. Let this mapping bem : [0, 9] → D₅

Let thenth digit bea_n and let the number of digits bek.

For example given the code 942 thenk is 3 anda₃ =m(2) =r².

Now define the permutationf : D₅ → D₅

For example,${\displaystyle f(r^3)=rs}$. Another example is${\displaystyle f^2(r^3)=r^3}$ since${\displaystyle f(f(r^3))=f(rs)=r^3}$.

Using multiplicative notation for the group operation of D₅, the check digit is then simply a valuec such that

${\displaystyle f^0(c)\cdot f^1(a_k)\cdot \dots \cdot f^{k-1}(a_2)\cdot f^k(a_1)=e}$

c is explicitly given by multiplicative inverse:

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

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

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

To evaluate this permutation quickly use that

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

to get that

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

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

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

In practice, the algorithm is implemented using simplelookup tables without needing to understand how to generate those tables from the underlying group and permutation theory. This is more properly considered a family of algorithms, as other permutations work too. Verhoeff's notes that the particular permutation, given above, is special as it has the property of detecting 95.3% of the phonetic errors.^[8]

The strengths of the algorithm are that it detects all transliteration and transposition errors, and additionally most twin, twin jump, jump transposition and phonetic errors.

The main weakness of the Verhoeff algorithm is its complexity. The calculations required cannot easily be expressed as a formula in sayZ / 10Z. Lookup tables are required for easy calculation. A similar code is theDamm algorithm, which has similar qualities.

The Verhoeff algorithm can be implemented using three tables:a multiplication tabled, an inverse table inv, and a permutation tablep.

The first table,d, is based on multiplication in the dihedral group D₅.^[7] and is simply theCayley table of the group. Note that this group is notcommutative, that is, for some values ofj andk,d(j,k) ≠d(k,j).

The inverse tableinv represents themultiplicative inverse of a digit, that is, the value that satisfiesd(j, inv(j)) = 0.

The permutation tablep applies apermutation to each digit based on its position in the number. This is actually a single permutation(1 5 8 9 4 2 7 0)(3 6) applied iteratively; i.e.p(i +j,n) =p(i,p(j,n)).

The Verhoeff checksum calculation is performed as follows:

1. Create an arrayn out of the individual digits of the number, taken from right to left (rightmost digit isn₀, etc.).
2. Initialize the checksumc to zero.
3. For each indexi of the arrayn, starting at zero, replacec withd(c,p(i mod 8,n_i)).

The original number is valid if and only ifc = 0.

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

The Verhoeff algorithm is used in a variety of systems, including:

• GermanDeutschemark banknotes^[10]
• IndianAadhaar numbers^[11]
• Irish Meter Registration System Operator^[12]
• TheSNOMED Clinical Terms dictionary^[13]

• Luhn algorithm – Simple checksum formula
• Damm algorithm – Check digit algorithm

Wikibooks has a book on the topic of:Algorithm_Implementation/Checksums/Verhoeff_Algorithm

• Detailed description of the Verhoeff algorithmArchived 2006-04-26 at theWayback Machine

• Modular arithmetic
• Checksum algorithms
• Error detection and correction
• 1969 introductions

• Articles with short description
• Short description is different from Wikidata
• Webarchive template wayback links