Hartung-Gorre Verlag

Inh.: Dr. Renate Gorre

D-78465 Konstanz

Fon: +49 (0)7533 97227

Fax: +49 (0)7533 97228




Series in Signal and Information Processing, Vol. 26
edited by Hans-Andrea Loeliger

Jiun-Hung Yu

A Partial-Inverse Approach to Decoding

Reed-Solomon Codes and

Polynomial Remainder Codes

1. Auflage/1st edition 2015, XIV, 130 Seiten/pages, € 64,00.

ISBN 978-3-86628-527-9


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.


Keywords: Error-Correcting Codes, Reed-Solomon Codes, Algebraic Coding Theory, Polynomial Remainder Codes, Berlekamp-Massey Algorithm, Padé Approximation, Euclidean Algorithm, Partial-Inverse Problem, Simultaneous Partial-Inverse Problem.



Direkt bestellen bei / to order directly from: Hartung.Gorre@t-online.de

Series / Reihe "Series in Signal and Information Processing" im Hartung-Gorre Verlag

Hartung-Gorre Verlag / D-78465 Konstanz / Germany

Telefon: +49 (0) 7533 97227  Telefax: +49 (0) 7533 97228
http://www.hartung-gorre.de   eMail: verlag@hartung-gorre.de