Error correction

A probe far from home shouts in a whisper, and cosmic noise flips some of its bits on the way. Error-correcting codes add carefully chosen extra bits so the receiver can find the flips and put them back, without ever asking for a resend.

Hamming(7,4) wraps every 4 data bits in 3 parity bits. Column j of its parity-check matrix H is j written in binary, so multiplying the received 7 bits by H gives a 3-bit syndrome that is zero for a clean block and otherwise spells out the position of a single flip. Two flips fool it: the syndrome points at an innocent bit and the decoder makes things worse.

Reed-Solomon works on whole bytes, as numbers in the field GF(256). A block is the coefficients of a polynomial that must vanish at the 2t points α⁰ to α^(2t-1), the roots of the generator g(x). The receiver evaluates the block there to get 2t syndromes, Berlekamp-Massey turns them into an error locator Λ(x), a Chien search finds its roots (where the bad bytes are) and Forney's formula gives the value to add back. Any t bad bytes are fixed, however many of their bits flipped, which is why it shrugs off bursts. Voyager 2 sent its pictures of Uranus and Neptune home wrapped in RS(255,223).

A payload handed over from Deflate is a real raw Deflate stream, so at home each lane's bits go through inflate, a decoder built into this page, and your browser's own DecompressionStream checks the verdict. A clean copy gives back the probe's words exactly. A damaged one either stops at a code that cannot exist, such as a copy from before the start or an incomplete code table, or worse, inflates into confident nonsense.

noise is random, but the code turns it into algebra: a few equations pin down exactly where the damage is.