ReedSolomon

Reed-Solomon codes are a family of error-correcting codes that operate over finite fields. They were introduced by Irving Reed and Gustave Solomon in 1960. RS codes are maximum distance separable (MDS) codes, with minimum distance d = n − k + 1, allowing correction of up to t = floor((n − k)/2) symbol errors in a codeword of length n over GF(2^m). The code length is at most q − 1 where q = 2^m.

An RS code RS(n, k) uses a finite field GF(2^m). The code is defined by a generator polynomial g(x) with roots at consecutive powers of a primitive element. Encoding maps a message of k symbols to a polynomial m(x) of degree < k, then forms the codeword c(x) = m(x) * x^{n−k} mod g(x) or, equivalently, by evaluating m at n distinct field elements.

Decoding: given a received word r, syndromes are computed to detect errors. If the number of errors is within the correcting capability, the key equations are solved to obtain the error locator polynomial and the error evaluator. The error positions and magnitudes are then determined (often using Forney’s formula) to correct r. Common decoding methods include Berlekamp–Massey–type decoders and related algorithmic variants; list-decoding approaches extend performance beyond the traditional bound.

Common parameter example: RS(255, 223) over GF(256) with 32 parity symbols, capable of correcting up to 16 symbol errors per codeword. This configuration is widely used in storage and communication systems.

Applications: Reed-Solomon codes are used in CDs, DVDs, Blu-ray discs, QR codes, and various data transmission and storage systems due to strong burst-error correction and practical hardware implementations.