In the late 1970s I managed a small community grocery store that was located in the Santa Cruz Mountains. I enjoyed the camaraderie with the community folk when I wasn't busy with the hectic inventory process.

 

On each box unloaded from the truck, I marked the wholesale price and date with a felt marker pin. At the time this was the acceptable way to maintain inventory for rotation of goods. With the wholesale price already on the box all one needed was a hand calculator to figure the markup price and stamp or sticker the price on each item.

 

Little did I know that barcode technology was on its way to stores and businesses all around the world. Perhaps my job could have been easier. I heard that this new technology promised substantial advantages to companies. It guaranteed improvements in productivity, accuracy and profitability. Well, except for the little mom and pop stores like the one I worked at. The technology at the time was hopelessly expensive.

 

Who discovered bar code technology?  How has this technology changed all our lives? Where are we going in the future with this technology? How has mathematics helped in launching this digital revolution? These are questions I will answer as well as demonstrate how Postnet and UPC codes are read and the mathematics behind error detection.

 

Bernard Silver was a graduate student at Drexel Institute. His involvement with bar coding began in 1948 when he overheard a president of a large food chain asking the dean of Drexel Institute if the school would take on a research project. The president wanted to capture product information at the checkout counter. The dean wasn't interested and turned him down. The eavesdropping student took this information to his friend Norman Joseph Woodland, a graduate student and teacher at Drexel.  Woodland was quite interested in the idea of coding.

 

