A partial-inverse approach to decoding Reed-Solomon codes and polynomial remainder codes
Autori
Viac o knihe
The thesis develops a new approach to the central themes of algebraic coding theory. The focus here is the newly introduced concept of a partial-inverse polynomial in a quotient ring F[x]/m(x). In particular, the decoding of Reed-Solomon codes can be attributed to the computation of a partial-inverse polynomial. The problem of practical computation of a partial-inverse polynomial is closely related to the problem of shift-register synthesis, which is based on the well-known Berlekamp-Massey algorithm. A major result of this work is a (new) algorithm for computing a partial-inverse polynomial. The new algorithm is very similar to the Berlekamp-Massey algorithm, but it is applicable generally, e. g., to extended Reed-Solomon codes and polynomial remainder codes. The algorithm can also be easily transformed into the so-called Euclidean algorithm, and thus provides a new derivation of the later. For decoding Reed-Solomon codes, the algorithm can be directly applied to the classical key equation; however, mathematically natural is the application to a new key equation that applies in particular to generalizations of Reed-Solomon codes. Two new interpolation are also presented to accompany this new key equation. Another focus of this work is the polynomial remainder codes, a natural generalization of Reed-Solomon codes. The theory of such codes is carefully constructed as in earlier work. In particular, varying degrees of remainders are allowed, resulting in two different definitions of the distance between two codewords. The decoding of these codes leads directly to the mentioned new key equation. A focus of the recent algebraic coding theory is the decoding of errors beyond half the minimum distance. A mainline of such algorithms is based on generalization of the Berlekamp-Massey algorithm on several parallel sequences. In this work, a corresponding generalization of the decoding algorithm via some partial-inverse polynomials is also developed.