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

概要

論文の詳細を見る
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+e^2-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.
社団法人電子情報通信学会の論文
1999-10-25