TI-210Technology1960

A message can survive losing pieces of itself

Reed–Solomon codes add extra symbols so a receiver can rebuild ones that were erased or corrupted. Voyager used them. A compact disc uses them. A scratch need not be a click.

Established2 min read

Irving Reed and Gustave Solomon, in 1960, constructed codes over finite fields in which any portion of the received word, if long enough, determines the original. You may lose symbols up to a budget. Past the budget the reconstruction fails cleanly rather than almost working. The Voyager probes, photographing the outer planets on a transmitter of tens of watts, leaned on this and on a convolutional code wrapped around it. The pictures were not a stronger radio. They were a code that tolerated a vicious channel.

On a compact disc the same idea, cross-interleaved so that a scratch ruins many short stretches instead of one fatal one, turns a gouge into samples the player can interpolate or conceal. The silence where a scratch would have been is the code spending its budget. There is a budget. A bad enough disc still wins.

Caveats

  • Not every scratch is inaudible, and not every deep-space dropout is recoverable. The code specifies how much damage it can bear. The marketing specifies nothing.
  • Later codes come closer to Shannon’s limit. Reed–Solomon is not the last word. It is the word that made the method obvious.

Sources

  1. 1Reed I. S., Solomon G.. Polynomial Codes over Certain Finite Fields. Journal of the Society for Industrial and Applied Mathematics 8, 1960.

Related