SIMPLIFIED UNDERSTANDING AND EFFICIENT DECODING OF A CLASS OF ALGEBRAIC-GEOMETRIC CODES

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(min) greater-than-or-equal-to 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(mn2), 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.