The same 1960 maths protects Voyager's pictures, your CDs and every QR code.
Reed–Solomon codes add carefully calculated extra data so that errors can be found and fixed without resending anything. Invented in 1960, they carried Voyager's images home, let CDs play through scratches, and keep damaged QR codes readable. A CD can shrug off a gap of about 2.5 millimetres.
Irving Reed and Gustave Solomon, then at MIT's Lincoln Laboratory, introduced their codes in a 1960 paper titled 'Polynomial Codes over Certain Finite Fields'. The idea is to treat a block of data as a set of symbols and add a number of check symbols calculated from them. With a given number of extra symbols, the code can locate and correct errors at unknown places up to half that number, or fill in twice as many gaps if it already knows where they are.
The early catch was decoding: the original method was impractical for anything but simple cases. Better algorithms followed, notably the Berlekamp–Massey decoder of 1969. In 1977 the Voyager probes used Reed–Solomon coding combined with another type of code to send back their pictures, a pairing that became standard for deep-space and satellite communications. Later versions served Galileo, Cassini and the Mars rovers, performing close to the theoretical limit.
The compact disc of 1982 was the first mass-market product to use strong error correction. It layers two Reed–Solomon codes with interleaving, which scatters neighbouring data across the disc so that one scratch damages a little of many blocks rather than all of one. The result can fully correct bursts of up to about 4,000 bits, around 2.5 millimetres of disc surface, so most skips are caused by the laser jumping track, not unfixable damage.
The same principle is everywhere: DVDs and Blu-ray discs, DSL broadband, digital TV broadcasting, RAID 6 storage arrays, and nearly all two-dimensional barcodes, including QR codes, which treat unreadable patches as gaps to be filled. It is one of the least-known pieces of maths that most people use every day.
Source: Wikipedia — Reed–Solomon error correction · Text summarised from Wikipedia (CC BY-SA 4.0)
