Jump to content

Verhoeff algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Richwales (talk | contribs) at 05:46, 16 April 2006 (New article on Verhoeff check digit algorithm). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 the dihedral group of order 10 — a non-commutative system of operations on ten elements, corresponding to the results of rotating and/or reflecting (flipping) a regular pentagon. In practice, however, the scheme can be implemented using precomputed lookup tables.

Informal explanation

(to be added later)

Algorithm

(to be added later)

Example

(to be added later)

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 (ab).
  • Transposition (switching) of two adjacent digits (abba).

Additionally, the Verhoeff algorithm detects most (but not all) occurrences of the following less common errors:

  • Twin errors (aabb).
  • Jump twin errors (acabcb).
  • Jump transpositions (abccba).
  • Phonetic errors (a01a; 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.