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

Jiun-Hung Yu*, Hans Andrea Loeliger

*Corresponding author for this work

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

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.

Original languageEnglish
Article number7576713
Pages (from-to)6737-6756
Number of pages20
JournalIEEE Transactions on Information Theory
Volume62
Issue number12
DOIs
StatePublished - 1 Dec 2016

Keywords

  • Berlekamp-Massey algorithm
  • Euclidean algorithm
  • Reed-Solomon codes
  • key equation
  • partial-inverse algorithm
  • partial-inverse problem
  • polynomial remainder codes

Fingerprint Dive into the research topics of 'Partial inverses mod m(x) and reverse berlekamp-massey decoding'. Together they form a unique fingerprint.

Cite this