Example: The Verhoeff check digit scheme

We have seen in §3.3.2 the ISBN check digit scheme. This helps detect an error made in one of the digits. In 1969, J. Verhoeff [V] describes a check digit scheme using the dihedral group.

Let $ G=D_{10}$. This group has $ 10$ elements, each element corresponding to the digits $ 0, 1, ..., 9$. For example, if $ D_{10}=\{g[0],g[1],...,g[9]\}$ are the elements of $ G$ in some order (it will be typographically simpler, as you will see, to use $ g[i]$ instead of $ g_i$ for our notation) then we can associate $ i$ to $ g_i$. We let

\begin{displaymath} \begin{array}{c} D_{10}=\{ 1, (2,5)(3,4), (1,2)(3,5), (1,2,3... ...1,4)(2,3), (1,4,2,5,3), (1,5,4,3,2), (1,5)(2,4) \}, \end{array}\end{displaymath}

so for example $ g[0]=1$.

Verhoeff check digit scheme ([Ki], §5.4) Fix an integer $ n>1$ and fix an element $ \sigma$ in the symmetric group of the set $ \{0,1,...,9\}$. Let $ d_1d_2...d_n$ be a identification number without a check digit. The digit $ d_{n+1}$ is appended to $ d_1...d_{n}$ provided

$\displaystyle g[\sigma(d_1)] g[\sigma^{2}(d_2)]... g[\sigma^{n-1}(d_{n-1})] g[\sigma^{n}(d_{n})]g[d_{n+1}]=1. $

(Actually, Verhoeff uses decending powers of $ \sigma$ in his scheme. We use ascending powers since it is easier to remember and because the German Bundesbank used this version for the Deutsche Mark - see [Ki] for more details.)

Example 5.10.3   Let $ \sigma=(1,7,9)(2,5,10,4,6)$ and let $ n=5$.

Consider the ID number $ 12345$, what is the check digit? We compute $ g[\sigma(1)]=(1,2)(3,5)$, $ g[\sigma^2(2)] =(1,2,3,4,5)$, $ g[\sigma^3(3)]= (1,2)(3,5)$, $ g[\sigma^4(4)]= (2,5)(3,4)$, $ g[\sigma^5(5)]= (1,3,5,2,4)$. Thus $ d_6$ is determined by

$\displaystyle (1,2)(3,5)(1,2,3,4,5)(1,2)(3,5)(2,5)(3,4)(1,3,5,2,4) g[d_6]=1. $

Since $ ((1,2)(3,5)(1,2,3,4,5)(1,2)(3,5)(2,5)(3,4)(1,3,5,2,4))^{-1}= (1,4)(2,4)=g[7]$, we have $ d_6=7$. The ID number with check digit is $ 123457$.

Consider the ID number $ 75872$, what is the check digit? Answer: $ d_6=5$. The ID number with check digit is $ 758725$. We leave it as an exercise to check this (see Exercise 5.10.4).


David Joyner 2007-09-03