Lesson plan
Berlekamp–Welch algorithm
The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon codes for an RS(n, k), code based on the Reed Solomon original view where a message m_1, \cdots, m_k is used as coefficients of a polynomial F(a_i) or used with Lagrange interpolation to generate the polynomial F(a_i) of degree a_1 , \cdots, a_k and then F(a_i) is applied to a_{k+1}, \cdots , a_n to create an encoded codeword c_1, \cdots , c_n . The goal of the decoder is to recover the original encoding polynomial F(a_i) , using the known inputs a_1, \cdots , a_n and received codeword b_1, \cdots , b_n with possible errors. It also computes an error polynomial E(a_i) where E(a_i) = 0 corresponding to errors in the received codeword.
Article summary
The Berlekamp–Welch algorithm, also known as the Welch–Berlekamp algorithm, is named for Elwyn R. Berlekamp and Lloyd R. Welch. This is a decoder algorithm that efficiently corrects errors in Reed–Solomon codes for an RS(n, k), code based on the Reed Solomon original view where a message m_1, \cdots, m_k is used as coefficients of a polynomial F(a_i) or used with Lagrange interpolation to generate the polynomial F(a_i) of degree a_1 , \cdots, a_k and then F(a_i) is applied to a_{k+1}, \cdots , a_n to create an encoded codeword c_1, \cdots , c_n . The goal of the decoder is to recover the original encoding polynomial F(a_i) , using the known inputs a_1, \cdots , a_n and received codeword b_1, \cdots , b_n with possible errors. It also computes an error polynomial E(a_i) where E(a_i) = 0 corresponding to errors in the received codeword.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.