Barcodes: The Ultimate System
6. The Ultimate System
The ISBN number illustrates some of the issues that designers of good error detection codes must face. One wants a code which detects as many errors as possible, but one wants to do this in an environment of working with one decimal check digit and where the characters in the code are all decimal digits. One might also like to have a system that would assign a check digit to a string of digits no matter how long or short. For other applications one might want codes that allowed a check digit to be assigned to code word strings that include symbols other than digits.
How can one compare the symmetries (distance preserving transformations) of these different sized and shaped things? One idea is to look at those ways of transforming these shapes onto themselves that preserve the properties of the shape one cares about. Of special interest are transformations which preserve the (Euclidean) distance relations. For example, there are rotations and reflections which transform these shapes onto themselves. These transformations may or may not transform the shape onto itself. However, if we rotate the square by 90 degrees in the clockwise direction the shape will superimpose on itself. If the same operation is performed on the rectangle or rhombus, the shape will not superimpose. The only two types of geometric transformations which can arise as the symmetries of these three types of 4-gons are rotations and reflections. Rotations and reflections are examples of geometric transformations known as isometries because they preserve distance. Here we are interested in Euclidean distance. (A complete list of isometries in Euclidean 2-dimensions are translations, reflections, rotations, and glide reflections (which are the result of either a reflection followed by a translation or a translation followed by a reflection).)
Thus, if we carry out transformation 3 followed by transformation 2 we get
These in turn give rise to the multiplication table below (where * is used to designate the non-standard multiplication:
Although the symmetries of the rectangle are again 4 in number, it does not follow that their symmetry groups are the same. From one point of view it's tempting to think the two symmetry groups are different, because in the group of the rhombus there are vertices which are transformed into themselves by symmetries other than the identity, while this does not happen for a rectangle. However, if you examine the two multiplication tables for the two groups, you will see they look identical! Thus, we say that the two groups are isomorphic. (There are two different (i.e. non-isomorphic) groups with 4 elements but no 4-gon has this other group as its symmetry group.)
Using this group of order 10, the dihedral group of order 10, Verhoeff designed a system which finds all substitution errors, errors which occur due to switching adjacent digits, as well as a variety of other common errors. The details of how to implement an error correction system based on this table are more technical than I want to get into. The interesting thing is that a variant of the system developed by Verhoeff was used by the German Bundesbank starting in about 1990 to provide a check digit system for German Bank notes. This system is an alphanumeric system where in addition to the usual 10 digits, there are also 10 letters of the alphabet with decimal digit representations that are employed. The system involves 11 characters where, the tenth character is a check digit based on the non-commutative group of order 10. Unfortunately, because of the use of digits to represent letters, certain errors are not caught.
Undoubtedly, the use of barcodes will continue to grow as new mathematical ideas and new technologies make possible ingenious new uses of the codes.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance