EE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada
One of the most widely used algorithms for character-based error control is known as the LUHN-10 Algorithm. This simple but effective error detection method is commonly used by companies and organizations when issuing account and membership numbers. The algorithm is specified in the ISO-7812-1 standard defining a common format for credit cards.
Like the ISBN used for book identification, the credit card number shown below is specially constructed to incorporate error detection. In particular, the final digit is included only as an error control mechanism.
Error control codes are often designed for known applications where certain types of errors are expected to occur. In this case, the most common errors expected would be those which humans would typically make when writing or typing the number or entering it on a web site. These errors would normally be either "write a single digit incorrectly", or "switch two adjacent digits". Of course, the ability to detect errors also provides a simple test to identify invalid numbers which might be encountered (for example, if someone were to forge a credit card number).
The final digit in the number provides the desired error detection capability. It is computed when the number is issued so that the entire value can be checked for errors whenever it is transcribed or transmitted.
One Possible Approach - Checksum "Modulus 10"
Consider a simple scheme in which the first digits are simply added up and the sum (or rather the 'ones' digit in the sum) is used as the final digit. For example with 4563 9601 2200 199_ the sum is 57 so the final digit would be '7':
4 5 6 3 9 6 0 1 2 2 0 0 1 9 9 7 4 + 5 + 6 + 3 + 9 + 6 + 0 + 1 + 2 + 2 + 0 + 0 + 1 + 9 + 9 = 57
Note that taking only the last digit in a decimal number is equivalent to dividing the number by 10 and using only the remainder. This result is also refered to the sum "modulus 10". This is generally written as:
How the LUHN-10 Algorithm Works
If a 'weighted sum' is constructed by multiplying adjacent digits by a different constant (in this case, either 1 or 2) the problem of adjacent swapped digits going undetected can be eliminated. A checksum is constructed from the sum of the resulting digits. If a product results in two digits (e.g. 2x6=12), the individual digits (1 and 2) are added separately into the checksum. The final digit is computed so that the weighted sum is an exact multiple of 10. In other words, the overall sum "modulus 10" equals zero. In this case, 70 is an exact multiple of ten.
4 5 6 3 9 6 0 1 2 2 0 0 1 9 9 9 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 x2 x1 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 8 5 12 3 18 6 0 1 2 2 0 0 2 9 18 9 8 + 5 +1+2+ 3 +1+8+ 6 + 0 + 1 + 2 + 2 + 0 + 0 + 2 + 9 +1+8+ 9 = 70
It is important when applying this method to numbers of different lengths that the rightmost digit (the check digit) is always multiplied by 1 and not by 2.
It can be observed that the presence or absence of leading zeros in a number to be checked has no effect on the result. (e.g. 8913105 or 08913105 or 00008913105 would all pass the test)
The contribution of a given digit to the total sum depends on its position in the number and, specifically, whether it is multipled by 1 or 2.
1. What if a single digit is wrong?
If a single digit is changed to another, the total sum must change, whether or not that digit is multiplied by 2. A single-digit error is always detected as each possible digit has a unique contribution and the sum cannot change by a multiple of 10.
2. What if adjacent digits are accidentally swapped (i.e. 34 becomes 43) somewhere in the number?
The LUHN-10 method is not perfect in detecting swapped digits. Although swapping two adjacent digits will generally result in a checksum failure, there are cases which will not be detected.
From the table above, it can be seen that the contribution of the digits 9 and 0 do not change with position. If the digits 9 and 0 are side-by-side and get swapped, their contribution to the total sum will be the same.
... 9 0... ... 0 9... ... x1 x2... ... x1 x2... -- -- -- -- 9 0 0 18 9 + 0 = 9 0 +1+8 = 9
It can be argued that for all possible two digit values (00..99) there are 90 cases of two different digits side by side and that the algorithm will fail to detect swapped digits in two of these cases ('09' becomes '90', and '90' becomes '09'). Consequently, swapped digits will be detected 88 times out of 90 (97.8%).
If two non-adjacent digits are swapped, either the change is not detected at all (if they are both multiplied by 1, or both by 2), or the situation is identical to swapping adjacent digits.
WORST CASE PERFORMANCE
If a LUHN-10 protected number is totally garbled (or forged!), the use of modulus 10 implies that there is one chance in ten that the (random) number will nonetheless pass the error detection test. Conversely, there are 9 chances out of 10 that the error will be detected. Consequently, while single-digit errors are all detected and most swapped adjacent digits can be detected, other types of errors should be detected with 9/10 = 90% reliability.
It is interesting to note the number and variety of different applications which make use of the exact same method of error detection. Of course, since it is not used for authentication there is no reason why different people should not use a standard error control method. Many software packages use the above test as a preliminary verification on a website or data terminal before submitting an account number for final authorization.
The following merchants or organizations use LUHN-10 in their client numbers:
Perhaps the most 'public' source of numbers to check in Canada is found in the GST registration number, as every merchant is required to print this nine-digit tax number on all sales receipts.
Try the EE4253 Online LUHN-10 Checking Tool
A systematic approach to error detection can lead to better codes. Both the simple checksum and the LUHN-10 method involve adding only one additional digit, yet the latter method is more effective as swapped adjacent digits can also be detected.
Sat May 25 01:00:07 ADT 2013
Last Updated: 17 OCT 2002
|Richard Tervo [ firstname.lastname@example.org ]||Back to the course homepage...|