A new check digit algorithm using the dihedral group

As part of the process of handing in my PhD thesis, I was required to get myself an ISBN. It made me ask myself what ISBN really is. Who implemented it? What do the numbers mean? It turns out that a great deal of information can be inferred from an ISBN — but for the purposes of this post I would like to confine myself entirely to a single digit in the ISBN, which is the check digit: a digit whose purpose is to detect typos as often as possible.

The goal of this post, then, is to introduce the notion of a check digit, and to review some well-known algorithms, along with their real-life uses. I will put these algorithms to the test to see how well they perform against randomly generated errors. Along the way, we will find an improved (in a precise but imperfect sense) version of a famous algorithm of Verhoeff. Moreover, I will propose a new algorithm, closely related to Verhoeff’s algorithm, which eliminates the need for multiplication tables while still retaining great error detection properties.

Problem statement

The essence of the problem is easy enough to state. Find an algorithm which, given a sequence of digits, appends one more digit, known as the check digit, whose job it is to detect common errors.

What do we mean by common errors? We are referring here to any error which can occur for instance when a barcode is scanned incorrectly, or when numbers are written or typed in the wrong order. In 1969, Jacobus Verhoeff, whom we will soon see again, published a classification of common error types, along with their relative frequencies. I have reproduced the classification below.

Notice that the phonetic error type clearly depends on language. It occurs because, for instance, ‘fourteen’ sounds a lot like ‘forty’.

The goal, then, is to device an algorithm producing a single check digits which is capable of detecting as many of the above-mentioned error types as possible, and at the very least the two most common types.

Common algorithms

A common check digit algorithm is known as the mod-10 algorithm or the Luhn algorithm, named after its creator Hans Peter Luhn. The check digit is computed as follows.

• Start with the rightmost digit. Moving left, double the value of every second digit, including the rightmost digit.
• Compute the sum $s$ of the digits of the resulting value in each position, using the original value where a digit did not get doubled.
• The check digit is $10 - s$ modulo $10$.

For instance, consider an account number $1872$. Then the sum is \[ s = 4 + 7 + (1 + 6) + 1 \equiv 9 \, (10) \text{,} \] so the check digit is $1$.

The strength of the mod-10 algorithm lies in its simplicity. It detects single digit errors as well nearly all adjacent-digit transpositions, with the exception of the transposition $90 \leftrightarrow 09$. However, misses many twin errors, phonetic errors, and jump twin errors, such as $22 \leftrightarrow 55$, $18 \leftrightarrow 80$, and $828 \leftrightarrow 323$, and it misses all jump transpositions. I refer you to the appendix for the precise numbers.

The algorithm was patented way back in 1960, a time in which computational simplicity was more crucial than it is now. Nonetheless, to this day, the Luhn algorithm is still used all over the place to validate identification numbers. For instance, it occurs as the last (15^th) digit of the IMEI of your phone.^{Note 1}

A weaker variant of the mod-10 algorithm is employed by the Universal Product Code, a barcode convention, and by the book identifier ISBN-13. It proceeds as follows.

• Sum the digits at odd-numbered positions, and multiply the result by $3$.
• Add the digit sum at the even-numbered positions; call the resulting sum $s$.
• The check digit is $10 - s$ mod $10$.

So for instance, an account number $2994$ has sum \[ s = (3 \times 2) + 9 + (3 \times 9) + 4 \equiv 6 \, (10)\text{,} \] so the check digit is $4$.

The added value of this algorithm over the one divised by Luhn is that it does not involve taking digit sums. It is also capable of detecting all phonetic errors, making it arguably more useful for codes which are often communicated over the phone. However, it is significantly worse at detecting the more common transposition errors. Numbers can again be found in the appendix.

Somewhat ironically, the older book identifier ISBN-10 uses a more powerful checksum algorithm than its successor. This algorithm is sometimes called the mod-11 algorithm, and it’s capable of detecting all single-digit errors and transpositions, at the cost of having to introduce an 11^th symbol.^{Note 2}

