A fast parallel implementation of a Berlekamp-Massey algorithm for algebraic-geometric codes

摘要

We obtain a parallel Berlekamp-Massey-type algorithm for determining error locating functions for the class of one point algebraic-geometric codes. The proposed algorithm has a regular and simple structure and is suitable for VLSI implementation. We give an outline for an implementation, which uses as main blocks /spl gamma/ copies of a modified one-dimensional Berlekamp-Massey algorithm, where /spl gamma/ is the order of the first nongap in the function space associated with the code. Such a parallel implementation determines the error locator for an algebraic-geometric code using the same time requirements as the underlying one-dimensional Berlekamp-Massey algorithm applied to the decoding of Reed-Solomon codes.