Reed-Solomon
Almost every explanation of this code starts with a generator polynomial and syndromes. That view came later. Reed and Solomon read the message as the coefficients of a single polynomial and send its VALUE at several different places, and the whole code follows from one fact about curves: four points pin down a curve of degree three, and it does not matter which four. Send eight, lose any four in the post, and the four that arrive are enough. Nothing is repeated, nothing is guessed, and the recovery is the same arithmetic a school algebra class does with simultaneous equations, in a field where addition is exclusive or.
Four bytes, eight values, and any four of them will do
1 Four bytes, read as the coefficients of one polynomial over the field
Four bytes. Pick a message; the same four numbers are about to become the coefficients of one polynomial.
| byte | hex | value | as text |
|---|---|---|---|
| 0 | 42 | 66 | B |
| 1 | 59 | 89 | Y |
| 2 | 54 | 84 | T |
| 3 | 45 | 69 | E |
Read as one polynomial, this message is P(x) = 42 + 59x + 54x^2 + 45x^3, with the coefficients in the field and the plus signs meaning exclusive or.
2 That polynomial evaluated at eight points, which is the codeword that gets sent
Eight places to look at one curve
The eight points are successive powers of the field's generator, so they are all different and none of them is zero. Each row is what the polynomial equals there.
| symbol | at x | value sent |
|---|---|---|
| 0 | 01 | 0A |
| 1 | 02 | AF |
| 2 | 04 | 82 |
| 3 | 08 | E0 |
| 4 | 10 | E2 |
| 5 | 20 | F4 |
| 6 | 40 | E5 |
| 7 | 80 | BC |
Eight values of one curve of degree three. No position in the codeword is reserved to carry a message byte, which is what makes the code non-systematic: it sends what the polynomial IS at eight places rather than the polynomial itself. For this message none of the eight values happens to equal one of the four bytes either, which is a coincidence and not the reason.
3 Symbols erased by hand, and the equations solved from whichever four survive
MeasuredErase some, and solve for the curve
Press a symbol to lose it. Four have to survive; which four does not matter.
| byte | recovered | as text | right |
|---|---|---|---|
| 0 | 42 | B | yes |
| 1 | 59 | Y | yes |
| 2 | 54 | T | yes |
| 3 | 45 | E | yes |
0 symbols erased, 8 left, and four is enough. Interpolating through them and solving the matrix returned the same four bytes.
4 Every one of the seventy ways to lose four, and the one loss it refuses to guess at
Every way of losing them, not the one on the screen
| lost | ways to lose them | recovered | wrong |
|---|---|---|---|
| 0 | 1 | 1 | 0 |
| 1 | 8 | 8 | 0 |
| 2 | 28 | 28 | 0 |
| 3 | 56 | 56 | 0 |
| 4 | 70 | 70 | 0 |
| 5 | 56 | 0 | refused |
163 erasure patterns recover this message exactly, and all 56 ways of losing one more are refused.
The marked row is the one that matters. Five gone leaves three survivors and three points do not pin down a curve of degree three: a whole family of messages passes through them, and the page can print two of them that agree with every symbol that arrived. That is the difference between a code that works and a code that appears to. A decoder that answered anyway would be right sometimes, which is worse than useless, because nothing downstream would know which times.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| every way of losing four of the eight symbols returns the same four bytes | yes | all 70 of them, which is every subset of size four |
| and the two ways of solving for the curve agree on all of them | yes | Lagrange basis polynomials against Gaussian elimination on the Vandermonde matrix, 70 times |
| for every message here, not only the one on the screen | yes | 4 messages times 70 erasure patterns, 280 recoveries |
| losing none, one, two, three or four all recover | yes | 163 erasure patterns in total, which is every way of losing four or fewer of the eight |
| losing five is refused every time, never guessed at | yes | all 56 ways of losing five symbols say no |
| and it can show two different messages that both fit what arrived | yes | for each of the 56 cases, two distinct messages agreeing with every surviving symbol |
| the field's fast table agrees with the rule it was built from, everywhere | yes | all 65,025 non-zero products, table against carry-less multiply and reduce |
| every non-zero symbol has an inverse and it multiplies back to one | yes | all 255 of them |
| a symbol equalling a message byte is a coincidence, not the message being carried | yes | BYTE has 0 symbols equal to one of its bytes and four zeroes has 32, on the same code: whether the values coincide depends on the message, while no position ever carries a byte verbatim |
| any two of these messages differ in at least five of the eight symbols | yes | the separation the code is built to have, checked on every pair here |
What is real here, and what is not
A shortened instance of the 1960 code, and not a systematic one
The paper reads the message as coefficients and sends the polynomial's values, and no position in the codeword is reserved to carry a message byte. That is what non-systematic means, and it is not the same as the values happening to differ: on the all-zero message every symbol equals every byte, and the code is no more systematic for it. Eight symbols over this field is also a shortened instance rather than the full-length code, which would run to 255 symbols. Real Reed-Solomon as shipped in CDs, QR codes and RAID is usually arranged so the data does appear, which is convenient and is a later rearrangement. Showing that version would be showing something other than what the page cites.
Erasures, not errors
Everything here assumes the receiver knows WHICH symbols are missing. That is the erasure case, it is the easier half of the subject, and it is what the whole first panel is about. Correcting an error whose position is unknown costs twice as many symbols, because the bound is that twice the errors plus the erasures must not exceed the parity. Practical decoders commonly reach for syndromes and an error-locator method such as Berlekamp-Massey, though those are one route rather than a requirement, and none of that machinery is here. The 1960 paper does not use the word erasure at all; the distinction was named later.
The field is built from its rule, not typed in
GF(2 to the 8) modulo 0x11D, the polynomial the CD and the QR code both use. The exponent and logarithm tables that make multiplication fast are generated by repeatedly multiplying by the generator, and the check below compares every one of the 65,025 non-zero products against carry-less multiply and reduce done the long way. A memorised table with two rows exchanged passes every structural test there is.
Recovered twice, by two routes that share no code
The bytes on the screen come from Lagrange interpolation, which builds a basis polynomial per point and never forms a matrix. They are checked against Gaussian elimination on the Vandermonde system, which is the route RFC 5510 specifies and has no basis polynomials in it. Two implementations that share a bug agree perfectly, so they were written to share nothing.
The refusal is demonstrated, not asserted
With five symbols gone, the page does not say recovery is impossible. It produces two different four-byte messages that both reproduce every symbol that arrived, and it re-encodes them to check that rather than trusting how they were built. Ambiguity you can see beats ambiguity somebody tells you about.
Eight symbols, and a CD uses far more
The code here is eight symbols carrying four bytes, which is a rate of one half and is chosen so the page can be exhaustive: 70 ways to lose four, 56 ways to lose five, all of them run. CIRC on a compact disc is two interleaved codes at rates 28/32 and 24/28, and QR codes run several sizes. The mechanism is the same and the numbers on this page are this page's.
Sound: no
What this page measures is how many erasure patterns recover, which is a count. Interleave, which is where this subject arrives on a compact disc, earned a sound because the thing it measures is an arrangement in time. This one is not.
Sources
- RFC 5510, Reed-Solomon Forward Error Correction Schemes — specifies erasure decoding as inverting a Vandermonde submatrix over the field, which is the second of the two routes this page solves with.
- Crossref's record for Reed and Solomon's Polynomial Codes Over Certain Finite Fields, which is where the journal, the June 1960 date and the page range come from. The paper itself is behind a cookie wall that returns a page with none of its text on it, so it is not cited as if it had been read here.
- Logical Art, the studio this belongs to.