The algorithm proceeds as follows. If $x_i$ is the $i$-th digit of ISBN-10, then the check digit $x_{10}$ must be chosen such that \[ 10 x_1 + 9 x_2 + \cdots + 2 x_{9} + 1x_{10} \equiv 0 \,(11) \text{.} \]

This mod-11 algorithm outperforms the mod-10 algorithms in that it can detect all transpositions as well as all jump transpositions (which completely evade detection by the mod-10 algorithms). It does however, perform marginally worse on the more uncommon twin errors and phonetic errors.

A variant of this algorithm is used by the Dutch ‘burgerservicenummer’ (BSN). This nine-digit number $x_1\cdots x_9$ must satisfy the relation \[ 9 x_1 + 8 x_2 + \cdots + 2 x_8 \equiv x_9 \, (11) \text{.} \] If you’re Dutch, you’re invited to try out your own BSN.

Verhoeff algorithm

The ISBN-10 check digit algorithm is capable of detecting all single-digit errors and all adjacent-digit transpositions. However, it has eleven outputs rather than ten, meaning that an additional symbol is needed to represent all possible codes. Does there exist a check digit algorithm with ten output which can detect all single typos and all adjacent-digit transpositions?

The first algorithm that meets this goal was developed by Jacobus Verhoeff (whom we met before as the author of the error classification) and is now known as the Verhoeff algorithm. The idea of the algorithm is to map the digits to elements of the dihedral group $D_{10}$, manipulate these, then map the result back into digits. We take the mapping to be \[ \begin{align*} 0 &\mapsto e & 5 &\mapsto s \\ 1 &\mapsto r & 6 &\mapsto rs \\ 2 &\mapsto r^2 & 7 &\mapsto r^2s \\ 3 &\mapsto r^3 & 8 &\mapsto r^3s \\ 4 &\mapsto r^4 & 9 &\mapsto r^4s \\ \end{align*} \]

Now let $f \colon D_5 \to D_5$ be the permutation \[ \begin{align*} e &\mapsto r & s &\mapsto r^3s \\ r &\mapsto s & rs &\mapsto r^3 \\ r^2 &\mapsto r^2s & r^2s &\mapsto e \\ r^3 &\mapsto rs & r^3s &\mapsto r^4s \\ r^4 &\mapsto r^2 & r^4s &\mapsto r^4 \\ \end{align*} \] Given a string of digits $x_1 \cdots x_n$, we define the check digit $c$ to be the digit corresponding to the unique element of $D_{10}$ for which \[ f(x_1) \cdot f^2(x_2) \cdots f^n(x_n) \cdot f^{n + 1}(c) = e \text{.} \]

What’s with the permutation? The answer is that this particular permutation was simply introduced because it empirically performs well at detecting errors. In particular, Verhoeff noted that this choice of permutation yields a strong protection against phonetic errors. And that, really, is all there is to it. There is no mathematical structure underlying the permutation, and any other permutation would yield a variant of the algorithm which may or may not perform better. We’ll get back to this in just a moment.

I should admit that I’ve had a great deal of difficulty verifying whether or not the permutation listed above is indeed the one that Verhoeff introduced. It appears all over the Internet — however, it seems that Verhoeff’s original paper is not freely available online. If you have a copy, I’d be grateful if you could share it with me.

According to the book Identification Numbers and Check Digit Schemes by Joseph Kirtland, a different permutation was later proposed by Winters, which is the permutation \[ \begin{align*} e &\mapsto e & s &\mapsto rs \\ r &\mapsto r^4 & rs &\mapsto r^2s \\ r^2 &\mapsto r^3 & r^2s &\mapsto r^3s \\ r^3 &\mapsto r^2 & r^3s &\mapsto r^4s \\ r^4 &\mapsto r & r^4s &\mapsto s \\ \end{align*} \] This permutation, unlike the one by Verhoeff, is capable of detecting all single typos and adjacent-digit transpositions. It does, however, perform substantially worse at phonetic errors. However, again I was unable to trace down the original work.

