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

For a class of algebraic-geometric codes, a type of recurring relation is introduced on the syndrome sequence of an error vector. Then, a new majority yoting scheme is developed. By applying the generalized Berlekamp-Massey algorithm, and incorporating the majority voting scheme, an efficient decoding algorithm up to half the Feng-Rao bound is developed for a class of algebraic-geometric codes, the complexity of which is O （ γo1n2）, where n is the code length, and γ is the genus of curve. On different algebraic curves, the complexity of the algorithm can be lowered by choosing base functions suitably. For example, on Hermitian curves the complexity is O(n7/3.

For a class of algebraic-geometric codes, a type of recurring relation is introduced on the syndrome sequence of an error vector. Then, a new majority voting scheme is developed. By applying the generalized Berlekamp-Massey algorithm, and incorporating the majority voting scheme, an efficient decoding algorithm up to half the Feng-Rao bound is developed for a class of algebraic-geometric codes, the complexity of which is O(γο1n2), where n is the code length, and γ is the genus of curve. On different algebraic curves, the complexity of the algorithm can be lowered by choosing base functions suitably. For example, on Hermitian curves the complexity is O( n7/3 ).