TY - JOUR

T1 - Simultaneous partial inverses and decoding interleaved reed-solomon codes

AU - Yu, Jiun-Hung

AU - Loeliger, Hans Andrea

PY - 2018/12/1

Y1 - 2018/12/1

N2 - This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed-Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp-Massey type. Fourth, decoding interleaved Reed-Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: If that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp-Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt-Sidorenko-Bossert bound and the Roth-Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms.

AB - This paper introduces the simultaneous partial-inverse problem (SPI) for polynomials and develops its application to decoding interleaved Reed-Solomon codes beyond half the minimum distance. While closely related both to standard key equations and to well-known Padé approximation problems, the SPI problem stands out in several respects. First, the SPI problem has a unique solution (up to a scale factor), which satisfies a natural degree bound. Second, the SPI problem can be transformed (monomialized) into an equivalent SPI problem where all moduli are monomials. Third, the SPI problem can be solved by an efficient algorithm of the Berlekamp-Massey type. Fourth, decoding interleaved Reed-Solomon codes (or subfield-evaluation codes) beyond half the minimum distance can be analyzed in terms of a partial-inverse condition for the error pattern: If that condition is satisfied, then the (true) error locator polynomial is the unique solution of a standard key equation and can be computed in many different ways, including the well-known multi-sequence Berlekamp-Massey algorithm and the SPI algorithm of this paper. Two of the best performance bounds from the literature (the Schmidt-Sidorenko-Bossert bound and the Roth-Vontobel bound) are generalized to hold for the partial-inverse condition and thus to apply to several different decoding algorithms.

KW - Euclidean algorithm

KW - Interleaved Reed-Solomon codes

KW - multi-sequence Berlekamp-Massey algorithm

KW - performance bounds

KW - simultanenous partial-inverse problem

KW - subfield-evaluation codes

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

U2 - 10.1109/TIT.2018.2868701

DO - 10.1109/TIT.2018.2868701

M3 - Article

AN - SCOPUS:85052849875

VL - 64

SP - 7511

EP - 7528

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 12

M1 - 8454805

ER -