View source for Verhoeff algorithm

{{short description|Decimal error detection code}}
The '''Verhoeff algorithm'''<ref name="Verhoeff_1969" /> is a [[Checksum|checksum]] for error detection first published by Dutch mathematician Jacobus Verhoeff in 1969.<ref name=Kirtland_2001 /><ref name=Salomon_2005 />  It was the first decimal [[Check digit|check digit]] algorithm that detects all single-digit errors, and all transposition errors involving two adjacent digits,<ref name=Haunsperger_2006 /> 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 a [[Formal proof|formal proof]] and an extension to any base.<ref>{{cite journal |last1=Gumm |first1=H. |title=A new class of check-digit methods for arbitrary number systems (Corresp.) |journal=IEEE Transactions on Information Theory |date=January 1985 |volume=31 |issue=1 |pages=102–105 |doi=10.1109/TIT.1985.1056991 |url=https://www.researchgate.net/publication/3084126 }}</ref>

== Goals ==
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<ref name=Sisson_1958 /> of these codes made base-11 codes popular, for example in the [[International Standard Book Number#Check digits|ISBN 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 are ''transpositions'' ({{nowrap|''ab'' → ''ba''}}), ''twins'' ({{nowrap|''aa'' → ''bb''}}), ''jump transpositions'' ({{nowrap|''abc'' → ''cba''}}), ''phonetic'' ({{nowrap|''1a'' → ''a0''}}), and ''jump twins'' ({{nowrap|''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:.
{| class="wikitable"
|- valign="middle"
! style="background:#ffc" | Digits in error
! style="background:#ffc" | Classification
! style="background:#ffc" | Count
! style="background:#ffc" | Frequency
|-
|style="background:#ffc" |1||style="background:#ffc" |Transcription||align="right"|9,574||align="right"|79.05%
|-
|style="background:#ffc" rowspan=8 |2||style="background:#ffc" |Transpositions||align="right"|1,237||align="right"|10.21%
|-
|style="background:#ffc" |Twins||align="right"|67||align="right"|0.55%
|-
|style="background:#ffc" |Phonetic||align="right"|59||align="right"|0.49%
|-
|style="background:#ffc" |Other adjacent||align="right"|232||align="right"|1.92%
|-
|style="background:#ffc" |Jump transpositions||align="right"|99||align="right"|0.82%
|-
|style="background:#ffc" |Jump Twins||align="right"|35||align="right"|0.29%
|-
|style="background:#ffc" |Other jump errors||align="right"|43||align="right"|0.36%
|-
|style="background:#ffc" |Other||align="right"|98||align="right"|0.81%
|-
|colspan=2 style="background:#ffc" |3||align="right"|169||align="right"|1.40%
|-
|colspan=2 style="background:#ffc" |4||align="right"|118||align="right"|0.97%
|-
|colspan=2 style="background:#ffc" |5||align="right"|219||align="right"|1.81%
|-
|colspan=2 style="background:#ffc" |6||align="right"|162||align="right"|1.34%
|-
|colspan=2 style="background:#ffc" |'''Total''' || align="right"|'''12,112'''
|
|}

== Description ==
The general idea of the algorithm is to represent each of the digits (0 through 9) as elements of the [[Dihedral group|dihedral group]] D<sub>5</sub>. That is, map digits to D<sub>5</sub>, manipulate these, then map back into digits. Let this mapping be {{nowrap|''m'' : [0, 9] → D<sub>5</sub>}}
: <math>m = \begin{pmatrix}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9\\
e & r & r^2 & r^3 & r^4 & s & rs & r^2s & r^3s & r^4s\end{pmatrix}
</math>

Let the ''n''th digit be ''a''<sub>''n''</sub> and let the number of digits be ''k''.

For example given the code 942 then ''k'' is 3 and {{nowrap|1=''a''<sub>3</sub> = ''m''(2) = ''r''<sup>2</sup>}}. 

Now define the permutation {{nowrap|''f'' : D<sub>5</sub> → D<sub>5</sub>}}
: <math>f = \begin{pmatrix}
e & r & r^2 & r^3 & r^4 & s & rs & r^2s & r^3s & r^4s\\
r & s & r^2s & rs & r^2 & r^3s & r^3 & e & r^4s & r^4\end{pmatrix}
</math>

For example, <math>f(r^3) = rs</math>. Another example is <math>f^2(r^3) = r^3</math> since <math>f(f(r^3)) = f(rs) = r^3</math>.

Using multiplicative notation for the group operation of D<sub>5</sub>, the check digit is then simply a value ''c'' such that
: <math> f^0(c) \cdot f^1(a_k) \cdot \ldots \cdot f^{k-1}(a_2) \cdot f^k(a_1) = e</math>

''c'' is explicitly given by multiplicative inverse:
: <math>c = \left(\prod_{n=1}^k f^n(a_{k+1-n})\right)^{-1}</math>

For example the check digit for 942 is 7. To verify this, use the mapping to D<sub>5</sub> and insert into the LHS of the previous equation
: <math> f^0(r^{2}s) \cdot f^1(r^2) \cdot f^2(r^4) \cdot f^3(r^{4}s) = e</math>

To evaluate this permutation quickly use that
: <math> f^3(r^4s) = f^2(r^4) = f^1(r^2) = f^0(r^2 s) = r^2 s</math>
to get that
: <math> r^2 s \cdot r^2 s \cdot r^2 s \cdot r^2 s = e</math>

This is the same reflection being iteratively multiplied. Use that reflections are their own inverse.<ref name="Gallian_2010" />
: <math> (r^2 s \cdot r^2 s) \cdot (r^2 s \cdot r^2 s) = e^2 = e</math>

In practice, the algorithm is implemented using simple [[Lookup table|lookup table]]s 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.<ref>{{harvnb|Verhoeff|1969|p=95}}</ref>

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 say {{nowrap|'''Z''' / 10'''Z'''}}. Lookup tables are required for easy calculation. A similar code is the [[Damm algorithm]], which has similar qualities.

== Table-based algorithm ==
The Verhoeff algorithm can be implemented using three tables:
a multiplication table ''d'', an inverse table inv, and a permutation table ''p''.

{{col-begin}}
{{col-break}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! rowspan=2 colspan=2 style="background:#ffc" | ''d''<ref>{{harvnb|Verhoeff|1969|p=83}}</ref>
! colspan=10  | ''k''
|- valign="middle"
! style="background:#ffc; width:1em" |  0
! style="background:#ffc; width:1em" |  1
! style="background:#ffc; width:1em" |  2
! style="background:#ffc; width:1em" |  3
! style="background:#ffc; width:1em" |  4
! style="background:#ffc; width:1em" |  5
! style="background:#ffc; width:1em" |  6
! style="background:#ffc; width:1em" |  7
! style="background:#ffc; width:1em" |  8
! style="background:#ffc; width:1em" |  9
|- valign="middle"
! rowspan=10 style="width:1em" | ''j''
! style="background:#ffc; width:1em" |  0
| 0 || 1|| 2 || 3|| 4 || 5|| 6 || 7|| 8 || 9
|- valign="bottom"
! style="background:#ffc" | 1
| 1|| 2 || 3|| 4 || 0|| 6 || 7|| 8 || 9|| 5
|- valign="bottom"
! style="background:#ffc" | 2
| 2|| 3 || 4|| 0 || 1|| 7 || 8|| 9 || 5|| 6
|- valign="bottom"
! style="background:#ffc" | 3
| 3|| 4 || 0|| 1 || 2|| 8 || 9|| 5 || 6|| 7
|- valign="bottom"
! style="background:#ffc" | 4
| 4|| 0 || 1|| 2 || 3|| 9 || 5|| 6 || 7|| 8
|- valign="bottom"
! style="background:#ffc" | 5
| 5|| 9 || 8|| 7 || 6|| 0 || 4|| 3 || 2|| 1
|- valign="bottom"
! style="background:#ffc" | 6
| 6|| 5 || 9|| 8 || 7|| 1 || 0|| 4 || 3|| 2
|- valign="bottom"
! style="background:#ffc" | 7
| 7|| 6 || 5|| 9 || 8|| 2 || 1|| 0 || 4|| 3
|- valign="bottom"
! style="background:#ffc" | 8
| 8|| 7 || 6|| 5 || 9|| 3 || 2|| 1 || 0|| 4
|- valign="bottom"
! style="background:#ffc" | 9
| 9|| 8 || 7|| 6 || 5|| 4 || 3|| 2 || 1|| 0
|}
{{col-break|gap=1em}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! style="background:#ffc; width:1em; height:3.5em;" |  ''j''
! style="width:1em; height:3.5em;" |  inv(''j'')
|-
! style="background:#ffc; width:1em" |  0
| 0
|- valign="bottom"
! style="background:#ffc" | 1
| 4
|- valign="bottom"
! style="background:#ffc" | 2
| 3
|- valign="bottom"
! style="background:#ffc" | 3
| 2
|- valign="bottom"
! style="background:#ffc" | 4
| 1
|- valign="bottom"
! style="background:#ffc" | 5
| 5
|- valign="bottom"
! style="background:#ffc" | 6
| 6
|- valign="bottom"
! style="background:#ffc" | 7
| 7
|- valign="bottom"
! style="background:#ffc" | 8
| 8
|- valign="bottom"
! style="background:#ffc" | 9
| 9
|}
{{col-break|gap=1em}}
{| class="wikitable" style="text-align:center"
|- valign="middle"
! rowspan=2 colspan=2 style="background:#ffc" | ''p''
! colspan=10 | ''num''
|- valign="middle"
! style="background:#ffc; width:1em" |  0
! style="background:#ffc; width:1em" |  1
! style="background:#ffc; width:1em" |  2
! style="background:#ffc; width:1em" |  3
! style="background:#ffc; width:1em" |  4
! style="background:#ffc; width:1em" |  5
! style="background:#ffc; width:1em" |  6
! style="background:#ffc; width:1em" |  7
! style="background:#ffc; width:1em" |  8
! style="background:#ffc; width:1em" |  9
|- valign="middle"
! rowspan=8 {{verth|va=middle| {{math| ''pos'' (mod 8)}} }}
! style="background:#ffc; width:1em" |  0
| 0 || 1|| 2 || 3|| 4 || 5|| 6 || 7|| 8 || 9
|- valign="bottom"
! style="background:#ffc" | 1
| 1|| 5 || 7|| 6 || 2|| 8 || 3|| 0 || 9|| 4
|- valign="bottom"
! style="background:#ffc" | 2
| 5|| 8 || 0|| 3 || 7|| 9 || 6|| 1 || 4|| 2
|- valign="bottom"
! style="background:#ffc" | 3
| 8|| 9 || 1|| 6 || 0|| 4 || 3|| 5 || 2|| 7
|- valign="bottom"
! style="background:#ffc" | 4
| 9|| 4 || 5|| 3 || 1|| 2 || 6|| 8 || 7|| 0
|- valign="bottom"
! style="background:#ffc" | 5
| 4|| 2 || 8|| 6 || 5|| 7 || 3|| 9 || 0|| 1
|- valign="bottom"
! style="background:#ffc" | 6
| 2|| 7 || 9|| 3 || 8|| 0 || 6|| 4 || 1|| 5
|- valign="bottom"
! style="background:#ffc" | 7
| 7|| 0 || 4|| 6 || 9|| 1 || 3|| 2 || 5|| 8
|}
{{col-end}}

The first table, ''d'', is based on multiplication in the dihedral group D<sub>5</sub>.<ref name=Gallian_2010 /> and is simply the [[Cayley table]] of the group.  Note that this group is not commutative, that is, for some values of ''j'' and ''k'', {{nowrap|''d''(''j'',''k'') ≠ ''d''(''k'', ''j'')}}.

The inverse table '''inv''' represents the [[Multiplicative inverse|multiplicative inverse]] of a digit, that is, the value that satisfies {{nowrap|1=''d''(''j'', inv(''j'')) = 0}}.

The permutation table '''''p''''' applies a [[Permutation|permutation]] to each digit based on its position in the number. This is actually a single permutation {{nowrap|(1 5 8 9 4 2 7 0)(3 6)}} applied iteratively; i.e. {{nowrap|1=''p''(''i'' + ''j'', ''n'') = ''p''(''i'', ''p''(''j'', ''n''))}}.

The Verhoeff checksum calculation is performed as follows:
# Create an array ''n'' out of the individual digits of the number, taken from right to left (rightmost digit is ''n''<sub>0</sub>, etc.).
# Initialize the checksum ''c'' to zero.
# For each index ''i'' of the array ''n'', starting at zero, replace ''c'' with {{nowrap|''d''(''c'', ''p''(''i'' mod 8, ''n''<sub>''i''</sub>))}}.

The original number is valid if and only if {{nowrap|1=''c'' = 0}}.

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

== Examples ==
{{col-begin}}
{{col-2}}
'''Generate''' a check digit for ''236'':
{| class="wikitable" style="text-align:center"
|-
! style="background:#ffc" | ''i''
! style="background:#ffc" | ''n<sub>i</sub>''
! style="background:#ffc" | ''p''(''i'', ''n<sub>i</sub>'')
! style="background:#ffc" | ''c''
|-
|0||0||0||0
|-
|1||6||3||3
|-
|2||3||3||1
|-
|3||2||1||2
|}
''c'' is 2, so the check digit is inv(2), which is 3.
{{col-2}}
'''Validate''' the check digit in 2363:
{| class="wikitable" style="text-align:center"
|-
! style="background:#ffc" | ''i''
! style="background:#ffc" | ''n<sub>i</sub>''
! style="background:#ffc" | ''p''(''i'', ''n<sub>i</sub>'')
! style="background:#ffc" | ''c''
|-
|0||3||3||3
|-
|1||6||3||1
|-
|2||3||3||4
|-
|3||2||1||0
|}
''c'' is zero, so the check is correct.
{{col-end}}

== Uses ==
The Verhoeff algorithm is used in a variety of systems, including:
* German Deutschemark banknotes <ref>{{cite web |title=EIMI 2010 Proceedings |url=http://www.fi.uu.nl/publicaties/literatuur/2010_eimi_proceedings.pdf |website=Freudenthal Institute, Utrecht University |publisher=Educational Interfaces between Mathematics and Industry |access-date=13 September 2025 |archive-url=https://web.archive.org/web/20240516203235/http://www.fi.uu.nl/publicaties/literatuur/2010_eimi_proceedings.pdf |archive-date=16 May 2024 |location=Lisbon, Portugal |page=128 |language=English |doi=10.1007/978-3-319-02270-3 |date=2010 }}</ref>
* [[Place:India|Indian]] [[Biology:Aadhaar|Aadhaar]] numbers <ref>{{cite web |last1=Surelia |first1=Vipin |title=Implementation of Verhoeff Algorithm by banks for Aadhaar related applications |url=https://www.npci.org.in/PDF/nach/circular/2013-14/Circular_No_9.pdf |website=npci.org.in |publisher=National Payments Corporation of India |access-date=10 September 2025 |archive-url=https://web.archive.org/web/20250910204938/https://www.npci.org.in/PDF/nach/circular/2013-14/Circular_No_9.pdf |archive-date=10 September 2025 |page=1 |format=Official Circular }}</ref>
* Irish Meter Registration System Operator <ref>{{cite web |title=Meter Point Reference Number (MPRN) |url=http://www.mrso.ie/about_mrso/mprn.htm |website=mrso.ie |publisher=Meter Registration System Operator, Ireland |access-date=13 September 2025 |archive-url=https://web.archive.org/web/20250913093809/http://www.mrso.ie/about_mrso/mprn.htm |archive-date=13 September 2025 }}</ref>
* The SNOMED Clinical Terms dictionary <ref>{{cite web |title=Check digit computation |url=https://docs.snomed.org/snomed-ct-specifications/snomed-ct-release-file-specification/snomed-ct-identifiers/6.4-check-digit/6.4.2-check-digit-computation |website=docs.snomed.org |publisher=SNOMED International |access-date=13 September 2025 |archive-url=https://web.archive.org/web/20250913095138/https://docs.snomed.org/snomed-ct-specifications/snomed-ct-release-file-specification/snomed-ct-identifiers/6.4-check-digit/6.4.2-check-digit-computation |archive-date=13 September 2025 |format=Official Documentation }}</ref>

== See also ==
* {{annotated link|Luhn algorithm}}
* {{annotated link|Damm algorithm}}

== References ==
<references>

<ref name="Verhoeff_1969">
{{cite journal |title=Error Detecting Decimal Codes (Tract 29) |last=Verhoeff |first=J. |journal=Zeitschrift für Angewandte Mathematik und Mechanik |publisher=The Mathematical Centre, Amsterdam |year=1969 |volume=51 |issue=3 |page=240 |doi=10.1002/zamm.19710510323 |bibcode=1971ZaMM...51..240N }}</ref>

<ref name=Kirtland_2001>{{cite book |title=Identification Numbers and Check Digit Schemes |last=Kirtland |first=Joseph | publisher=Mathematical Association of America |year=2001 |page=153 |isbn=0-88385-720-0 |chapter=5. Group Theory and the Verhoeff Check Digit Scheme |chapter-url=https://books.google.com/books?id=npTxORxmLosC&pg=PA121 }}</ref>

<ref name=Salomon_2005>{{cite book |title=Coding for Data and Computer Communications |last=Salomon |first=David |publisher=Springer |year=2005 |isbn=0-387-21245-0 |pages=56–58 |chapter=§2.11 The Verhoeff Check Digit Method |chapter-url=https://books.google.com/books?id=A88kvYwIVu0C&pg=PA57 }}</ref>

<ref name=Haunsperger_2006>{{cite book |title=The Edge of the Universe: Celebrating Ten Years of Math Horizons |editor1-last=Haunsperger |editor1-first=Deanna |editor2-last=Kennedy |editor2-first=Stephen |publisher=Mathematical Association of America |year=2006 |isbn=978-0-88385-555-3 |lccn=2005937266 |url=https://books.google.com/books?id=jiaIeCUpoFwC&pg=PA39 |page=38 }}</ref>

<ref name=Sisson_1958>{{cite journal |first=Roger L. |last=Sisson |title=An improved decimal redundancy check |journal=Communications of the ACM |volume=1 |issue=5 |pages=10–12 |date=May 1958 |doi=10.1145/368819.368854 |url=|doi-access=free }}</ref>

<ref name=Gallian_2010>{{cite book |title=Contemporary Abstract Algebra |edition=7th |last=Gallian |first=Joseph A. |publisher=Brooks/Cole |year=2010 |isbn=978-0-547-16509-7 |lccn=2008940386 |page=[https://archive.org/details/contemporaryabst00gall_1/page/111 111] |url=https://archive.org/details/contemporaryabst00gall_1 |url-access=registration |quote=verhoeff check digit. |access-date=August 26, 2011 }}</ref>

</references>

== External links ==
{{wikibooks|Algorithm_Implementation/Checksums/Verhoeff_Algorithm}}
* [http://www.cs.utsa.edu/~wagner/laws/verhoeff.html Detailed description of the Verhoeff algorithm] {{webarchive|url=https://web.archive.org/web/20060426102358/http://www.cs.utsa.edu/~wagner/laws/verhoeff.html |date=2006-04-26 }}

{{DEFAULTSORT:Verhoeff Algorithm}}
[[Category:Modular arithmetic]]
[[Category:Checksum algorithms]]
[[Category:Error detection and correction]]

{{Sourceattribution|Verhoeff algorithm}}