A type of recurring relation on sequences and efficient decoding of a class of algebraic-geometric codes (II) - An efficient decoding algorithm

For a class of algebraic-geometric codes, a type of recurring relation is i ntroduced on the syndrome sequence of an error vector. Then, a new majority voting scheme is developed. By applying the generalized Berlekamp-Massey a lgorithm, and incorporating the majority voting scheme, an efficient decodi ng algorithm up to half the Feng-Rao bound is developed for a class of alge braic-geometric codes, the complexity of which is O(gamma o(1)n(2)), where n is the code length, and gamma is the genus of curve. On different algebra ic curves, the complexity of the algorithm can be lowered by choosing base functions suitably. For example, on Hermitian curves the complexity is O(n( 7/3)).