Simplified understanding and efficient decoding of a class of algebraic-geometric codes
Gui-Liang Feng, Victor K. Wei, T.R.N. Rao, Kenneth K. Tzeng · IEEE Transactions on Information Theory · 1994
An efficient decoding algorithm for algebraic-geometric codes is presented. For codes from a large class of irreducible plane curves, including Hermitian curves, it can correct up to [(d*-1)/2] errors, where d* is the designed minimum distance. With it we also obtain a proof of d/sub min//spl ges/d* without directly using the Riemann-Roch theorem. The algorithm consists of Gaussian elimination on a specially arranged syndrome matrix, followed by a novel majority voting scheme. A fast implementation incorporating block Hankel matrix techniques is obtained whose worst-case running time is O(mn/sup 2/), where m is the degree of the curve. Applications of our techniques to decoding other algebraic-geometric codes, to decoding BCH codes to actual minimum distance, and to two-dimensional shift register synthesis are also presented.>