Whatever the history may be, with today’s computational capacity, it is completely feasible to just brute-force your way through all potential permutations in $S_{10}$. I have decided to do exactly that, and I came to find four permutations which were particularly exceptional at detecting the classified errors, outperforming even the 11-output ISBN-10 algorithm! One such permutation is \[ \begin{align*} e &\mapsto r^4s & s &\mapsto r^2s \\ r &\mapsto e & rs &\mapsto s \\ r^2 &\mapsto r^4 & r^2s &\mapsto r \\ r^3 &\mapsto r^3s & r^3s &\mapsto r^3 \\ r^4 &\mapsto rs & r^4s &\mapsto r^2 \\ \end{align*} \] I have, as always, collected relevant results in the appendix. The data for this particular permutation are listed under ‘Best’.

Damm algorithm

The Damm algorithm is a check digit alorithm developed by H. Michael Damm in 2004. It is capable of detecting all single-digit errors and all adjacent transposition errors, just as the Verhoeff algorithm does — however, it is simpler to implement because it requires only a single lookup table.

To define the Damm algorithm, we first present a general class of check digit algorithms using binary operations. Given a finite set $X$ (which you can just think of as the set of digits $0,1,\ldots,N - 1$ in base $N$) and a binary operation $\varphi \colon X \times X \to X$, we define a check digit algorithm $\Phi$ by sending a string $x_1x_2\cdots x_n$ to \[ \varphi(\varphi(\cdots\varphi(\varphi(x_1, x_2), x_3)\cdots\big), x_n \big) \text{.} \] It’s easily verified that $\Phi$ detects all single-digit typos and all adjacent-digit transpositions if $\varphi$ satisfies the following three axioms.

• The maps $\varphi(x,\,\cdot\,)$ and $\varphi(\,\cdot\,,x)$ are bijective;
• if $\varphi(x,y) = \varphi(y,x)$ then $x = y$;
• if $\varphi(\varphi(u,x),y) = \varphi(\varphi(u,y),x)$, then $x = y$.

The first property says that $\varphi$ defines a quasigroup, or equivalently, that the multiplication table of $X$ defines a Latin square. Quasigroups moreover satisfying the second and third property have been called totally antisymmetric quasigroups or TA quasigroups by Damm.

Here’s an easy way to define many TA quasigroups. Let $R$ be a finite commutative ring, and fix two elements $a$ and $b$. Define $\varphi \colon R \times R \to R$ as $\varphi(x, y) = ax + y$. Then $\varphi$ is quasigroup if $a$ is a unit, and the quasigroup is TA if $a - 1$ is a unit as well.

It’s rather uncommon for a ring to have a unit $a$ such that $a - 1$ is also a unit — but it’s not impossible. For instance, if $R$ is a finite field $\mathbb{F}_q$, then any element $a \neq 0,1$ works. Such an element, of course, can be found for every field except $\mathbb{F}_2$. The result can then be extended to products of finite fields as well, thus yielding many TA quasigroups of any $N$ which is either odd or a multiple of $4$.

This leaves open the case $N = 10$! Moreover, there is no other ring of order $10$ that will do the job, since there are no rings of order $10$ except $\mathbb{Z}/10\mathbb{Z}$. This is one reason that people were led to suspect that there are no TA quasigroups of order $10$.

In his thesis, H. Michael Damm produced a whole array of counterexamples to the suspicion by giving methods of producing TA quasigroups of any finite order. Any such quasigroup will, in principle, yield a check digit algorithm. One such quasigroup which seems to be used often is \[ \begin{pmatrix} 0 & 3 & 1 & 7 & 5 & 9 & 8 & 6 & 4 & 2 \\ 7 & 0 & 9 & 2 & 1 & 5 & 4 & 8 & 6 & 3 \\ 4 & 2 & 0 & 6 & 8 & 7 & 1 & 3 & 5 & 9 \\ 1 & 7 & 5 & 0 & 9 & 8 & 3 & 4 & 2 & 6 \\ 6 & 1 & 2 & 3 & 0 & 4 & 5 & 9 & 7 & 8 \\ 3 & 6 & 7 & 4 & 2 & 0 & 9 & 5 & 8 & 1 \\ 5 & 8 & 6 & 9 & 7 & 2 & 0 & 1 & 3 & 4 \\ 8 & 9 & 4 & 5 & 3 & 6 & 2 & 0 & 1 & 7 \\ 9 & 4 & 3 & 8 & 6 & 1 & 7 & 2 & 0 & 5 \\ 2 & 5 & 8 & 1 & 4 & 3 & 6 & 7 & 9 & 0 \end{pmatrix} \] though as before I’ve been unable to locate its origin. Wikipedia claims it is based on a quasigroup appearing on page 111 of Damm’s thesis, but no such quasigroup seems to be defined there.^{Note 3}

