SafekipediaReed–Solomon error correction
Adapted from Wikipedia · Adventurer experience
Reed–Solomon codes are a special kind of error-correcting code used to keep information safe when it is stored or sent. They were created by Irving S. Reed and Gustave Solomon in 1960 and are important in many everyday technologies. You might use them without even knowing it when you listen to music on a CD, watch a movie on a DVD or Blu-ray disc, scan a QR code, or connect to the internet through DSL or WiMAX.
These codes work by adding extra symbols, called check symbols, to blocks of data. This helps find and fix mistakes that can happen when data is copied, sent, or stored. For example, if a few pieces of information get mixed up, Reed–Solomon codes can often figure out what the correct information should be. This makes sure that important data, like the music on your MiniDisc or the data sent in satellite communications, arrives correctly even if some errors occur.
Reed–Solomon codes are especially good at handling many small mistakes that happen close together. They can also correct problems when the exact places where mistakes happen are known. Because of their usefulness, these codes are used in many systems, from RAID 6 storage to DVB and ATSC broadcasting, helping keep our digital world running smoothly.
History
Reed–Solomon codes were created in 1960 by Irving S. Reed and Gustave Solomon. These codes help fix mistakes in data, so information stays correct even if some parts get lost or mixed up.
Since then, Reed–Solomon codes have been used in many technologies, like compact discs and digital storage devices. They were also used in space missions, such as the Voyager program, to keep important data safe during its journey.
Applications
Reed–Solomon coding is used in many storage systems to fix mistakes caused by scratches or marks on the media. It is important for compact disc and is also used in DAT and DVD. This helps make sure music and data can still be read even if the surface is damaged.
Reed–Solomon error correction is also used in two-dimensional bar codes such as PDF-417, MaxiCode, Datamatrix, QR Code, Aztec Code and Han Xin code. This lets bar codes still be read even if part of them is hidden or damaged. It is also used in some data transmission systems like xDSL and in space communications, such as the images sent back by the Voyager program.
| Years | Code | Mission(s) |
|---|---|---|
| 1958–present | Uncoded | Explorer, Mariner, many others |
| 1968–1978 | convolutional codes (CC) (25, 1/2) | Pioneer, Venus |
| 1969–1975 | Reed–Muller code (32, 6) | Mariner, Viking |
| 1977–present | Binary Golay code | Voyager |
| 1977–present | RS(255, 223) + CC(7, 1/2) | Voyager, Galileo, many others |
| 1989–2003 | RS(255, 223) + CC(7, 1/3) | Voyager |
| 1989–2003 | RS(255, 223) + CC(14, 1/4) | Galileo |
| 1996–present | RS + CC (15, 1/6) | Cassini, Mars Pathfinder, others |
| 2004–present | Turbo codes | Messenger, Stereo, MRO, MSL, others |
| est. 2009 | LDPC codes | Constellation, M2020, MAVEN |
Constructions (encoding)
Reed–Solomon codes are a type of error-correcting code created in 1960. They are used in many everyday technologies like CDs, DVDs, and QR codes to fix small errors in data.
These codes work by treating data as a set of symbols. The original idea was to treat the data as parts of a math equation called a polynomial. By evaluating this polynomial at different points, a codeword is created. This method helps in detecting and correcting errors that might occur during data storage or transmission.
| n | Sn+1 | d | C | B | b | m |
|---|---|---|---|---|---|---|
| 0 | 732 | 732 | 197 x + 1 | 1 | 732 | 1 |
| 1 | 637 | 846 | 173 x + 1 | 1 | 732 | 2 |
| 2 | 762 | 412 | 634 x2 + 173 x + 1 | 173 x + 1 | 412 | 1 |
| 3 | 925 | 576 | 329 x2 + 821 x + 1 | 173 x + 1 | 412 | 2 |
| i | Ri | Ai |
|---|---|---|
| −1 | 001 x4 + 000 x3 + 000 x2 + 000 x + 000 | 000 |
| 0 | 925 x3 + 762 x2 + 637 x + 732 | 001 |
| 1 | 683 x2 + 676 x + 024 | 697 x + 396 |
| 2 | 673 x + 596 | 608 x2 + 704 x + 544 |
Reed Solomon original view decoders
The decoders in this section see a codeword as a list of values from a polynomial. Both the encoder and decoder use the same fixed values. The decoder tries to find the original polynomial from the message it receives.
A perfect way to fix errors would be to find the polynomial that best fits the received values. But this can be slow because it needs to check many options.
Later work made better decoders. For example, a decoder from 1986 uses a simpler method. Newer updates keep making error correction faster for data transmission.
| i | Ri | Ai |
|---|---|---|
| -1 | 001 z4 + 000 z3 + 000 z2 + 000 z + 000 | 000 |
| 0 | 785 z3 + 213 z2 + 666 z + 055 | 001 |
| 1 | 658 z2 + 858 z + 323 | 200 z + 141 |
| 2 | 294 z + 709 | 905 z2 + 020 z + 925 |
Images
This article is a child-friendly adaptation of the Wikipedia article on Reed–Solomon error correction, available under CC BY-SA 4.0.
Images from Wikimedia Commons. Tap any image to view credits and license.