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

On each box unloaded fromthe truck, I marked the wholesale price and date with a felt marker pin. At thetime 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 handcalculator to figure the markup price and stamp or sticker the price on eachitem.

Little did I know thatbarcode technology was on its way to stores and businesses all around theworld. Perhaps my job could have been easier. I heard that this new technologypromised substantial advantages to companies. It guaranteed improvements inproductivity, accuracy and profitability. Well, except for the little mom andpop stores like the one I worked at. The technology at the time was hopelesslyexpensive.

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

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

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

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

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

Since Woodland was working forIBM at the time, he had approached them with an offer, asking for help infurthering the development of the bar code. IBM wasn't interested in helpingthem but was interested in buying the patent. IBM made an offer to buy thepatent but Silver and Woodland declined because they felt they could get morefor their ideas. Philco made them a good offer and they sold their patent tothem. Lasco Fittings states that in1962 Philco bought the patent. Philco later sold the patent to RCA and itwasn't long before RCA made advancements which caused this technology toblossom. (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 everybusiness used some type of coding system. Some industries needed a more complexcoding system which was 100 percent accurate. Others needed barcodes which heldmore information. As a result a variety of barcode systems were developed withdifferent error check and error correcting algorithms. Some of which can beseen in Table 1 below.  Gallian,Winters, (1991) shows different varying percentages in errordetection system algorithms. As the error rate diminishes the complexity of themath increases. (pg550) Most of the math formulas used incomplex error correction is so complex that it is too difficult to explain. Forthis reason I will only emphasize two types of barcodes, the Postnet and theUPC code.

Table 1.

The Postnet code used by theU.S. Postal Service is found on many pieces of commercial mail yet most of usare 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 tenthcheck digit as well as find and correct an incorrect or missing number.

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

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

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

Table 2.

Zip Code barcodes can beexpressed in an algebraic formula. Table 2(b) I will demonstrate error codedetection, first by defining the formula, present the formula and then give anexample. Table 2(c) shows solving for error correction, finding the incorrector missing digit using the check digit.

1. Assigning the CheckDigit

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 greaterthan 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 theCheck 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 codeintegers 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

IfX does not equal an integer evenly divisible by 10 then there is an error andeither a rescan or manual read is required.

3. Error Correcting Usingthe 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 minusthe 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 arefamiliar with is the Universal Product Code (UPC) which is found on mostconsumer products. Gallian, (1991) tells us thata UPC identification number consists of twelve digits, each of which can benumber from 0 to 9. Bar codesare a set of symbols used to represent alpha-numeric information. Basically, insteadof seeing the number "1", or the letter "A", you would seea 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 beendeveloped and refined over the years into accepted languages calledsymbologies. We would use different symbologies for different applications inthe same way that we would use a bold or italic font to emphasize a particularline 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 symbolsare either identification labels or messages composed of one or more fieldspresented in an instrument-reader form. (pg.26)  Onesignificant difference between zip codes and UPC codes is that the fields aredifferent. Zip codes consist of ten blocks of five black modules (bars) whichare read while the UPC code on the other hand reads the white spaces as well asthe black bars. This particular type of coding allows for more information tobe placed in a smaller space. One more feature that the UPC code possesses isthat it has twelve blocks of seven modules.

Next is toestablish a foundation in which we better understanding UPC bar code modulesand how they are divided. In order to read a barcode it is best to firstunderstand how they are designed. Below in table 3(a) the manufacture code ison the left and the product code is on the right. Representing each number areseven modules consisting of two bars and two spaces. The bars and blanks varyin width depending on how many modules they take up. In table 3(b) the numbersdivided into 1's and 0's. Notice that the manufacture and product sides areopposites. The manufacture side where 1's are represented with black bars and0's are blanks, and the product side consists of 1's as blanks and 0's as blackbars. 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 ofproduct. The next five digits identify the manufacturer. The next five digitsare 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 numberis by counting the modules and checking to see which digit represents thepattern of bars and spaces.

Table 4.

In table 5 below I willexplain how the math works in UPC coding. Thanks to the AmericanMathematical Society I can demonstrate how the check digit is used in errorcorrection.

Table 5.

Example: Find the checkdigit for the UPC number:
                                    3 05212 90500?

1. sum the numbers in the oddpositions, multiply by 3

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

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

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

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

·     Thus, thecheck 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)

Wenow have established the mathematical principals which allow us to check forerrors. Let's take a look at UPC barcodein Table 6 which was created by Church and used for demonstrationproposes. (31 Oct.2002) (http://www.beakman.com/upc/barcode.html)  With itI will explain how to read and calculate the mathematical principals that applyto this bar code and determine if the check digit number is five.

Using the diagramscombination of numbers we will apply the same mathematical principal to thisUPC 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 formulais some what similar to zip code error correction and   detection. Shown below are the algebraic steps forfinding errors in the UPC code.

1. Assigning the UPCCheck 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 greaterthan 3 times the sum of all odd positioned integers plus the sum of all even positionedintegers minus 3 times the sum of all odd positioned integers plus thesum 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 Usingthe 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 oddpositioned integers plus the sum of all even positioned integers plusthe 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

IfX does not equal an integer evenly divisible by 10 then there is an error andeither a rescan or manual read is required.

3. Error Correcting Usingthe Check Digit

Definition

X= Any single bar that is unreadable

W=3(sumof 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 by10 and greater than three times the sum of all readable odd positioned integersplus the sum of all readable even positioned integers minus the sum ofthree times the sum of all readable odd positioned integers plus the sum of allreadable 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 morecomplex the coding, the more difficult the math becomes and simply toodifficult to explain. This is where I conclude.

CONCLUSION

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

Advancements are being made in barcodetechnology as our needs dictate change. Our hospitals have become safer sincebar codes track medicines as well as our blood supply. The Army uses two footlong barcodes on their boats. Marathon runners wear barcodes. Loggers tag cuttrees with codes.

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

Currently sophisticated forms of identification are being used by ForensicsScientists 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 ormissing children.

We currently carry credit cards, driver'slicenses, ATM cards and such, all of which contain volumes of personalinformation that can be read with just one quick swipe. How many plastic cardsmust we carry anyway? Is their a better solution? If every human possess theirvery own genetic fingerprint and no two are alike, wouldn't it make sense thatour gene structure might become our ID code of information? Is it possible thatour personal genetic information can be made into a readable, scanable identitythat holds volumes of information which can be carried or worn? Just imagine, nocards to be lost, no pin numbers to remember, no identities to be stolen. Onthe 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 orlike 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 thedigital revolution is fascinating and this technology will certainly becomemore refined and useful into the future.

BIBLIOGRAPHY

BOOKS
Burke, Harry E. BarcodeEngineering and Implementation.

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

Burke, Harry E. Handbook of Bar CodingSystems.
            DataPathing Systems Division/NCR Corporation
            NewYork, 1984

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

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

JOURNAL
Gallian, Joseph A. “The Mathematicsof Identification Numbers”
            TheCollege Mathematical Journal, (1991). Vol. 22, No. 3,
            (pg.194)

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

American MathematicalSociety
            TheDigital 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
            BarCodes for Beginners. 20, Sept,2002                   <http://www.systemid.com/education/beginners.asp?source=LSM062>