SafekipediaReed–Solomon error correction
Adapted from Wikipedia · Discoverer experience
Reed–Solomon codes are a special kind of error-correcting code used to keep information safe during storage and transmission. They were created by Irving S. Reed and Gustave Solomon in 1960 and have become very 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 detect 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, which are called burst errors. 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 developed in 1960 by Irving S. Reed and Gustave Solomon. These codes help fix mistakes in data, making sure information stays accurate 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 protect important data during its journey.
Applications
Reed–Solomon coding is very widely used in mass storage systems to correct errors caused by scratches or defects on media. It is a key part of the compact disc and is also used in DAT and DVD. This helps ensure that 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 allows bar codes to still be read even if part of them is damaged or obscured. 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 first 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 treat a codeword as a sequence of values from a polynomial. Both the encoder and decoder use the same set of fixed values. The decoder works to recover the original polynomial from the received message.
A theoretical method to correct errors involves finding the most likely polynomial that matches the received values. However, this method is often too slow because it requires checking many possibilities.
Later developments created more practical decoders. One example from 1986 uses a method that works with manageable complexity. More recent improvements continue to enhance how errors are corrected efficiently in 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.