by Neal R. Wagner
Copyright © 2002 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
In 1969, a Dutch mathematician named Verhoeff carried out a study of errors made by humans in handling decimal numbers. He identified the following principal types:
Verhoeff had the clever idea to use some other method besides addition modulo 10 for combining the integers from 0 to 9. Instead he used the operation of a group known as the dihedral group D_{5}, represented by the symmetries of a pentagon, which has ten elements that one can name 0 through 9. The discussion here will use # for the group operation and 0 for the identity element. This is not a commutative group, so that a # b will not always equal b # a. Here is the multiplication table for this group. (Each table entry gives the result of the bold table entry on the left combined with the bold table entry across the top, written left to right. The red italic entries show results which are not commutative.)
# | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ||
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 |
The reader should realize that D_{5} is a complex entity whose elements are somewhat arbitrarily mapped to the integers from 0 to 9, and the group operation # is not at all like addition or multiplication. Keep in mind that the ten symbols 0 through 9 are the only symbols in the group. When two are combined, you get another of them. There is no number 29, but only separate group elements 2 and 9 that could be combined in two ways: 2 # 9 = 6 and 9 # 2 = 7. There is no concept of order such as < or > in this group. The five numbers 0 through 4 combine in the group just as they do with addition in the group Z_{5}, but the remaining numbers are quite different, since each of 5, 6, 7, 8, and 9 is its own inverse. (With ordinary addition in Z_{10}, only 5 is its own inverse.)
If one just used the check equation
where # is the group operation in D_{5}, this would be much better than simply adding the digits modulo 10, since in both cases single errors are caught, but in D_{5} two-thirds of adjacent transpositions are caught (60 out of 90, represented by the red entries in the table above), whereas ordinary addition catches no transpositions. This suggests that stirring things up a little more would give the answer.
Verhoeff considered check equations of the form
where each f_{i} is a permutation of the ten digits. He was able to get an excellent check in the special case where f_{i} is the ith iteration of a fixed permutation f. As the Java implementation will show, this check is not hard to program and is efficient, but it employs several tables and could not be carried out by hand as all the earlier checks could. This discussion will employ Java notation to keep the subscripts straight. First the check needs the group operation, defined as a two-dimensional array op[i][j], for i and j going from 0 to 9 giving the result of combining the two numbers in D_{5} (the same as the table above):
int[][] op= { {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, {1, 2, 3, 4, 0, 6, 7, 8, 9, 5}, {2, 3, 4, 0, 1, 7, 8, 9, 5, 6}, {3, 4, 0, 1, 2, 8, 9, 5, 6, 7}, {4, 0, 1, 2, 3, 9, 5, 6, 7, 8}, {5, 9, 8, 7, 6, 0, 4, 3, 2 ,1}, {6, 5, 9, 8, 7, 1, 0, 4, 3, 2}, {7, 6, 5, 9, 8, 2, 1, 0, 4, 3}, {8, 7, 6, 5, 9, 3, 2, 1, 0, 4}, {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} };Then comes an array Inv, where Inv[i] gives the inverse of each digit i in D_{5}:
int[] inv = {0, 4, 3, 2, 1, 5, 6, 7, 8, 9};Finally, the check requires another two-dimensional array giving the special permutation and iterations of it:
int[][] F = new int[8][]; F[0] = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // identity permutation F[1] = new int[]{1, 5, 7, 6, 2, 8, 3, 0, 9, 4}; // "magic" permutation for (int i = 2; i < 8; i++) { // iterate for remaining permutations F[i] = new int[10]; for (int j = 0; j < 10; j++) F[i][j] = F[i-1] [F[1][j]]; }Now the check equation takes the form:
public static boolean doCheck(int[] a) { int check = 0; for (int i = 0; i < a.length; i++) check = op[check][ F[i % 8][a[i]] ]; if (check != 0) return false; else return true; }The check digit can be inserted in position a[0] using the array Inv, as is show in the actual implementation later in this section.
Verhoeff's check above catches all single errors and all adjacent transpositions. It also catches 95.555% of twin errors, 94.222% of jump transpositions and jump twin errors, and 95.3125% percent of phonetic errors (assuming a ranges from 2 to 9).
Law DECIMAL2: It is possible to use a single check digit to detect all single errors and all adjacent transpositions, and nobody uses this method.
Verhoeff's Scheme (all transpositions detected): Java source.