Barcodes and QR Codes: Zebra stripes and Leopard spots

Barcodes and QR codes are described in this week’s That’s Maths column in The Irish Times (TM060, or search for “thatsmaths” at irishtimes.com).

EAN-13 barcode.

Virtually everything that you buy in your local supermarket has a curious little zebra-like pattern the size of a postage stamp printed on it. Barcodes, originally devised about forty years ago to label railroad cars, are now universal on consumer products.

But how do they work, and how can we be confident that they are scanned accurately and that we are charged the correct amount for our trolley of groceries?

EAN-13

There are several symbologies, or systems of embedding information in barcodes. In the EAN-13 system, the information is contained in a 13-digit number, each digit from 0 to 9 being represented by a unique sequence of two bars and two spaces of varying widths, with a total width of seven units per digit.

The beginning, middle and end of the code are marked by two thin bars. The digits are in two groups of six with an additional single digit to start. The code is optically scanned by a laser with a high level of accuracy.

The final digit is a check-digit used to detect errors. A simple example illustrates the idea: if the information digits are added together, then the check-digit is chosen so that the total of all 13 digits is a multiple of 10. Thus, if the information digits are 123 456 789 012, which sum to 48, the check-digit is 2, making a grand total of 50. If a total is found that is not divisible by 10, we know that there must be an error.

EAN-13 uses a more sophisticated method of checking. Digits are cleverly weighted so as to trap common errors. This enables single digit errors and most two-digit errors, such as transpositions, to be detected and also corrected.

An example of an EAN-13 barcode is shown above. The ISBN numbers on books contain a similar check-digit capable of detecting a range of errors. Serial numbers on currency notes also have error detecting check-digits.

QR Codes

Recently, more intricate two-dimensional barcodes, that look like miniature Mondrian paintings, have started to appear. They are more like leopard skins than the zebra stripes of barcodes. Originally devised for stock control of motor parts, these QR codes allow much greater data volumes for a given area.

QR Code linking to this blog.

QR stands for Quick Response code. One commonly-used version can encode 4,296 characters, equivalent to about three pages of text. The information is written in a zigzag pattern that can be scanned using a QR code reader on a smart phone.

QR codes are more versatile than standard barcodes because they can store much higher volumes of data, which may include web links, geo-coordinates, emails, images and plain text.

But can we be confident that a QR code is scanned accurately? Yes, because the encoding uses a sophisticated mathematical technique called the Reed-Solomon error correcting algorithm.

The use of barcodes and QR codes goes far beyond products in the supermarket. They have become common in a variety of contexts since their first use in 1974 when a packet of Wrigley’s chewing gum was checked out.

They are now found on patient identification tags in hospitals, on airline luggage labels, boarding passes, registered mail stickers and cinema tickets. Many more applications are likely in the future.

*        *        *        *        *        *

Peter Lynch’s book about walking around the coastal counties of Ireland is now available as an ebook (at a very low price!). For more information and photographs go to http://www.ramblingroundireland.com/