Reed–Solomon Codes
摘要
Reed-Solomon (RS) codes are introduced as resulting from an interpolation with a degree-limited polynomial. This is shown to be equivalent to using an IDFT, where the redundancy is given as cyclically consecutive zeros. After having defined generator and parity-check polynomials, the major encoding and decoding algorithms are described in detail, where also the decoding is first explained by Prony’s curve fitting. The more standard description follows with defining the error-locator and errore valuator polynomials, the key equation, the Berlekamp-Massey and Euclidean algorithms. The Berlekamp-Massey algorithm is explained using Massey’s shift-register synthesis and alternatively the author’s matrix approach, which is analogous to the typical solution of Toeplitz systems in linear prediction commonly applying the Levinson-Durbin algorithm. How errors and erasures are jointly corrected, is also shown inside the Berlekamp-Massey algorithm or as a separate step.