Regardless of history, we are free to test out its strength against the various errors. As it turns out, the algorithm performs exceptionally well, being slightly outperformed only by the hyperoptimised Verhoeff algorithm that we found a section ago. That being said, the Damm algorithm easily beats the Verhoeff algorithm in terms of speed, and it moreover requires only a single lookup table, thus reducing the amount of nasty code in its implementation.

A new algorithm

As indicated in the introduction, I’d like to propose a different check digit algorithm which detects all single typos and all transpositions. It does not require a lookup table to implement — in fact, it may be implemented entirely using elementary operations. It is directly inspired by Verhoeff’s insight to make use of the dihedral group.

As in Verhoeff’s algorithm, we let the ten digits correspond to the elements of $D_{10}$. However, for computational reasons, we choose to work with a different correspondence: \[ \begin{align*} 0 &\mapsto e & 5 &\mapsto r^2s \\ 1 &\mapsto s & 6 &\mapsto r^3 \\ 2 &\mapsto r & 7 &\mapsto r^3s \\ 3 &\mapsto rs & 8 &\mapsto r^4 \\ 4 &\mapsto r^2 & 9 &\mapsto r^4s \\ \end{align*} \]

Given a string $x_1 x_2 \cdots x_n$, we let the check digit be the digit corresponding to the element \[ r x_1 r x_2^{-1} \cdots r x_n^{\pm 1} \text{.} \] It’s clear that this scheme detects all single typos. As for adjacent-digit transpositions, it suffices to verify that \[ x r y^{-1} = y r x^{-1} \implies x = y \text{.} \] The left-hand equality can be rewritten into \[ r^{-1} g r = g^{-1} \qquad \text{where} \qquad g = y^{-1} x \text{,} \] and so the claim is equivalent to saying that conjugation an element $g$ by $r$ never yields the inverse $g^{-1}$, unless $g = e$.

Lemma. Let $G$ be a finite group, and fix an element $r$ of $G$. Then the following are equivalent.

• The centraliser of $r$ in $G$ is of even order.
• There exists a nontrivial element $g$ in $G$ such that $r^{-1} g r = g^{-1}$.

Since the centraliser of $r$ in $D_{10}$ has order $5$, the claim that we can detect transpositions immediately follows.^{Note 4}

Proof: Suppose the centraliser of $r$ in $G$ is of odd order, and suppose there exists an element $g$ such that $r^{-1} g r = g^{-1}$. Then we have the identities \[ \begin{split} gr &= rg^{-1} \\ (gr)^2 &= (rg^{-1})(gr) = r^2 \\ (gr)^3 &= gr^3 \\ (gr)^4 &= (rg^{-1})(gr^3) = r^4 \\ &\vdots \end{split} \] Now let $n$ be the order of $r$. Since its centraliser is of odd order, $n$ itself must be odd, and so \[ (gr)^{n - 1} r = r^{n - 1} r = e \text{,} \] hence $r^{-1} = (gr)^{n - 1}$. Now multiply by $gr$ from the right to get \[ r^{-1} g r = (gr)^n = gr^n = g \text{.} \] This forces $g = g^{-1}$, and moreover implies that $g$ lies in the centraliser. But since the order of the centraliser is odd, so must the order of $g$ be, which forces $g$ to be trivial.

