The Welch-Berlekamp and Berlekamp-Massey algorithms
Simon R. Blackburn⋆ · 2002
Classically, the decoding of a Reed-Solomon code is carried out by calculating power sum syndromes and then using the Berlekamp-Massey algorithm to solve the resulting linear recurrence problem. A new approach, taken by Welch and Berlekamp, is to convert the decoding problem into a rational interpolation problem which can then be solved by the Welch-Berlekamp algorithm. One of the advantages of this second approach is that the syndromes do not have to be calculated, thus saving decoder computations. We show that the problems solved by the Berlekamp-Massey and Welch-Berlekamp algorithms are special instances of a more general problem which has been studied (in the characteristic zero case) by control theorists. We present an algorithm to solve this general problem which can be used to find the solutions to both the classical key equation and the Welch-Berlekamp interpolation problem.