by Neal R. Wagner
Copyright © 2002 by Neal R. Wagner. All rights reserved.
NOTE: This site is obsolete. See book draft (in PDF):
The previous discussions have focused on coding theory applied to binary numbers. In coding theory, the binary number system is regarded as the finite field Z2 with two elements. The theory can be extended to any finite field, but decimal numbers do not work because there is no finite field with 10 elements. It is possible to apply normal coding theory to the fields of order 2 and 5 separately, and then handle a message modulo 2 and modulo 5 separately, combining results at the end. It is also possible to convert a decimal number to binary and use binary error detection and correction. For decimal numbers, neither of these approaches is satisfactory. In the first case the extra error digits would be different numbers of binary and base 5 digits, which would not fit together and could not be combined into individual checkable decimal digits. More importantly for both approaches, the possible errors in a message will be errors in decimal digits. If the number is expressed in binary, a decimal error might change any number of binary bits. If the number is represented using 4 bits per decimal digit, a single decimal error could still change up to 4 bits. For these and other reasons, one needs new decimal-oriented approaches to handle decimal numbers
In applications involving people, numbers with decimal digits are almost always used. (Called the simian preference, because humans have 10 fingers -- well, most of them anyway, and if you count thumbs.) Humans and machines processing these numbers make decimal mistakes in them. The most common mistakes that humans make are to alter a single digit or to transpose two adjacent digits. It is also common to drop a digit or to add an extra digit. Machines can misread a digit, though they would not transpose digits. Applications often add an extra check digit to catch as many errors as possible. There is usually also a check equation which all digits, including the check digit, must satisfy. On the average, one expects to detect about 90% of the errors in this way.
Suppose one has n-1 digits in an application, such as a credit card number: a1, a2, ... , an-1. A check digit will be added in position 0 as a0.
A Simple Check: The simplest check equation just adds all digits mod 10 (form the sum and take the remainder on division by 10) and expects to get 0. So the equation looks like:
where "mod" is given in Java or C by the operator %. Starting with the data digits, one needs to choose the check digit a0 so that the check equation will hold. This is easy to do by setting
The above simple scheme catches all errors in a single digit. In fact the value of the check equation will tell the amount of the error but not which position is incorrect. This method might be suitable for an optical scanning system that occasionally has trouble reading a digit but knows the position in error. However, this scheme misses all adjacent transpositions, so it is not desirable because transpositions are a common human error.
The U.S. Banking Check: A different and better check scheme is used by U.S. banks for an 8-digit processing number placed on bank checks. They add a check digit and use the check equation:
It is essentially the same scheme to repeat the coefficients 1, 3, and 7 indefinitely. This scheme also catches all single errors and it catches all adjacent transpositions of digits that do not differ by 5. Thus 88.888% of adjacent transposition errors are caught (80 out of 90). (Computer programs later in this section verify this fact; it is also easy to prove mathematically.)
The IBM Check: The most common check now in use, for example on credit card numbers, is often called the "IBM" check." Here the check equation is:
where 2#ai means to multiply ai by 2 and add the decimal digits. In Java
For example, if the account number is 54996, then the check equation without the check digit is:
so that the check digit must equal 4 to make the check equation true. Actual credit cards currently have 16 digits and place the check digit on the right, but they treat the other digits as above, so that the first (leftmost) digit is acted on by 2#, while the final 16th digit (the rightmost digit, which is also the check digit) is just added in to the check sum. For example, if a VISA card has number 4270710015912024, then the rightmost 4 is the check digit, chosen so that the check equation will work out to zero:
(2#4 + 2 + 2#7 + 0 + 2#7 + 1 + 2#0 + 0 + 2#1 + 5 + 2#9 + 1 + 2#2 + 0 + 2#2 + 4) mod 10 =
(8 + 2 + 5 + 0 + 5 + 1 + 0 + 0 + 2 + 5 + 9 + 1 + 4 + 0 + 4 + 4) mod 10 = 0
This scheme detects all single-digit errors as well as all adjacent transpositions except for 09 and 90. Thus it catches 97.777% of all adjacent transposition errors (88 out of 90).
The ISBN Check: The ISBN number of a book uses a mod 11 check. The check equation is:
If n >= 11 just keep repeating the weights from 1 to 10. Actual ISBN numbers use n = 10 and write the digits in reverse order. For example if the ISBN number is 0140046569, then the rightmost digit of 9 is chosen so that the following check equation is true:
The check catches all single errors and all transpositions, whether adjacent or not. (If n >= 11 then transpositions are caught if they are no more than 10 positions apart.) Unfortunately, in this check the check "digit" has a value from 0 to 10, and the ISBN number uses an X to represent 10. (I guess they were thinking of "ten" in Roman numerals.) Because the check calculates numbers modulo 11 and requires an extra symbol for the "digit" 10, it is not properly speaking a decimal check at all. Here is an ISBN number with an X in it: 374661046X (the ISBN for Franz Kafka's Der Prozess).
All these checks have disadvantages. The IBM check seems best, except that it does miss two transpositions. The ISBN check performs much better, but it has the serious disadvantage of an extra X inside every 11th number on the average.
Verhoeff's Scheme:
The next section presents a more interesting decimal error
detecting scheme developed by a Dutch mathematicial Verhoeff:
Verhoeff's Check. This method
has a section to itself because it is more challenging
mathematically.
For a very low error rate, one could use two check digits and a modulo 97 check, with weights successive powers of 10. This check catches 100% of all errors on Verhoeff's list (except for additions or omissions), and 99.94% of adjacent double errors. Overall, it catches 99% of all errors, compared with 90% for the single check digit schemes.
Keep in mind that the mod 97 check "digit" itself would be represented as two decimal digits. These two digits would be protected against all double errors. However, a double error would only be caught 99% of the time if it involved adjacent digits where one is a check digit (part of the mod 97 check digit), and the other is a data digit.
For even better performance, one could use a modulo 997 or a modulo 9973 check, again with weights successive powers of 10, and with 3 or 4 check digits, respectively. (The numbers 97, 997, and 9973 are each the largest prime less than the respective power of 10.)
The Hamming code can be carried out modulo any prime number, in particular modulo 11, using the field Z11. This would allow single error correction. Such a check would work with base 11 digits, but one would just treat the base 10 number as if it were base 11. However, any check digits might have the additional value of 10, so there must be some way to represent this value, such as X (as in ISBN numbers) or A (as in hexadecimal).
The Hamming mod 11 Code With Two Check Digits: With two mod 11 check digits and up to 9 data digits, the code would use the following two check equations:
Here the two check digits are a1 in the first equation and a0 in the second. One starts with data digits a2 through a10, then determines the check digit a1 so that the first check equation is true, and then determines the check digit a0 so that the second check equation is true. To correct any single error, get the amount of the error from the second check equation and the position of the error from the first.
This system will correct any single error (including errors in the check digits themselves). Unlike the binary Hamming code, this code will interpret many double errors as if they were some other single error.
The Hamming mod 11 Code With Three Check Digits: Nine data digits are probably too few for current applications, but the Hamming code will work fine with a third check digit, allowing up to 118 data digits. Again, such a system would correct any single error, including a single error in one of the check digits. Keep in mind that all these mod 11 checks require the possibility of an X (or something else) as the value for any of the check digits.
Here the digits go from a0 up to as high as a120. The check digits are a0, a1, and a11. (An actual implementation might collect these three digits at one end.) There are three check equations:
The above equations explicitly show multipliers by 0 to help keep the pattern clear. Start with up to 118 data digits a2, a3, ..., a10, a12, ..., a119, a120. In either order, determine the check digits a1 and a11 using the first two equations. Then determine the check digit a0 using the third equation. If there are fewer than 118 data digits, just set the remaining ones equal to zero in the equations above (and leave them off in transmission and storage). As before, the third equation gives the value of the error, and the first two equations give the location of the error. If pos is the location of the error (pos < 121), then the first equation gives pos%11, while the second gives pos/11, and together these give pos.
Suppose this scheme were used for current credit card numbers. These use the IBM scheme and have 15 data digits (expandable to any number of digits) and one check digit. One would replace these with 15 data digits (expandable to 118 data digits) and 3 mod 11 check digits. Thus the new numbers would have two disadvantages compared with the old: two extra digits and the possibility of an X in three of the digits. In exchange, the system would correct any single error, and would have an extremely low error rate for random errors (1/113 = 0.075% compared with the current error rate of 10%).
With the full 121 digits, this scheme interprets any two errors as if they were a single error in some other position. However, many of these miscorrections try to put a ten, that is, an X into a position other than 0, 1 or 11, and so are recognized as a double error. Thus with 121 digits, about 18.5% of double errors are detected, or 81.5% are undetected.
With only 18 digits, most double errors (75%) will be interpreted as an error in a position greater than 18 and so will be detected as a double error. Also if a double error is interpreted as a "correction" of a position other than 0, 1, or 11 to an X, or if the amount of error comes up as 0, these also represents a detected double error, detecting an additional 9.3%, for a total of 84.3% of double errors detected, or 15.7% undetected.
In summary, the three-digit Hamming mod 11 scheme would have an extremely low error rate if used only for detection. It would allow the correction of any single error. However, for a size such as 15 data digits, about 15% of double errors would be erroneously interpreted as a single error, compounding the problems. For these and other reasons, it does not seem likely that anyone will want to use this code for practical decimal-oriented applications.
In contrast, the binary Hamming code (see the chapter on the Hamming code) corrects any single error and detects any double error. In the mod 11 Hamming code above, the overall check gives the amount of the error. With the binary Hamming code, the corresponding check is not needed, since if there is an error, its amount must be 1 (that is, a 1 changed to a 0 or vice versa). Moreover, any double error will still show up as an error according to the other checks, but a double binary error appears as no error in the overall check. Thus the double error detection works only in the special case of the base 2 Hamming code. Because of this the binary Hamming code has often been implemented for hardware RAM memory. The absence of double error detection in the Hamming mod 11 code, and more importantly, the fact that double errors can mask as a single correctable errors, are fatal flaws.
Law DECIMAL2: Hamming codes exist for prime bases other two, but because they do not support double error detection, and because they may misinterpret a double error as a correctable single error, they are not useful.
The "IBM" Scheme (all but 2 transpositions detected): Java source.
The ISBN Scheme (all transpositions detected): Java source.
The mod 97 Scheme (all transpositions detected): Java source.
Hamming mod 11 Code: