Also known as: Reed–Solomon code, Reed-Solomon, RS code
Reed–Solomon (RS) is a block error-correction code that works on multi-bit symbols rather than individual bits, which makes it especially good at correcting bursts of errors — a run of adjacent bad bits usually damages only a symbol or two.1 An RS code is written (n, k) over the Galois field GF(2^m): it takes k data symbols, appends n−k parity symbols, and can correct up to t = (n−k)/2 symbol errors anywhere in the codeword.
How it works
Reed–Solomon treats each block of m bits as one element of the finite field GF(2^m) and a codeword as a polynomial over that field. The parity symbols are chosen so that a valid codeword is divisible by a generator polynomial whose roots are consecutive powers of a primitive element; that structure lets the decoder detect and locate errors purely algebraically. Classic hard-decision decoding runs in three stages, each of which has its own page:
- Syndromes → error locator. The decoder evaluates the received polynomial at the code’s roots to get syndromes, then solves for the error-locator polynomial using the Berlekamp–Massey algorithm (or the equivalent Euclidean method).
- Find the error positions. Chien search evaluates the locator polynomial at every field element; its roots point to which symbols are wrong.
- Find the error values. Forney’s algorithm then computes the magnitude to XOR into each located symbol, completing the correction.
Because the whole pipeline is symbol-oriented, a burst that corrupts many consecutive bits still counts as only a handful of symbol errors — the source of RS’s famous burst resilience.
In practice
RS is almost always paired with interleaving: the encoder spreads the symbols of each codeword across time (or across a data frame) so that a long fade or dropout damages only a few symbols in any single codeword instead of wiping one out entirely. Concatenating an inner convolutional/Viterbi stage with an outer RS code — the scheme used by CDs, DVB, and deep-space links — is a classic way to clean up the residual burst errors the inner decoder leaves behind. Reed–Solomon is also the mathematical cousin of the BCH codes; both are built on the same Galois-field machinery, and RS is essentially a non-binary BCH code.
Relevance to SDR
Reed–Solomon protects signalling and data fields in P25 and DMR, and it is ubiquitous in storage (CDs, DVDs, QR codes) and broadcast (DVB, ATSC). In the scanner path, RS decoding helps GopherTrunk recover trunking control messages and data payloads on marginal signals where several symbols per block arrive corrupted.
Sources
-
Reed–Solomon error correction — Wikipedia, for the symbol-oriented block code, Galois-field construction, and burst-error correction. See also BCH code for the shared algebraic decoding theory. ↩