Correcting errors

Reed-Solomon: QR codes, CDs and RAID

Correcting entire bursts

Hamming corrects an isolated error, but on a scratched CD or a torn QR code, entire blocks disappear. The Reed-Solomon code is designed for this: it works not on isolated bits but on symbols (packets of bits), and corrects symbols that are entirely erased or wrong. It is what makes QR codes, CDs, DVDs and RAID storage so robust.

The idea: overdetermining a curve

The geometric intuition is beautiful. Two points are enough to define a line; but if you transmit more points than necessary, all lying on that same line, then you can lose a few points and still recover the original line from the remaining ones.

Reed-Solomon idea (overdetermining a curve):

data -> define a curve (polynomial)

   *       *                        (data points)
      *       *   *     *            (+ redundant points, on the SAME curve)
   ----------------------
   |  X  |     |  X  |               (X = lost or damaged points)

-> enough valid points remain to rebuild the whole curve,
   and therefore to recover the lost points

Erasures and errors

Reed-Solomon distinguishes two cases. An erasure is a symbol known to be lost (known position): easy to rebuild. An error is a wrong symbol whose position is unknown: more costly, because it must first be located. With r redundancy symbols, up to r erasures, or r/2 errors, can be corrected.

Why it is everywhere

Its strength is resisting clustered damage, which is exactly what happens in real life: a scratch damages neighboring symbols, a QR code can lose up to 30% of its surface and remain readable. Reed-Solomon is often combined with interleaving, which scatters the symbols, so that a physical burst turns into isolated errors that are easier to correct.

Classic pitfall