Conversely, suppose the centraliser of $r$ has even order. Then in particular, there exists a nontrivial element $g$ of order~$2$ in the centraliser. By definition, $r^{-1} gr = g$, but as $g$ is of order $2$, we might as well write $r^{-1} gr = g^{-1}$, which proves the result. ∎

What about the computational aspect of our algorithm? The correspondence between digits and elements of $D_{10}$ are specifically chosen so as to take away the need for dedicated lookup tables. Indeed, consider an element $g$ in $D_{10}$, and multiply it from the right by an element $h$. At the level of digits, this means the following. Letting $n_g$ and $n_h$ denote the corresponding integers, we have \[ n_{gh} = \begin{cases} n_g + n_h \qquad &\text{if $n_g$ is even;} \\ n_g - n_h \qquad &\text{if $n_h$ is odd.} \end{cases} \] To describe inverses, it helps to encode the digits in terms of their quotient and residue upon division by $2$. That is, write a digit $n$ as a pair $(k, p)$ so that $2k + p = n$. Multiplication of pairs becomes \[ (k,p) \cdot (k',p') = \begin{cases} (k + k', p + p') \qquad &\text{if $p = 0$;} \\ (k - k', p + p') \qquad &\text{if $p = 1$;} \end{cases} \] and the inverse of $(k, p)$ is \[ (k, p)^{-1} = \begin{cases} (-k, p) \qquad &\text{if $p = 0$;} \\ (k, p) \qquad &\text{if $p = 1$.} \end{cases} \]

Using this logic, our checksum can be constructed inductively. Define the partial checksums \[ C_i = r x_1^{-1} r x_2 \cdots r x_i^{\pm 1} \] Let $P_i$ be the remainder of $i$ modulo $2$. Denote by $(k, p)$ the pair corresponding to $C_i$, and by $(m, q)$ the pair corresponding to $x_{i + 1}$. Then \[ C_{i + 1} = \begin{cases} (k + m + 1, p + q) \qquad &\text{if $p$ and $P \mid q$;} \\ (k + m - 1, p + q) \qquad &\text{if $\neg p$ and $P \mid q$;} \\ (k - m + 1, p + q) \qquad &\text{if $p$ and $\neg (P \mid q)$;} \\ (k - m - 1, p + q) \qquad &\text{if $\neg p$ and $\neg (P \mid q)$.} \end{cases} \]

Of course, the most crucial question is performance. As indicated before, I have done Monte Carlo simulations in the appendix to test the strengths of different check digit algorithms, including the one presented here, which is listed under ‘New’. As the results indicate, the algorithm is significantly more powerful than the common algorithms, including the Verhoeff algorithm with Verhoeff’s choice of permutation. However, it does get outperformed by the Verhoeff algorithm with the permutation that we found earlier using brute-force methods, as well as by the Damm algorithm.

Appendix: Monte Carlo simulations

I have run some Monte Carlo simulations to compare the efficacy of the various check digit algorithms. The results are presented in the table below.

Loose ends

There’s a nagging loose end that I’d like to see resolved. When evaluating performance of different algorithms, I restricted myself to a uniform distribution on the errors that can be classified. However, it would have been more interesting, at least from an applied perspective, to work with a dataset of real-life errors as they occur in practice, particularly so since a significant portion of errors were left unclassified by Verhoeff, but also because the classified errors will likely occur in a biased way. For instance, the single-digit error $6 \to 9$ will be more frequent than $6 \to 1$, because $6$ and $9$ are right next to each other on a numeric keypad. Does such a dataset by any chance exist?

Footnotes

1. You can find your IMEI by dialing *#06#.
2. This is why some older book identifiers end with an X.
3. Admittedly, since Damm’s thesis is entirely written in German, I made virtually no effort in finding the quasigroup.
4. In fact, for any finite group $G$, along with an element $r$ in $G$ of odd-order centraliser, there is an analogous check digit algorithm for base-$|G|$ expressions. This has no further added value in base $10$, since $D_{10}$ is the only nonabelian group of order $10$.