Verhoeff algorithm
Encyclopedia
The Verhoeff algorithm, a checksum
formula for error detection first published in 1969, was developed by Dutch mathematician Jacobus Verhoeff (born 1927). Like the more widely known Luhn algorithm
, it works with strings of decimal
digits of any length. It detects all single-digit errors and all transposition errors involving two adjacent digits.
Verhoeff devised his algorithm using the properties of D5 (the dihedral group
of order 10) — a non-commutative system of operations on ten elements, corresponding to the results of rotating or reflecting (flipping) a regular pentagon. In practice, however, the scheme would normally be implemented using precomputed lookup table
s.
a multiplication table d, a permutation table p, and an inverse table inv.
The first table, d, is based on multiplication in the dihedral group D5.
The second table, p, applies a permutation
to each digit based on its position in the number. The positions of the digits are counted from right to left, starting with zero. The permutation repeats after eight rows (the row for pos=8 is identical to the row for pos=0, etc.). Storage space can be reduced using the fact that 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 third table, inv, represents the multiplicative inverse of a digit in the dihedral group D5: in other words, for any j, the inv table shows the value k such that d(j,k) = 0.
The original number has a valid check digit if and only if c = 0.
If the original number ends in a zero (i.e., n0 = 0), then inv(c) is the proper value to use as the check digit in place of the final zero.
The first step is to break up the number into an array n = [0,7,5,8,2,4,1], in which the digits are listed in reverse order (right to left). Then, the other values in the formula are computed in sequence. Since the final value of c is zero, the check digit is valid.
Additionally, the Verhoeff algorithm detects most (but not all) occurrences of the following less common errors:
The main weakness of the Verhoeff algorithm is its complexity. Unlike the Luhn algorithm, the calculations required for a Verhoeff check digit cannot readily be performed by hand from memory.
Checksum
A checksum or hash sum is a fixed-size datum computed from an arbitrary block of digital data for the purpose of detecting accidental errors that may have been introduced during its transmission or storage. The integrity of the data can be checked at any later time by recomputing the checksum and...
formula for error detection first published in 1969, was developed by Dutch mathematician Jacobus Verhoeff (born 1927). Like the more widely known Luhn algorithm
Luhn algorithm
The Luhn algorithm or Luhn formula, also known as the "modulus 10" or "mod 10" algorithm,is a simple checksum formula used to validate a variety of identification numbers, such as credit card numbers, IMEI numbers, National Provider Identifier numbers in US and Canadian Social Insurance Numbers...
, it works with strings of decimal
Decimal
The decimal numeral system has ten as its base. It is the numerical base most widely used by modern civilizations....
digits of any length. It detects all single-digit errors and all transposition errors involving two adjacent digits.
Verhoeff devised his algorithm using the properties of D5 (the dihedral group
Dihedral group
In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.See also: Dihedral symmetry in three...
of order 10) — a non-commutative system of operations on ten elements, corresponding to the results of rotating or reflecting (flipping) a regular pentagon. In practice, however, the scheme would normally be implemented using precomputed lookup table
Lookup table
In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than...
s.
Tables
The Verhoeff algorithm can be implemented using three tables:a multiplication table d, a permutation table p, and an inverse table inv.
The first table, d, is based on multiplication in the dihedral group D5.
| d(j,k) | 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 | |
The second table, p, applies a permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
to each digit based on its position in the number. The positions of the digits are counted from right to left, starting with zero. The permutation repeats after eight rows (the row for pos=8 is identical to the row for pos=0, etc.). Storage space can be reduced using the fact that 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)).
| p(pos,num) | 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 third table, inv, represents the multiplicative inverse of a digit in the dihedral group D5: in other words, for any j, the inv table shows the value k such that d(j,k) = 0.
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| inv(j) | 0 | 4 | 3 | 2 | 1 | 5 | 6 | 7 | 8 | 9 |
Algorithm
Using the above tables, the following procedure will perform the Verhoeff checksum calculation on a number.- Create an array n out of the individual digits of the number, taken from right to left (rightmost digit is n0, etc.).
- Initialize the checksum c to zero.
- For each index i of the array n, starting at zero, replace c with d(c, p(i, ni)).
The original number has a valid check digit if and only if c = 0.
If the original number ends in a zero (i.e., n0 = 0), then inv(c) is the proper value to use as the check digit in place of the final zero.
Example
Validate the checksum for the number 1428570.The first step is to break up the number into an array n = [0,7,5,8,2,4,1], in which the digits are listed in reverse order (right to left). Then, the other values in the formula are computed in sequence. Since the final value of c is zero, the check digit is valid.
| ni | previous c | new c = d(c,p(i,ni)) | ||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 7 | 0 | 0 | 0 |
| 2 | 5 | 9 | 0 | 9 |
| 3 | 8 | 2 | 9 | 7 |
| 4 | 2 | 5 | 7 | 2 |
| 5 | 4 | 5 | 2 | 7 |
| 6 | 1 | 7 | 7 | 0 |
Strengths and weaknesses
The Verhoeff algorithm will detect all occurrences of the following common transcription errors in a number:- Replacement of a single digit by a different digit (a → b).
- Transposition (switching) of two adjacent digits (ab → ba).
Additionally, the Verhoeff algorithm detects most (but not all) occurrences of the following less common errors:
- Twin errors (aa → bb).
- Jump twin errors (aca → bcb).
- Jump transpositions (abc → cba).
- Phonetic errors (a0 ↔ 1a; e.g.; "sixty" ↔ "sixteen").
The main weakness of the Verhoeff algorithm is its complexity. Unlike the Luhn algorithm, the calculations required for a Verhoeff check digit cannot readily be performed by hand from memory.
External links
- Detailed description of the Verhoeff algorithm
- A description using lookup tables
- Verhoeff implementation in Perl (from CPANCPANCPAN, the Comprehensive Perl Archive Network, is an archive of nearly 100,000 modules of software written in Perl, as well as documentation for it. It has a presence on the World Wide Web at and is mirrored worldwide at more than 200 locations...
) - Verhoeff implementation in FileMaker Pro
- Verhoeff implementation in MS SQL Server Transact SQL
- Biographical sketch of Jacobus Verhoeff
- Verhoeff validation & generation code in C++
- Verhoeff validation & generation code in Javascript
- Verhoeff validation & generation code in C#, VB.NET, VBA, Java, Python and D