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

An efficient decoding algorithm for algebraic-geometric codes is prese nted. For codes from a large class of irreducible plane curves, includ ing 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 spe cially arranged syndrome matrix, followed by a novel majority voting s cheme. A fast implementation incorporating block Hankel matrix techniq ues is obtained whose worst-case running time is O(mn2), where m is th e degree of the curve. Applications of our techniques to decoding othe r algebraic-geometric codes, to decoding BCH codes to actual minimum d istance, and to two-dimensional shift register synthesis are also pres ented.