Berlekamp-Welch algorithm

The Berlekamp-Welch algorithm, also called the Welch-Berlekamp algorithm, is a decoding procedure for Reed-Solomon error-correcting codes. It is named for Elwyn R. Berlekamp and Lloyd R. Welch. In the original view of a Reed-Solomon code, a message of k symbols supplies the coefficients of a polynomial, or the polynomial is built from the message by Lagrange interpolation, and that polynomial is then evaluated at n known inputs to produce a codeword. The decoder receives a version of the codeword that may contain errors and must recover the original polynomial from the known inputs and the received values. The algorithm does this efficiently and, along the way, also computes an error polynomial that equals zero at the positions where the received codeword was corrupted, which locates the errors as well as correcting them.