A fast parallel decoding algorithm for ge with a systolic array arc
Masazumi Kurihara, Shojiro Sakata · 1994
In this paper we propose a fast paral- lel decoding algorithm for general one-point algebraic geometric(1-pt AG) codes with a systolic array archi- tecture(SAA). This algorithm is able to correct up to half the Feng-Rao bound and the time complexity is O(n) by using a series of O(n) processors where n is the code length and each processor is composed of r cells for the smallest non-zero and non-gap value r. Our decoding algorithm is a parallel version of the decod- ing algorithm given in (5), which is a special version of multi- dimensional Berlekamp-Massey(mu1ti-D BM) algorithm. This algorithm is implemented with a SAA. In (6), we recently pre- sented a parallel version of ID BM algorithm with a SAA which can be applied to decoding of Reed-Solomon codes and BCH codes. In this paper we present a scheme which is moti- vated by the systolic algorithm(6). To implement the parallel computation, we introduce a concept of a discrepancy poly- nomial having discrepancies as coefficients of its terms in the multi-D BM algorithm. Let X be a curve with genus g over a finite field F.