An optimal system: the Verhoeff Scheme

The purpose of check digits is to detect errors in the transcription of numbers with many digits. What features should such a code have? It must detect all singular errors (a mistake in a single digit) and all transpositions of adjacent digits (1), since about 90% of usual errors are of one of those two types. On the other hand, for the sake of ease of use, it is often preferable to have systems with identification numbers build only with digits \(0, 1, 2,..., 9\), with no need of extra symbols, and with a unique check digit (2).

Most implemeted codes (Barcodes, Identity Card, NIB, Visa Cards, banknotes, etc.) are based on modular arithmetic, but none of them have both the above properties. NIB code needs more than one check digit, barcodes and Visa cards do not detect all consecutive transpositions, BI code (if applied correctly) needs \(11\) symbols (thus digits \(0, 1, 2,..., 9\) are not enough), and the Euro system do not even detects all singular errors. In fact, one can show that any error-detecting code based on Modular Arithmetic can not satisfy both properties (1) and (2).

In 1969, the Dutch mathematician J. Verhoeff, designed an "optimal" (in the sense that it satisfies both properties (1) and (2)) error-detecting code. It relies on "more sophisticated" concepts and ideas from Group Theory.

Let us see an example of a Verhoeff code that uses some Group Theory. This code could replace more effectively the one currently implemented in ID cards.