Verhoeff
A checksum algorithm that is not based on mods
The checksum algorithm of Jacobus (Koos) Verhoeff is based on multiplications in point group D5, and a permutation. This causes the contribution of each digit to the checksum to be dependent on the previous digits, unlike the usual addition-modulo-something checksum algorithms.
The point group D5
The point group D5 is a.o. used to describe the symmetry of certain molecules, and to derive some of their physical properties. It has 10 elements, and that's why it has been used to calculate checksums for decimal digits. In terms of symmetry operators, the 10 elements are: the unit operator E, 4 rotations along a five-fold symmetry axis C5 (so a rotation over multiples of 72°, the fifth rotation being equal to E) and 5 two-fold rotations C2.
Multiplication in D5 can be regarded as applying one operator after another. This multiplication is non-commutative, for example: C5*C2' ≠ C2'*C5 (as can be seen in the colored multiplication table).
For a checksum calculation the operators correspond to the numbers 0 to 9.
Permutation σ
Verhoeff extended the D5 scheme by adding a permutation σ, and performing the permutation i times on the ith digit.
Multiplication in point group D5.
See also an interactive animation.
Note that σ8(x) = x, so σ9(x) = σ(x), and so on.
For a number a with digits ai (starting at the right), the check digit a0 is set by
σ(an) * σ2(an−1)* ... * σn(a1) * a0 = 0
The algorithm was used by the Deutsche Bank, to number their banknotes. The 11-digit numbers also contained letters, which where mapped to digits by the table below:
A 10 Deutsche Mark bank note with number GN4480100S8.
Electronic device
In 1969, Verhoeff and US Philips Corp. filed a patent application for electronic checksum calculators using a.o. the algorithm described above.
Part of electronic Verhoeff devices, from US Patent 3,675,202
Mechanical device
Because I'm interested in mechanical calculators I looked for a mechanical implementation of the Verhoeff-algorithm, but failed to find one.
So I decided to design one myself. It consists of 11 cylinders, each with a different table printed on it. The cylinders lie side by side in a slotted box. The slots leave one column of each table visible. A cylinder is rotated when selecting a number from the visible column on the previous cylinder.
In the prototype a (red) indicator is moved to a digit by rotating the next cylinder. The indicator is attached to a wire that runs along the ends of the cylinder, as indicated in the detail. If you turn a cylinder, the wire is wound from the top and wound onto the bottom, thus shifting the indicator. A more advanced embodiment could use a Curta-like setting mechanism.
Prototype of a mechanical Verhoeff checksum calculator, with detail.
The cylinders contain the following tables:
The letter-to-number conversion is on a separate static table, but could also be incorporated on the cylinders, either by adding the letter in each cell or by doubling the length of the cylinders and putting a letter version of the tables on the lower part (be sure to make the wire long enough to move the indicator over twice the length)
References
J. Verhoeff, “Error Detecting Decimal Codes”, (Mathematical Centre Tracts, 29). Mathematisch Centrum. Amsterdam 1969; second edition 1975.
J. Verhoeff, “Device for checking a group of symbols...”, US Patent 3,675,202, filed 1-6-1969, patented 4-7-1972, assigned to U.S. Philips Corp., based on Dutch Patent 690,8248