Verhoeff algorithm

Verhoeff algorithm

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 does a better job than the Luhn algorithm, though, in that it will detect "all" "transposition" errors (switching of two adjacent digits), as well as catching many other types of errors that pass the Luhn formula undetected.

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 tables.

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
j 0 1 2 3 4 5 6 7 8 9
00123456789
11234067895
22340178956
33401289567
44012395678
55987604321
66598710432
77659821043
88765932104
99876543210

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.).

p(pos,num)num
pos 0 1 2 3 4 5 6 7 8 9
00123456789
11576283094
25803796142
38916043527
49453126870
54286573901
62793806415
77046913258

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)0432156789

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.

i ni p(i,ni) previous
c
new c =
d(c,p(i,ni))
00000
17000
25909
38297
42572
54527
61770

trengths 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. The involved nature of the Verhoeff check might especially be seen as a drawback "if" the client applications within a system need to explicitly report that an invalid ID has failed the check digit test (as opposed to an ID simply not being found in the system's database). If it is sufficient for a client to look up each ID in a master database and report malformed values as "not found," then only the piece of the system that issues new ID's needs to know how to do the Verhoeff calculations, and the complexity issue is mitigated.

References

* Verhoeff, J. “Error Detecting Decimal Codes”, Mathematical Centre Tract 29, The Mathematical Centre, Amsterdam, 1969.

External links

* [http://www.cs.utsa.edu/~wagner/laws/verhoeff.html Detailed description] of the Verhoeff algorithm
* [http://www.augustana.ab.ca/~mohrj/algorithms/checkdigit.html A description] using lookup tables
* [http://www.unsw.adfa.edu.au/admin/finance/guides/numeric_departments.pdf Another description] using lookup tables
* [http://search.cpan.org/~jpeterson/Algorithm-Verhoeff-0.3/lib/Algorithm/Verhoeff.pm Verhoeff implementation in Perl] (from CPAN)
* [http://en.dahnielson.com/2006/09/verhoeff.html Verhoeff implementation in PHP]
* [http://www.briandunning.com/cf/616 Verhoeff implementation in FileMaker Pro]
* [http://modp.com/release/checkdigits/ Verhoeff and others, implementation in Java, JavaScript]
* [http://www.stens.ca/kb/VerhoeffCheck Verhoeff implementation in MS SQL Server Transact SQL]
* [http://www.ams.org/featurecolumn/archive/verhoeff.html Biographical sketch] of Jacobus Verhoeff


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • 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… …   Wikipedia

  • Check digit — A check digit is a form of redundancy check used for error detection, the decimal equivalent of a binary checksum. It consists of a single digit computed from the other digits in the message. With a check digit, one can detect simple errors in… …   Wikipedia

  • Алгоритм Верхоффа — (Verhoeff)  алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 г. голландским математиком Якобом Верхоффом. Алгоритм позволяет выявить большее число… …   Википедия

  • Checksum — Effect of a typical checksum function (the Unix cksum utility). 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… …   Wikipedia

  • Error detection and correction — In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data (information) integrity across noisy channels and less than reliable storage… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

  • List of mathematics articles (V) — NOTOC Vac Vacuous truth Vague topology Valence of average numbers Valentin Vornicu Validity (statistics) Valuation (algebra) Valuation (logic) Valuation (mathematics) Valuation (measure theory) Valuation of options Valuation ring Valuative… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”