# Lecture 20: Reed-Solomon Codes Source: https://www.youtube.com/watch?v=OapnQzIDBM0 Recap page: https://rapidrecap.app/video/OapnQzIDBM0 Generated: 2025-12-17T16:37:07.878+00:00 --- ## 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) = r_i * 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. ## Detailed Analysis The lecture outlines the history of error-correcting codes, noting that Reed-Solomon codes (1960) only became practical after the Berlekamp-Massey decoding algorithm (1969) and concatenated codes (1966) were developed, allowing their deployment on the Voyager spacecraft. Reed-Solomon codes construct a code word by evaluating a message polynomial p(x) of degree k-1 at n distinct points (0 through n-1) over a finite field, yielding n code word entries. The minimum Hamming weight is n-k+1, which dictates that e errors can be corrected if n-k >= 2e. Decoding relies on a theorem stating that received word r and the unknown error-location polynomial f(x) relate to the message polynomial p(x) via q(x) = p(x)f(x), where q(x) = r(x)f(x) at all points. This relationship leads to a system of linear equations in the coefficients of f(x) and q(x); specifically, with n-k=2e, there are k+2e linearly independent equations for k+2e+1 variables, yielding a unique solution for f(x) and q(x) (assuming f_e=1), allowing recovery of the message via p(x) = q(x)/f(x). Furthermore, the lecture explains that concatenated codes, combining an outer Reed-Solomon code with an inner code, dramatically improved performance, enabling robust communication even at 10% bit error rates, although the resulting overhead (multiplying bits by about 4) was still higher than the ideal Shannon bound (multiplying bits by 2). ### Historical Timeline - Shannon discovered noisy coding theorem (1948) - Hamming codes (1950) - Reed-Solomon codes (1960) - Concatenated codes (1966) - Berlekamp-Massey decoding (1969) - Voyager used RS codes (1977) - Turbo/LDPC codes took over mid-1990s. ### Reed-Solomon Encoding - Message m0 through mk-1 forms polynomial p(x) = m0 + m1*x + ... + mk-1*x^(k-1) - Codeword is p(0), p(1), ..., p(n-1) over a finite field (e.g., Z_p or GF(2^k)). ### Error Correction Capability - Minimum weight is n-k+1 - Corrects e errors if minimum distance (n-k+1) >= 2e+1, meaning n-k >= 2e. ### Decoding Theorem Basis - If l <= e errors occur at positions i1 through il, there exist polynomials f(x) (degree <= e) and q(x) (degree <= k+e-1) such that q(i) = r_i * f(i) for all received points i. ### Decoding via Linear Algebra - The relationship q(i) = r_i * f(i) yields k+2e linearly independent equations in the coefficients of q(x) and f(x) when n-k=2e - Solving these equations determines f(x) and q(x) - The message polynomial is recovered as p(x) = q(x) / f(x). ### Practicality with Concatenated Codes - An example uses an outer RS code (256 bytes in, 150 encoded, e=53 errors correctable) combined with an inner (19, 8, 7) code (corrects 3 byte errors) - This combination achieves a probability of decoding success close to 1 (10^-60 chance of failure) at 10% bit error rate. ### Inner Code Decoding - For the inner code, table lookup across all 2^19 possibilities is possible for modern systems, though Voyager likely used cleverer methods like Hamming codes or smaller block sizes due to memory constraints.