Bar codes and QR codes aren’t just generic emblems of the consumer world. There’s something special about them.
These small black-and-white images encode data that can be read by handheld scanners or smartphones. Since the device often obtains an imperfect image (for instance, when your hand shakes while taking a photo), these codes are designed in a format that allows for error detection. When a bar code is scanned incorrectly, the scanner can tell an error occurred — and sometimes even correct it.
The grids of black-and-white squares at the bottom of this column represent messages consisting of the eight most common letters of the alphabet. (Similar schemes can be used to encode any message.) Each four-by-four grid encodes three letters. Each row of the three-by-three subgrid in the upper left encodes a single letter, as described in the chart just below. The remaining row and column are filled in so every row and column has an even number of shaded squares.
For example, the following grid is an encoding of the word “HAT”: the first three squares of the top row encode the letter “H”, the first three squares on the second row encode “A”, and so on.
Crucially, the scanner knows that every row and column should have an even number of squares. So if a bad scan turns one square of the four-by-four grid from black to white, or vice versa, then some row and column will have an odd number of shaded squares.
Now consider the following grid:
At first glance, this looks like an encoding of the word “TEN”. But note that the first column and the third row each have an odd number of shaded squares. This breaks the rule that a correct grid contains an even number of shaded squares in each row or column. In other words, there’s an error!
Fortunately, this encoding scheme allows not only error detection, but also error correction. Observe that changing the single square in the first column and third row from shaded to unshaded will result in a grid that obeys the rule. This is the only valid grid that can be obtained changing only a single square. The corrected grid encodes the message “TEA”.
In the message below, each of the four-by-four grids contain an error. Can you figure out the original message? Giving it a try will leave you with new respect for all the work the humble bar code does.Aloni Cohen, Sunoo Park, and Adam Sealfon are members of MIT’s Cryptography and Information Security group.
SOLUTION: The bar code images spell out “SHOESHINE.”