TY - JOUR

T1 - Partial inverses mod m(x) and reverse berlekamp-massey decoding

AU - Yu, Jiun-Hung

AU - Loeliger, Hans Andrea

PY - 2016/12/1

Y1 - 2016/12/1

N2 - This semi-tutorial paper introduces the partial-inverse problem for polynomials and develops its application to decoding Reed-Solomon codes and some related codes. The most natural algorithm to solve the partial-inverse problem is very similar to, but more general than, the Berlekamp-Massey algorithm. Two additional algorithms are obtained as easy variations of the basic algorithm: the first variation is entirely new, while the second variation may be viewed as a version of the Euclidean algorithm. Decoding Reed-Solomon codes (and some related codes) can be reduced to the partial-inverse problem, both via the standard key equation and, more naturally, via an alternative key equation with a new converse. Shortened and singly-extended Reed-Solomon codes are automatically included. Using the properties of the partial-inverse problem, two further key equations with attractive properties are obtained. The paper also points out a variety of options for interpolation.

AB - This semi-tutorial paper introduces the partial-inverse problem for polynomials and develops its application to decoding Reed-Solomon codes and some related codes. The most natural algorithm to solve the partial-inverse problem is very similar to, but more general than, the Berlekamp-Massey algorithm. Two additional algorithms are obtained as easy variations of the basic algorithm: the first variation is entirely new, while the second variation may be viewed as a version of the Euclidean algorithm. Decoding Reed-Solomon codes (and some related codes) can be reduced to the partial-inverse problem, both via the standard key equation and, more naturally, via an alternative key equation with a new converse. Shortened and singly-extended Reed-Solomon codes are automatically included. Using the properties of the partial-inverse problem, two further key equations with attractive properties are obtained. The paper also points out a variety of options for interpolation.

KW - Berlekamp-Massey algorithm

KW - Euclidean algorithm

KW - Reed-Solomon codes

KW - key equation

KW - partial-inverse algorithm

KW - partial-inverse problem

KW - polynomial remainder codes

UR - http://www.scopus.com/inward/record.url?scp=85000642879&partnerID=8YFLogxK

U2 - 10.1109/TIT.2016.2613559

DO - 10.1109/TIT.2016.2613559

M3 - Article

AN - SCOPUS:85000642879

VL - 62

SP - 6737

EP - 6756

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 12

M1 - 7576713

ER -