A check digit is a form of redundancy check used for error detection. It consists of a single digit computed from the other digits in the message. Many items that we see every day use a check digit to help detect forgery or errors. Items like driver's licenses, money orders, airline tickets, and UPCs on merchandise. A check digit is formed by a algorithm that uses modular arithmetic, then is added to the end of the identification number.

Several states, including Florida use linear functions to encode the month and date of birth into a three-digit number that is made into the last three digits of the driver's license number. For males in Florida the last three digits are given by 40(m-1)+b, where m is the month and b is the date of birth. So a male with check number 230=40(6-1)+30 would have been born on June 30. For a female they then add 500 to this number. For Illinois it's 31(m-1)+b, then if the driver is a female add 600. If you want to learn more about how Florida and Illinois create there entire driver's license number see US Driver's License Numbers.

Nearly every item we purchase has a UPC. A UPC contains 12 digits. The first 6 indicate the manufacturer and next indicate the product and the last one is a check digit. To check for errors we do the following. Denote digits 1 though 12 as(a₁,a₂,a₃,...,a₁₂) then compute

(a₁,a₂,a₃,...,a₁₁,a₁₂)*(3,1,3,1,3,1,3,1,3,1,3,1) then reduce mod 10.

Where * denotes the dot product, which is short had for 3a₁+a₂+3a₃+...+3a₁₁. If this does not result in 0, then there is an error.For example suppose you see a UPC code of
036000 291452. Lets verify that this has the correct check number. So we compute

(0,3,6,0,0,0,2,9,1,4,5,2)*(3,1,3,1,3,1,3,1,3,1,3,1) mod 10

which is 60mod10=0. Check digits are chosen to ensure that this computation results in 0. If given the first 11 digits of a UPC, you can always pick the check digit 0-9 so that this computation results in 0.

The advantage of using this scheme is that it will detect all errors involving one digit and nearly all errors involving the transposition of two adjacent digits. If we switch the 2 and 3 positions in our example giving us a UPC of 063000 291452 the computation gives us 66mod10=6, not 0. So we know there has been an error. Now consider the UPC 016000291454 our computation yields 60mod10=0. Good right? But what if we made the error of switching positions 2 and 3 again? We would have written down 061000291454 our computation yields 50mod10=0 so we have the right code correct? Now, why didn't our check code system detect and error? It's because any time two adjacent numbers are switched and there difference is 5 the UPC check code system fails to detect this error.


Problem Set 3 :

Suppose you are working as a bouncer and a male that looks a bit young hands you a Florida State driver's license with the last three digits 177 and states that his birthday is February 2, making him just barely old enough to enter the bar. Is this Driver's License legitimate? If his birthday were really February 2, what should the last three digits be?

Prove that the check digit on a UPC can detect any one digit error.

Show that if two adjacent digits in a UPC are transposed, that the check digit will detect this error if and only if there difference is not equal to five.

Knowing the result of the previous problem. What is the probability that given two adjacent digits in a UPC have transposed that the check digit will detect an error?

End of Problem Set 3

The final character of a ten digit International Standard Book Number is a check digit. You will see these on any book and once in college you can save quite a bit of money buy purchasing your books online. This check digit system helps ensure that you are purchasing the correct text book. Suppose that you copy down the ISBN of a book that you need and switch two adjacent digits or simply write down one of the digit wrong, then when you go to search for that text online it will show you no books of that ISBN. The way that the check digit works for ISBNs is comparable to the UPC system. To verify that you have written down your ISBN correctly do this computation.

(a₁,a₂,a₃,...,a₉,a₁₀)*(10,9,8,7,6,5,4,3,2,1) then reduce mod 11.

If this does not yield 0, then there is an error in your ISBN. Some times it is necessary for the last digit to be 10, in this case the ISBN will end with the letter X. The check digit will always detect if you wrote one of the numbers down one number incorrectly. To see this first fix the position were the error is to occur a_i, the correct number is say n, and the digit you wrote down is m. The correct addition to the check digit is ni, but you instead added mi. Since 11 is prime, fixing 0<=i<=9 multiplying i by any number 0,1,2,3,...,9 will give you a different check digit addition mod 11.

Problem Set 4 :

Show that there is an error in the ISBN 0395861899. If you assume that the first nine digits are indeed correct, what should the last digit be?

Give an example of an ISBN where the last digit must be X.

Prove that if any two adjacent digits in an ISBN are transposed that the ISBN check digit system will detect this error.

End of Problem Set 4

References and Further Reading:
[1]Joseph A. Gallian.Contemporary Abstract Algebra 4th Edition Houghton Mifflin Company, 1998, pages 4-13.
[2]Wikipedia Check Digit http://en.wikipedia.org/wiki/Check_digit