The Mathematics
of Barcodes

Cracking Barcodes
The UPC a Scheme
Coding Errors
Appendices
Credits
Student CopyTeacher CopyReference Copy

Activity 1: Cracking Barcodes
(Student Copy)

Materials

Part A

See the definition for modular arithmetic on the reference sheet.  Modular arithmetic deals with numbers that are congruent based on their remainder with respect to a particular divisor.  For example, 7 º 13 (mod 3) because 7 and 13 divided by 3 both have a remainder of 1.
  1. What is the remainder when 18 is divided by 5?  List 3 numbers that are congruent to 18 (mod 5).
  2. What is the remainder when 26 is divided by 11?  List 3 numbers that are congruent to 26 (mod 11).
Modular arithmetic is used to provide a numerical check to the UPC-A system.  In order for the UPC-A number to be valid, the twelve numbers in the bar code must satisfy the following condition:

3a1+a2+3a3+a4+3a5+a6+3a7+a8+3a9+a10+3a11+a12 º 0 (mod 10).

Another way of stating the above congruence relationship is to say that 3 times the sum of the digits in the odd positions plus the sum of the digits in the even positions is congruent to 0 (mod 10).

For example, to check the validity of the UPC-A number 065961100602, calculate 3(0 + 5 + 6 + 1 + 0 + 0) + (6 + 9 + 1 + 0 + 6 + 2) = 3(12) + (24) = 36 + 24 = 60 º 0 (mod 10).  Therefore, it is a valid number.

  1. Check the validity of the UPC-A number 057627529316.  Is it a valid UPC-A number?
  2. Check the validity of each 12-digit UPC-A bar code on the reference sheet and record your answers in a table like the one below.
12-Digit Number Valid  Not Valid
230124231978 Yes .
011110868527 ? ?
055653670209 ? ?
037000661153 ? ?
  1. In your group, write 3 12-digit numbers.  Do this by randomly writing 12 digits (0-9) for each number.  Check the validity of each, and record your work in a table like the one above. If the number you choose is not valid, change one of the digits to make it a valid UPC-A code.

Part B

The 12th number of the UPC-A system is the check number.  It is the one that makes the whole 12-digit scheme fit the condition that

"3 times (the sum of the digits in the odd positions) + (the sum of the digits in the even positions) º 0 (mod 10)."

Look at the reference sheet, to find the definition of congruence ().  All of the other digits are used to identify the manufacturer and product while the 12th digit is designed to simply "make up the difference" in mod 10.

Consider the bar code number 06592143210.  The equation to find the check number is:

3(0 + 5 + 2 + 4 + 2 + 0) + (6 + 9 + 1 + 3 + 1 + C) º 0 (mod 10).

C represents the check number.  Next, the equation is simplified:

3(13) + (20 + C) º 0 (mod 10)
39 + 20 + C º 0 (mod 10)
59 + C º (mod 10)

Thus, C would have to be 1 to make the left hand side of the congruence a 60, which is congruent to 0 (mod 10).

However, while the check digit is always bar coded in the UPC-A system, it is not always written on the product in numerical form.  Use the bar codes on the reference sheet where the   12th digit is missing.  Your group's task will be to find the missing check digit.  Fill in the table below.  First, find the 12th digit mathematically.  Then, check your answer by reading the widths of the bars and spaces of the bar code and look up the number on the right hand code chart (see the reference sheet).

11-Digit Number Calculated
Check Number		 Check Number
from Table
06592143210 1 1
01258760032 ? ?
41606135119 ? ?
02429115081 ? ?

Part C

The IBM code is a more complicated but also more error-proof than the UPC-A system.  Like the UPC-A coding scheme, it also includes a check number as its last digit and it uses mod 10 arithmetic to arrive at this number.  However, instead of a simple system of multiplying all of the odd digits by three, adding them to the sum of all of the even digits, and setting that sum congruent to zero (mod 10), the IBM scheme utilizes a permutation for encoding.  The congruence statement for a code with an even number of digits is

(a1) + a2 + (a3) + a4 + ... + (an-1) + an º 0 (mod 10),

where s maps numbers according to an encoding scheme and the alternate digits are unchanged.  If the number of digits in the bar code is odd, s is applied to the even numbered positions instead of the odd positions as shown above.

Find the definition of permutation on the reference sheet.  For this activity, use the permutation (0)(124875)(36)(9) which means that 0 ® 0, 1 ® 2, 2 ® 4, 4 ® 8, 8 ® 7, 7 ® 5, 5 ® 1, 3 ® 6, 6 ® 3, and 9 ® 9.

For example, take the IBM code number 85469. Since there are an even number of digits, s functions on the digits in the odd positions.  The resulting congruence statement would be 7 (8 maps into 7) + 2 (2 in an even position remains unchanged) + 1 (5 maps into 1) + 9 + 8 + 3 + 3 + 3 + 9 + 8 º 0 (mod 10).  Since the sum of the left side is 50 which is congruent to zero (mod 10), the code is a valid one in the IBM system.

  1. Come up with two valid IBM codes:  one with an odd and one with an even number of digits.
  2. Check the validity of 345678921, which has an odd number of digits.
  3. Find C, the check number, for 9776827468C (an odd number of digits).
  4. Find C, the check number, for 320053461C (an even number of digits).


© Copyright
Area 10 Mathematics and Technology Professional Development Center
Permission is granted to duplicate these materials for classroom use.

Last updated on 1/30/1999
Comments: egalindo@indiana.edu
http://www.indiana.edu/~atmat/units/barcodes/bar_s1.htm