A Code That Survives Sand

A Code Made of Stones

On 25 January 2013, at Arpoador, the rocky point at the end of Ipanema beach, Rio de Janeiro laid the first of its QR codes into the seafront promenade, made of the same black and white stones as the city’s famous sidewalk mosaics. Point a phone at it and a map opens, with notes on the place in Portuguese, Spanish or English. The city planned 30 of them.

The block in front of you is laid the same way, two stones to a square. Its pattern holds the address of this page, and your phone can read it off the screen. None of it is decoration: every square has a job, and some are there only to repair the others.

A block of seafront pavement with a QR code in it, cut out like a specimen · two stones to a square

Three Eyes

The QR code was released in 1994 by Denso Wave, then part of the car-parts maker Denso, and the car industry took it up to track parts through its factories. A team of two led by Masahiro Hara wanted a code a scanner could read quickly and from any angle. A reader’s first job is to find the code at all, and that is what the three big squares in its corners are for.

Cut across one along any line through its middle and you meet dark, light, dark, light, dark, in widths of 1:1:3:1:1. The team chose that ratio after surveying flyers, magazines and cardboard boxes for the one that turned up least in print. Between the eyes run two rows of alternating squares that give the reader the grid’s spacing, and a smaller fourth eye helps it correct for a slanted view.

Letters in a Zigzag

Every letter of the address becomes a byte: eight squares, dark for 1 and light for 0. They are laid in a column two squares wide, snaking up from the bottom-right corner, then down the next column, around the eyes and the timing rows. A short header goes first, saying “bytes follow” and how many.

The address takes 29 bytes. The code has room for 44, and a standard padding pattern fills the rest. Then come 26 more, shown in blue. They spell nothing. They are the spare bytes, and they are why this code survives what comes next.

The Mask

Laid out raw, the bytes could leave big solid patches, long stripes or, by chance, a shape that looks like an eye, all of which confuse a camera. So the encoder tries eight fixed patterns, swapping dark and light wherever a pattern says so, scores each result for patches, stripes, false eyes and an uneven mix of dark and light, and keeps the one that scores best.

To swap the squares back, the reader has to know which pattern was used. That, along with how much spare the code carries, is written in 15 squares beside the eyes (shown in violet), twice over and with a small error-correcting code of its own, because if it can’t be read, nothing else can.

Sand on the Promenade

Before the first code was laid, the city was already worried that on windy days sand blown off the beach would make it hard to read, and talked of varnishing the stones. Let the wind blow. Wherever sand buries a dark square, the reader sees light, and every byte that loses a square is now wrong (marked in red).

The code still reads. Reed–Solomon codes, published by Irving Reed and Gustave Solomon in 1960, compute every spare byte from all of the data bytes at once, in an arithmetic of just 256 numbers where adding and multiplying never lead outside them. When bytes go wrong, the spare bytes stop agreeing with the data, and the way they disagree points to which bytes are wrong and what they should be. Each repair costs two spare bytes, one to find where and one to find what. This code’s 26 spare bytes can repair any 13.

Where It Gives Up

More sand. Past 13 wrong bytes, the reader stops. It doesn’t guess: the spare bytes tell it the damage is beyond repair, and it reports nothing rather than something wrong. A misreading is possible, but only if the damage happens to turn the code into a different valid one, which is very rare.

Whoever makes a code chooses how much spare it carries: at levels L, M, Q and H, about 7, 15, 25 or 30 percent of all its bytes can be restored. More spare takes more squares for the same message. Watch the same sand fall on the same address made at level H: the code grows from 29 squares across to 33, and reads again. Codes with a logo in the middle work this way too: the logo is damage they were built to survive.