Decoding of reed‐solomon codes beyond the bch bound using euclidean algorithm
Toshio Horiguchi · Electronics and Communications in Japan (Part III Fundamental Electronic Science) · 1996
Abstract 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 ≥ 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 errros, which exceeds the BCH bound, by estimating the undetermined polynomials. the proposed algorithm requires O(2v ‐ 1n2vlog 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(n2v + 1log2 n) operations. Also, it is shown that the proposed decoding algorithm can be applied to continued fraction decoders.