Reed–Solomon error correction

A method for detecting and correcting symbol errors or erasures by encoding data as codewords over a finite field. Its redundancy lets a decoder reconstruct the original message from a bounded number of corrupted or missing symbols.

Finite field: A set with addition, subtraction, multiplication, and division by nonzero elements, all obeying field laws. Reed–Solomon symbols are field elements, so their arithmetic wraps around a finite set.
Error-correcting code: A code that adds structured redundancy so a message can be recovered after some data is altered or lost. Reed–Solomon correction is one specific form of error-correcting coding.
Compact Disc digital audio: The digital audio format used by Compact Disc, with layered coding and interleaving to withstand disc defects. Its CIRC system uses Reed–Solomon codes to recover audio despite scratches and dropouts.
BCH code: A family of cyclic error-correcting codes that can be designed to correct a specified number of bit errors. BCH codes often target bit errors, while Reed–Solomon codes correct errors in multi-bit symbols.
Reed–Solomon code: A nonbinary error-correcting code whose codewords are evaluations of low-degree polynomials over a finite field. This code construction supplies the redundancy that the correction method decodes.
Hamming distance: The number of positions at which two equal-length strings differ. The minimum distance between codewords determines how many symbol errors can be corrected.
QR code: A two-dimensional matrix barcode that stores data and error-correction information in black-and-white modules. Its Reed–Solomon redundancy allows data recovery when parts of the symbol are obscured.
Convolutional code: A code that encodes a data stream using finite-state operations on current and preceding input bits. It is suited to streaming channels, unlike block-oriented Reed–Solomon coding.
Polynomial interpolation: The reconstruction of a polynomial from values known at distinct input points. Decoding recovers a polynomial from surviving symbol values and their positions.
Minimum distance: The smallest distance between distinct codewords in a code. A Reed–Solomon code's distance sets its error-and-erasure correction bound.

Linked from 1 page