UNB ECE4253 Digital Communications
Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Secrets of the LUHN-10 Algorithm - An Error Detection Method

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.

4563 9601 2200 1999
This credit card number holds a secret.

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.

4563 9601 2200 1999
The final digit is appended for error control.

One Possible Approach - Checksum "Modulo 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
If any single digit is written incorrectly, this scheme will detect that error; however, if two digits are switched with each other, the sum will not be affected and that error would go undetected. Although this simple 'checksum' does provide some error detection, it is not good enough for this application.

Modulus Arithmetic

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 referred to the sum "modulo 10". This is generally written as:
57 ≡ 7 (mod 10)
After division by 10, the remainder is 7.

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   4   2   0   0   2   9  18   9
 8 + 5 +1+2+ 3 +1+8+ 6 + 0 + 1 + 4 + 2 + 0 + 0 + 2 + 9 +1+8+ 9 = 70 
70 ≡ 0 (mod 10)
The number is correct if a zero result is obtained.
It is important when applying this method to numbers of different lengths that the rightmost digit (the check digit) is arranged to be multiplied by 1.

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)


PERFORMANCE ANALYSIS

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.

            DIGITS  0 1 2 3 4 5 6 7 8 9  
                    -------------------  
 Contribution (x1)  0 1 2 3 4 5 6 7 8 9  
 Contribution (x2)  0 2 4 6 8 1 3 5 7 9  


Contribution of LUHN-10 digits to the summation.

1. Single Bad Digit

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. Adjacent Digits Switched (e.g. 34 becomes 43)

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.

Applications of LUHN-10

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 LUHN-10 is not used for authentication there is no reason why different credit cards, for example, would 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 applications use LUHN-10 in their client numbers:

Perhaps the most 'public' source of numbers to check in Canada is found in the GST/HST 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


Conclusions

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.

Thu Sep 19 05:36:00 ADT 2019
Last Updated: 17 OCT 2002
Richard Tervo [ tervo@unb.ca ] Back to the course homepage...