Decoding of Reed-Solomon codes beyond the BCH bound using Euclidean algorithm

The output polynomials of Euclid's decoding method for t-error-correcting Reed-Solomon (RS) codes with design distances of d = 2t + 1 and d = 2t + 2 are analyzed when t + v (v greater than or equal to 1) errors occur. A method is proposed which expresses the error-locator polynomials for t + v errors in terms of output and undetermined polynomials, The error-locator polynomials are expressed for v = 1, 2 as specific examples that are important in applications. Furthermore, a decoding algorithm is proposed that corrects t + v errors, which exceeds the BCH bound, by estimating the undetermined polynomials. The proposed algorithm requires O(2(v-1)n(2v)log n) arithmetic operations for decoding t + v errors with a t-error-correcting RS codes with length n and a design distance of 2t + 1, whereas previous decoding methods that exceeded the BCH bound required O(n(2v+1)log(2) n) operations. Also, it is shown that the proposed decoding algorithm can be applied to continued fraction decoders.