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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reed–Solomon Codes

  • Werner Henkel

摘要

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.