Silver and Woodland worked on many ideas. The first was using patterns of ink that could be read under ultraviolet light. They were having difficulties with the inconsistency of the ink and determined that the cost for printing would be very expensive. After many tedious months of work, Woodland hit on the idea of a linear bar code, based on elements from two established technologies: movie soundtracks and Morse code. The dots and dashes were simply extended down. Woodland later decided to replace the horizontal lines with another design called the bull's eye code which was circular and
could be scanned from many directions. Lasco Fittings states that the men filed for a patent on October 20, 1949. Their patent was granted in October 1952. (patent number 2,612,994). (12 Sept 2002) (http://www.lascofittings.com/BarCode-EDI/bc-history.htm)

 

Silver and Woodland had finally established a functional barcodes. The next logical step was to develop a reader. They started working in Woodlands apartment and built a device that was huge, about the size of a desk. Lasco Fittings writes that the men came up with two key elements: a five hundred-watt incandescent bulb as the light source and an RCA 935 photo-multiplier tube, designed for movie sound systems, as the reader.

(12 Sept 2002) (http://www.lascofittings.com/BarCode-EDI/bc-history.htm) This system gave them the results they had hoped for. All their hard work had finally paid off. Now, what they needed was someone to finance the project.

 

Since Woodland was working for IBM at the time, he had approached them with an offer, asking for help in furthering the development of the bar code. IBM wasn't interested in helping them but was interested in buying the patent. IBM made an offer to buy the patent but Silver and Woodland declined because they felt they could get more for their ideas. Philco made them a good offer and they sold their patent to them. Lasco Fittings states that in 1962 Philco bought the patent. Philco later sold the patent to RCA and it wasn't long before RCA made advancements which caused this technology to blossom. (12 Sept 2002) (http://www.lascofittings.com/BarCode-EDI/bc-history.htm)

It was in the 1980s when barcode technology really took off. Just about every business used some type of coding system. Some industries needed a more complex coding system which was 100 percent accurate. Others needed barcodes which held more information. As a result a variety of barcode systems were developed with different error check and error correcting algorithms. Some of which can be seen in Table 1 below.  Gallian, Winters, (1991) shows different varying percentages in error detection system algorithms. As the error rate diminishes the complexity of the math increases. (pg 550) Most of the math formulas used in complex error correction is so complex that it is too difficult to explain. For this reason I will only emphasize two types of barcodes, the Postnet and the UPC code.

Table 1.

The Postnet code used by the U.S. Postal Service is found on many pieces of commercial mail yet most of us are not aware of it. Let's take a look at Zip Codes, the simplest of barcodes. Here we will understand its structure, readability and calculate the tenth check digit as well as find and correct an incorrect or missing number.

 

Each numeric number is identified by five bars that consist of three short and two long bars which are in different orders shown in table 2(a).  Linear barcode always have a long guard bar at the beginning and end which indicate the starting and ending points for the barcode set.

 

In table 2(b) we solve for the check digit number or in other words solve for X. There are ten blocks of five vertical bars and each block represents a number. The tenth and last block is the check digit number. By using an algebraic formula we can solve for X. If we sum the ten integers we can find the check digit number by adding to the sum a number that will make the total divisible by ten. Refer to #1.Assigning the Check Digit on page 4.

 

The example used in table 2(c) shows a number missing in the string of code. Solving for X you sum the known numbers and add a single digit that will make that number divisible by ten. See below Table 2 for Algebraic solutions. Refer to #2 and #3 on pages 4. and 5.

 

Table 2.

 

Zip Code barcodes can be expressed in an algebraic formula. Table 2(b) I will demonstrate error code detection, first by defining the formula, present the formula and then give an example. Table 2(c) shows solving for error correction, finding the incorrect or missing digit using the check digit.

 

1. Assigning the Check Digit

Definition

X = Check Digit

Y = Sum of all zip code integers

Z = Any integer evenly divisible by 10 and > Y

 

Formula

X = Z - Y

or: the check digit equals any integer evenly divisible by 10 and greater than the sum of all zip code integers minus the sum of all zip code integers.

 

Example

X = Z - (U1+U2+U3+U4+U5+U6+U7+U8+U9)

X = Z - (9+5+1+1+0+2+2+4+8)

X = Z - 32

Z = 40

X = 40 - 32

X = 8

 

2. Error Check Using the Check Digit

Definition

X = Any integer evenly divisible by 10

Y = Sum of all zip code integers

Z = Check Digit

 

Formula

X = Z + Y

or: any integer evenly divisible by 10 equals the sum of the zip code integers plus the check digit.

 

Example

X = Z + (U1+U2+U3+U4+U5+U6+U7+U8+U9)

X = Z + (9+5+1+1+0+2+2+4+8)

X = Z + 32

Z = 8

X = 8 + 32

X = 40

If X does not equal an integer evenly divisible by 10 then there is an error and either a rescan or manual read is required.

 

3. Error Correcting Using the Check Digit

Definition

X = Any single bar that is unreadable

           W = Sum of readable zip code integers

Y = Integer evenly divisible by 10 and greater than W

Z = Check Digit

 

Formula

X = Y - (W + Z)

or: any integer evenly divisible by 10 and greater  than the sum of all readable zip code integers minus the sum of all readable zip code integers plus the check digit.

 

Example

X = Y - (U1+U2+U3+U4+U5+?+U7+U8+U9 + Z)

X = Y - (9+5+1+1+0+2+4+8 + Z)

X = Y - (30 + Z)

Z = 8

X = Y - (30 + 8)

Y = 40

X + 40 - (30 + 8)

X = 2

 

The next code most of us are familiar with is the Universal Product Code (UPC) which is found on most consumer products. Gallian, (1991) tells us that a UPC identification number consists of twelve digits, each of which can be number from 0 to 9. Bar codes are a set of symbols used to represent alpha-numeric information. Basically, instead of seeing the number "1", or the letter "A", you would see a series of bars, both fat and thin, used to represent that number. (pg.194)

Systems ID explains that a number of bar code standards have been developed and refined over the years into accepted languages called symbologies. We would use different symbologies for different applications in the same way that we would use a bold or italic font to emphasize a particular line of text in a report. Different symbologies or "bar code fonts" are used for different applications. (20, Sept 2002) (http://www.systemid.com/education/beginners.asp?source=LSM062)

Burke, (1990) explains that barcode symbols are either identification labels or messages composed of one or more fields presented in an instrument-reader form. (pg.26)  One significant difference between zip codes and UPC codes is that the fields are different. Zip codes consist of ten blocks of five black modules (bars) which are read while the UPC code on the other hand reads the white spaces as well as the black bars. This particular type of coding allows for more information to be placed in a smaller space. One more feature that the UPC code possesses is that it has twelve blocks of seven modules.

Next is to establish a foundation in which we better understanding UPC bar code modules and how they are divided. In order to read a barcode it is best to first understand how they are designed. Below in table 3(a) the manufacture code is on the left and the product code is on the right. Representing each number are seven modules consisting of two bars and two spaces. The bars and blanks vary in width depending on how many modules they take up. In table 3(b) the numbers divided into 1's and 0's. Notice that the manufacture and product sides are opposites. The manufacture side where 1's are represented with black bars and 0's are blanks, and the product side consists of 1's as blanks and 0's as black bars. The purpose is that the codes can be scanned from either direction.

Table 3.

Freeman, (2001) tells us that the first digit identifies the kind of product. The next five digits identify the manufacturer. The next five digits are assigned by the manufacture to identify the product, and can include size, color, or other important information. The final digit is a check digit number. (pg 344)

In table 4 let's determine what each number is by counting the modules and checking to see which digit represents the pattern of bars and spaces.

Table 4.

In table 5 below I will explain how the math works in UPC coding. Thanks to the American Mathematical Society I can demonstrate how the check digit is used in error correction.

Table 5.

Example: Find the check digit for the UPC number:
                                     3 05212 90500 ?

1. sum the numbers in the odd positions, multiply by 3

2. sum the numbers in the even positions and add this sum to result 1
    find the next largest number that is evenly divisible by ten

3. subtract result 2 from result 3 to find the check digit number.

…      The digits in the odd positions are 3, 5, 1, 9, 5, and 0.
These sums to 23, which tripled yields 69.

…      The digits in the even positions are 0, 2, 2, 0, and 0.
These sum to 4, which, when added to 69, gives 73.

…      Thus, the check digit is 7, because 73 + 7 = 80 is divisible by 10.

Symbolically, if we denote the code string, including the check digit by:
            u₁u₂u₃u₄u₅u₆u₇u₈u₉u₁₀u₁₁u₁₂

We compute the check digit u₁₂ so that:
            R = 3(u₁ + u₃ + u₅ + u₇ + u₉ + u₁₁) + (u₂ + u₄ + u₆ + u₈ + u₁₀ + u₁₂)
            R  = 3 (3   +  5   +  1   +  9   +  5  +   0   ) + ( 0   +  2  +   2  +   0  +   0    +   ?  )

(12 Sept 2002) (http://www.ams.org/new-in-math/cover/barcodes4.htm)

We now have established the mathematical principals which allow us to check for errors. Let's take a look at UPC barcode in Table 6 which was created by Church and used for demonstration proposes. (31 Oct. 2002) (http://www.beakman.com/upc/barcode.html)  With it I will explain how to read and calculate the mathematical principals that apply to this bar code and determine if the check digit number is five.

Using the diagrams combination of numbers we will apply the same mathematical principal to this UPC bar code.
           

R = 3(u₁ + u₃ + u₅ + u₇ + u₉ + u₁₁) + (u₂ + u₄ + u₆ + u₈ + u₁₀ + u₁₂)
Plugging in the numbers, this is how it reads.
            R   = 3 (0   +   2   +   4   +   6   +   8   +   0)   +   ( 1  +  3   +   5   +   7   +   9   +   5 )

Table 6.

The UPC formula is some what similar to zip code error correction and   detection. Shown below are the algebraic steps for finding errors in the UPC code.

1. Assigning the UPC Check Digit

Definition

X = Check Digit

Y = 3(sum of all odd positioned integers) + sum of all even positioned integers

Z = Any integer evenly divisible by 10 and > Y

 

Formula

X = Z - Y

or: the check digit equals any integer evenly divisible by 10 and greater than 3 times the sum of all odd positioned integers plus the sum of all even positioned integers minus 3 times the sum of all odd positioned integers plus the sum of all even positioned integers

 

Example

X = Z - 3(U1+U3+U5+U7+U9+U11) + (U2+U4+U6+U8+U10)

X = Z - 3(0+2+4+6+8+0) + (1+3+5+7+9)

X = Z - 85

Z = 90

X = 90 - 85

X = 5

 

2. Error Checking Using the Check Digit

Definition

X = Any integer evenly divisible by 10

Y = 3(sum of all odd integers) + sum of all even positioned integers

Z = Check Digit

 

Formula

X = Z + Y

or: any integer evenly divisible by 10 equals 3 times the sum of all odd positioned integers plus the sum of all even positioned integers plus the check digit.

 

Example

X = Z + 3(U1+U3+U5+U7+U9+U11) + (U2+U4+U6+U8+U10)

X = Z + 3(0+2+4+6+8+0) + (1+3+5+7+9)

X = Z + 85

Z = 5

X = 5 + 85

X = 90

If X does not equal an integer evenly divisible by 10 then there is an error and either a rescan or manual read is required.

 

3. Error Correcting Using the Check Digit

Definition

X = Any single bar that is unreadable

W=3(sum of all readable odd integers) + sum of all even positioned readable integers

Y = Integer evenly divisible by 10 and greater than W

Z = Check Digit

Formula

X = Y - (W + Z)

or: any single bar that is unreadable equals any integer evenly divisible by 10 and greater than three times the sum of all readable odd positioned integers plus the sum of all readable even positioned integers minus the sum of three times the sum of all readable odd positioned integers plus the sum of all readable even positioned integers plus the check digit

 

Example

X = Y - (W + Z)

X = Y - 3(U1+U3+U5+U7+U9+U11) + (U2+?+U6+U8+U10)

X = Y - 3(0+2+4+6+8+0) + (1+?+5+7+9)

X = Y - (82 + Z)

Z = 5

X = Y - (82 + 5)

X = Y -   87

Y = 90

X = 90 - 87

X = 3

 

As stated before, the more complex the coding, the more difficult the math becomes and simply too difficult to explain. This is where I conclude.

CONCLUSION

There is no doubt that barcode technology has touched all our lives in one way or another. Everytime a product is bought or sold by a manufacturer, you can bet that a barcode related to that item is scanned and read. Manufactures are better able to keep accurate inventory which in turn keeps up with supply and demand. This technology is helping retailers deter theft with state of the art anti-shoplifting devices that go undetected by professional shoplifters.

Advancements are being made in barcode technology as our needs dictate change. Our hospitals have become safer since bar codes track medicines as well as our blood supply. The Army uses two foot long barcodes on their boats. Marathon runners wear barcodes. Loggers tag cut trees with codes.

Beyond barcoding, other encoding technologies continue to advance as well. Science and code technology go hand in hand. Researchers glued small bar codes to the backs of 100 bees and monitored their activities coming and going from a hive. Cows are imprinted with codes and the beef is tracked all the way to the grocery market case.

Currently sophisticated forms of identification are being used by Forensics Scientists who are able to solve crimes with just a trace of human DNA. Children's DNA is being placed into files to help authorities locate lost or missing children.

We currently carry credit cards, driver's licenses, ATM cards and such, all of which contain volumes of personal information that can be read with just one quick swipe. How many plastic cards must we carry anyway? Is their a better solution? If every human possess their very own genetic fingerprint and no two are alike, wouldn't it make sense that our gene structure might become our ID code of information? Is it possible that our personal genetic information can be made into a readable, scanable identity that holds volumes of information which can be carried or worn? Just imagine, no cards to be lost, no pin numbers to remember, no identities to be stolen. On the other hand, could this technology hinder our lives as we know it today? Perhaps we might become like the bees with barcodes attached to their backs or like the cows imprinted with a code, or then again, perhaps not.

Who's to say where this technology is going? Barcodes are continuing to evolve as needs change. One has to admit that the digital revolution is fascinating and this technology will certainly become more refined and useful into the future.

BIBLIOGRAPHY

BOOKS
Burke, Harry E. Barcode Engineering and Implementation.

Automatic Management Information Systems, Vol. 2
New York, 1990 (pg. 26)

Burke, Harry E. Handbook of Bar Coding Systems.
            Data Pathing Systems Division/NCR Corporation
            New York, 1984

Freeman, W. H. For All Practical Purposes. 5^th Edition
            New York, 2001 (pg. 344)

Erdei, William H. Bar Codes.
            Design, Printing and Quality Control
            Mexico, 1993

JOURNAL
Gallian, Joseph A. ìThe Mathematics of Identification Numbersî
            The College Mathematical Journal, (1991). Vol. 22, No. 3,
            (pg. 194)

INTERNET
Lasco Fittings
            History of Bar Code. 12 Sept 2002
            <http://www.lascofittings.com/BarCode-EDI/bc-history.htm>

American Mathematical Society
            The Digital Revolution.
            Barcodes: The Universal Product Code. 12 Sept 2002.
            < http://www.ams.org/new-in-math/cover/barcodes4.html >

Beakman's World
            Church, Jok. Beakman & Jax. 31 Oct. 2002
            <http://www.beakman.com/upc/barcode.html> 

Systems ID Warehouse
            Bar Codes for Beginners. 20, Sept,2002                   <http://www.systemid.com/education/beginners.asp?source=LSM062>