Systolic implementations of modified Gaussian eliminations for the decoding of Reed-Solomon codes

Chih-Wei Liu*, Li Lien Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Systolic array implementations of modified Gaussian eliminations for the decoding of an (n, n - 2t) RS code, including the Hong-Vetterli algorithm and the FIA proposed by Feng and Tzeng, are designed in this paper. These modified Gaussian eliminations are more easily understanding than the classical Berlekamp-Massey algorithm and, in addition, are efficient to decode RS codes for small e or e ≪ t, where e is the number of errors actually occurred. These architectures can also be applied to solving a linear system Ax = b, where A has an arbitrary rank e and e ≤ t. For hardware reduction and saving complexity or power, a fast version of the FIA, or an early stopped Berlekamp-Massey (ESBM) algorithm, has been re-developed by Liu and Lu recently. The ESBM algorithm can be directly implemented by the proposed architecture of the FIA with some modifications. The computation complexity of the ESBM algorithm is upper bounded by te+e2 - 1 for any e ≤ t. With the fast algorithm, it preserves not only the fastest processing time but also the smallest computation complexity and, if e ≪ t, it will save about half of the computation efforts and processing time of the conventional Berlekamp-Massey algorithm.

Original languageEnglish
Pages (from-to)2251-2258
Number of pages8
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
VolumeE82-A
Issue number10
StatePublished - 1 Jan 1999

Keywords

  • Berlekamp-Massey algorithm
  • FIA
  • Gaussian elimination
  • Hong-Vetterli algorithm
  • RS code
  • Systolic array

Fingerprint Dive into the research topics of 'Systolic implementations of modified Gaussian eliminations for the decoding of Reed-Solomon codes'. Together they form a unique fingerprint.

Cite this