Berlekamp-Welch algorithm

The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. The algorithm efficiently corrects errors in BCH codes and Reed–Solomon codes (which are a subset of BCH codes). Unlike many other decoding algorithms, and in correspondence with the code-domain Berlekamp–Massey algorithm that uses syndrome decoding and the dual of the codes, the Berlekamp–Welch decoding algorithm provides a method for decoding Reed–Solomon codes using just the generator matrix and not syndromes.

In the problem of decoding Reed–Solomon codes, the inputs are pair wise distinct evaluation points ${\displaystyle \alpha _{1},\cdots ,\alpha _{n}}$ where ${\displaystyle \alpha _{i}\in \mathbb {F} }$ with dimension ${\displaystyle k}$ and distance ${\displaystyle d=n-k+1}$ and a codeword ${\displaystyle y=(y_{1},\cdots ,y_{n})\in \mathbb {F} ^{n}.}$ Our goal is to describe an algorithm that can correct ${\displaystyle e<{\tfrac {1}{2}}(n-k+1)}$ many errors in polynomial time. To do so we have to find ${\displaystyle P\in \mathbb {F} [X]}$ such that ${\displaystyle \deg(P)<k-1}$ and the number of indices for which ${\displaystyle P(\alpha _{i})\neq y_{i}}$ is less than or equal to ${\displaystyle e.}$ We can assume that there exists a polynomial ${\displaystyle P}$ such that

...
Wikipedia