That's Maths: How barcodes and QR codes work

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 40 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?

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 corrected.

An example of an EAN-13 barcode can be found on the front page of this newspaper. 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. These QR codes, originally devised for stock control of motor parts, allow much greater data volumes for a given area.

QR stands for “quick response”. One commonly used version can encode 4,296 characters, equivalent to about three pages of text. The information is written in a zig-zag pattern that can be scanned using a QR code reader on a smartphone.

QR codes are more versatile than standard barcodes because they can store much more data. This may include web links, co-ordinates, emails, images and plain text. But can we be confident 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 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 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.

[ thatsmaths.com ]