Two new decoding algorithms for Reed-Solomon codes (Q1311609)

Two new decoding algorithms for Reed-Solomon codes are presented, based on the Berlekamp-Welch algorithm. The first one uses the extended Euclidean algorithm and is very efficient for VLSI implementation. The second one is similar to the classical Peterson algorithm but works with remainders rather than with syndromes. The complexity of the algorithms are comparable to the classical ones and as such they may be a viable alternative for decoding Reed-Solomon codes. Pascal-like descriptions are given, and comparisons with different methods are made. Error-and-erasure decoding is not included.