Systolic Implementations of Modified Gaussian Eliminations for the Decoding of Reed-Solomon Codes

Chih-Wei LIU, Li-Lien LIN

Summary :

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 Axb , 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+e²-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.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E82-A No.10 pp.2251-2258
• Publication Date: 1999/10/25
• Type of Manuscript: PAPER
• Category: Information Theory and Coding Theory

Authors

Chih-Wei LIU
Li-Lien LIN

Keyword

systolic array,  Gaussian elimination,  RS code,  Hong-Vetterli algorithm,  FIA,  Berlekamp-Massey algorithm