Fast algorithm for computing the roots of error locator polynomials up to degree II in Reed-Solomon decoders

The central problem in the implementation of a Reed-Solomon code is finding the roots of the error locator polynomial. In 1967, Berlekamp et al, found an algorithm for finding the roots of an affine polynomial in GF(2(m)) that can be used to solve this problem, In this paper, it is shown that this Berlekamp-Rumsey-Solomon algorithm, together with the Chien-search method, makes possible a fast decoding algorithm in the standard-basis representation that is naturally suitable in a software implementation. Finally, simulation results for this fast algorithm are given.