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.
In 1969, J. Verhoeff used mathematics to design a system which was remarkably flexible, and in which the code words were all decimal digits and the check digit appended at the end of the digit string was another decimal digit. Is there a way of improving on the error detection rate that is associated with the relatively simple decimal error code detection systems? Mathematics to the rescue, and from a rather surprising place: the theory of groups, illustrating the value of research in pure mathematics. Tools for applied problems are often available due to human curiosity. Are you surprised that the tool Verhoeff used was a mathematical idea better known for telling how symmetrical something is?
Group theory has many aspects, but one major way of viewing the theory of groups is that it provides a way of understanding symmetry. Consider the three figures below, all of them quadrilaterals: a rhombus, a rectangle, and a square.
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).)
Suppose we wish to describe an isometry of the rhombus, say, its one rotational symmetry through an angle other than zero degrees. We can represent this transformation with two rows of letters. The top row giving the the name of a vertex of the polygon and under it in the second row we give the location where that vertex of the polygon is moved to by the transformation. Since a rotation of 180 degrees moves vertex a to c and c back to a, while b is moved to d and d to b, we represent this rotation using the notation:
There are two reflections which will transform the rhombus onto itself, one in each of the diagonals of the rhombus. (Remember that the diagonals of a rhombus are perpendicular while those of a rectangle with two unequal sides will not meet at right angles.) There is also the identity transformation which transforms every vertex of the 4-gon back to itself. Using the letters attached to the vertices of the rhombus, we can denote these transformations using the notation described above. Now, it is convenient to represent each of these transformations by a number as shown. We use the number 1 for the identity transformation.
Using the numbers we have given to represent the transformations, we can construct a table, which can be used to show the result of multiplying two of the transformations, that is, carrying out one of the transformations followed by the other. In such tables we will use the * symbol to represent the multiplication.
|
*
|
1 |
2 |
3 |
4 |
|
1 |
1 |
2 |
3 |
4 |
|
2 |
2 |
1 |
4 |
3 |
|
3 |
3 |
4 |
1 |
2 |
|
4 |
4 |
3 |
2 |
1 |
Thus, if we carry out transformation 3 followed by transformation 2 we get
because a goes to a in 3 and then a goes to c in 2; b goes to d in 3 and d then d goes to d in 2; etc. The symbol whose second row has exactly these entries is the one labeled 4.
Just as we devised a way of representing the symmetries of the rhombus, we can arrive at labels for the symmetries of the rectangle in a similar manner:
These in turn give rise to the multiplication table below (where * is used to designate the non-standard multiplication:
|
*
|
1 |
2 |
3 |
4 |
|
1 |
1 |
2 |
3 |
4 |
|
2 |
2 |
1 |
4 |
3 |
|
3 |
3 |
4 |
1 |
2 |
|
4 |
4 |
3 |
2 |
1 |
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.)
The square, on the other hand, has more than 4 symmetries; it has eight symmetries that transform the square into itself. These transformations are easy to describe geometrically: there are 4 rotations of 0 degrees, 90 degrees, 180 degrees, and 270 degrees; reflection in a horizontal line; a reflection in a vertical line; and reflections in the two diagonals. The symmetry group of the square is known as the dihedral group of order 8.
Although the square has 8 symmetries which preserve the distances between the vertices, note there are 24 different transformations of symbols to 4 symbols. If we look at a square not as an object involving distances between its points but as a graph (think of the square as 4 dots joined by 4 lines), the transformations of the graph of a square (which is the same as the graph of any quadrilateral) which preserve edges which are adjacent to each other is exactly the same as the transformations we have already identified!
Verhoeff's system to compute a check digit is based on the fact that one can use the digits 0, 1, ..., 9 to represent elements in a group rather than the usual integer values. A group can be thought of as an algebraic structure which allows one to multiply pairs of elements to get a unique new element within the same structure, and where the multiplication behaves nicely. This means that the associative law holds, that there is an element which behaves like the number 1, and every element has an inverse. There are exactly 2 groups built on 10 symbols. (The number of groups with a given number of elements is a complex and interesting subject.) One of these groups is the cyclic group with 10 elements, a group which has the property that ab = ba for all element pairs (i.e. the group is commutative). However, the other group of order 10 is a non-commutative group. That is, ab and ba are not the same for all group elements. This other group consists of exactly the 10 symmetries of a regular polygon with 5 sides. Thus, it is exactly analogous to the symmetries of the 4-gons treated in some detail above. The entries in the table must correspond to decimal digits, so they are labeled 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9. The table has the usual properties of a group but it is not commutative.
|
* |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
0 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
1 |
2 |
3 |
4 |
0 |
6 |
7 |
8 |
9 |
5 |
|
2 |
2 |
3 |
4 |
0 |
1 |
7 |
8 |
9 |
5 |
6 |
|
3 |
3 |
4 |
0 |
1 |
2 |
8 |
9 |
5 |
6 |
7 |
|
4 |
4 |
0 |
1 |
2 |
3 |
9 |
5 |
6 |
7 |
8 |
|
5 |
5 |
9 |
8 |
7 |
6 |
0 |
4 |
3 |
2 |
1 |
|
6 |
6 |
5 |
9 |
8 |
7 |
1 |
0 |
4 |
3 |
2 |
|
7 |
7 |
6 |
5 |
9 |
8 |
2 |
1 |
0 |
4 |
3 |
|
8 |
8 |
7 |
6 |
5 |
9 |
3 |
2 |
1 |
0 |
4 |
|
9 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
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.
-
Introduction
-
Barcodes
-
Zip codes
-
The Universal Product Code
-
ISBN Numbers
-
The Ultimate System
-
References
