Reed–Solomon error correction, worked by hand

A check digit can tell you that a number is wrong. It cannot tell you what the number should have been. Reed–Solomon codes can, and they are why a scratched QR code still scans.

I wrote about what that means on a loading bay in a note about scratched labels. This one is the mechanism itself, worked through with numbers small enough to check on paper.

The idea in one sentence

Treat your data as the coefficients of a polynomial, and send more values of that polynomial than you strictly need.

A line is fixed by any two of its points. A polynomial of degree less than k is fixed by any k of its values. So if you send n values with n greater than k, the receiver can lose some of them and still rebuild the polynomial, and with it the data. The extra n − k values are the parity.

Encoding: four numbers mod 7

Take two data symbols, 3 and 2, so k = 2. Use them as the coefficients of a line: p(x) = 3 + 2x. Do all arithmetic mod 7, so every value stays in 0 to 6.

Evaluate the line at four points, n = 4: p(0) = 3, p(1) = 5, p(2) = 7 mod 7 = 0, p(3) = 9 mod 7 = 2. The codeword is 3, 5, 0, 2. Two of the four symbols are data and two are parity.

Two symbols lost: rebuilding them

Say positions 0 and 2 are destroyed, and you know which ones. That is called an erasure. You still have p(1) = 5 and p(3) = 2, two points on a line, which is enough.

The slope is (2 − 5) / (3 − 1). Mod 7, 2 − 5 = −3, which is 4, and dividing by 2 means multiplying by the inverse of 2, which is 4, because 2 × 4 = 8 = 1 mod 7. So the slope is 4 × 4 = 16 = 2 mod 7. The intercept is 5 − 2 × 1 = 3.

The line is 3 + 2x again. The data is back, and so are the two lost symbols. With n − k = 2 parity symbols, any two erasures can be repaired.

One symbol wrong: finding it

An error is harder than an erasure, because you do not know where it is. Say the codeword arrives as 3, 5, 6, 2: the symbol at position 2 was changed from 0 to 6, and nothing marks it.

Ask which line agrees with the most received values. There are 49 possible lines mod 7. Exactly one of them, 3 + 2x, agrees with three of the four values. No other line agrees with more than two. The odd one out, position 2, is the error, and the line says it should be 0.

That is the rule in general: with n − k parity symbols you can correct up to (n − k) / 2 errors at unknown positions. Finding a symbol costs one parity symbol and fixing it costs another, which is why an error costs twice what an erasure does. Real decoders do not try every polynomial; they compute syndromes and solve for the error positions with algorithms such as Berlekamp–Massey. The answer is the same one this search finds.

The numbers that matter

That last row is why Reed–Solomon codes are called maximum distance separable. No code with the same n and k can do better, and that is a proved bound, not a property of one implementation.

Why it needs a finite field

Rebuilding the line needed division: dividing by 2 became multiplying by 4. Ordinary integers do not allow that without leaving the integers, and real numbers would bring rounding errors into exact data. A finite field is a set of numbers where addition, subtraction, multiplication and division all work exactly and the results never leave the set. The integers mod a prime, like mod 7, are the simplest example.

Computers prefer fields of size 2^m, written GF(2^m), so that each symbol is a whole number of bits. QR codes use GF(256), where each symbol is one byte.

The field size is a choice, and it should follow the data. For sequence data over a small alphabet, such as twenty amino acids, I used GF(32): one symbol holds one letter with room to spare, instead of spending a whole byte on it. The toolkit is open, at doi.org/10.6084/m9.figshare.32963456.

Symbols, not bits

One property makes Reed–Solomon match real damage. It counts damaged symbols, not damaged bits. Eight bad bits inside one byte cost one symbol. A scratch, a water drop or a crease takes out a patch, which is a short run of neighbouring symbols. That is why the same family of codes protects QR codes and Data Matrix labels, and was used in CDs and DVDs, where damage also comes in bursts.