Lecture 20: Reed-Solomon Codes

Quick Overview

Reed-Solomon codes, discovered in 1960, became practical with the Berlekamp-Massey decoding algorithm and concatenated codes, enabling their use in applications like the Voyager spacecraft, but they were eventually superseded by turbo codes, LDPC codes, and polar codes after newer techniques were developed to meet Shannon's bound.

Key Points: Reed-Solomon codes were discovered by Reed and Solomon in 1960, following Shannon's noisy coding theorem (1948) and Hamming codes (1950). The practical use of Reed-Solomon codes was enabled by the 1969 Berlekamp-Massey decoding algorithm and the discovery of concatenated codes in 1966. Reed-Solomon codes were utilized on the Voyager aircraft, which launched in 1977 and are still transmitting signals using these codes. The minimum Hamming weight of a Reed-Solomon code word is proven to be n minus k plus 1, allowing correction of e errors if n minus k is greater than or equal to 2e. Decoding is based on the theorem that for received word r and at most e errors, there exist non-zero polynomials f(x) (degree <= e) and q(x) (degree <= k+e-1) such that q(i) = ri f(i) for all i. The message polynomial p(x) is recovered by computing p(x) = q(x) / f(x) via linear algebra solving for the coefficients of f(x) and q(x). Concatenated codes, using an outer Reed-Solomon code and an inner code like a (19, 8, 7) code, made Reed-Solomon practical even with high bit error rates like 10%, achieving performance close to Shannon's bound, though newer codes eventually took over.

Context: The lecture provides a historical timeline and technical analysis of Reed-Solomon codes, starting with their discovery in 1960 and tracing their evolution alongside other major milestones in coding theory, such as Shannon's theorem and the development of decoding algorithms. The discussion emphasizes how Reed-Solomon codes, despite not initially meeting Shannon's bound, were critical for early deep space communication like the Voyager missions before being gradually replaced by newer, more efficient codes like turbo codes and LDPC codes starting in the mid-1990s.