Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Berlekamp–Welch algorithm
open-in-new
<h2 id="the-key-equations">The key equations</h2> <p>Defining <i>e</i> = number of errors, the key set of <i>n</i> equations is </p> b i E ( a i ) = E ( a i ) F ( a i ) {\displaystyle b_{i}E(a_{i})=E(a_{i})F(a_{i})} <p>Where E(<i>ai</i>) = 0 for the <i>e</i> cases when bi ≠ F(ai), and E(ai) ≠ 0 for the <i>n</i> - <i>e</i> non error cases where <i>bi</i> = F(<i>ai</i>) . These equations can't be solved directly, but by defining Q() as the product of E() and F(): </p> Q ( a i ) = E ( a i ) F ( a i ) {\displaystyle Q(a_{i})=E(a_{i})F(a_{i})} <p>and adding the constraint that the most significant coefficient of E(ai) = <i>ee</i> = 1, the result will lead to a set of equations that can be solved with linear algebra. </p> b i E ( a i ) = Q ( a i ) {\displaystyle b_{i}E(a_{i})=Q(a_{i})} b i E ( a i ) − Q ( a i ) = 0 {\displaystyle b_{i}E(a_{i})-Q(a_{i})=0} b i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e e a i e ) − ( q 0 + q 1 a i + q 2 a i 2 + ⋯ + q q a i q ) = 0 {\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e}a_{i}^{e})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=0} <p>where <i>q</i> = <i>n</i> - <i>e</i> - 1. Since <i>ee</i> is constrained to be 1, the equations become: </p> b i ( e 0 + e 1 a i + e 2 a i 2 + ⋯ + e e − 1 a i e − 1 ) − ( q 0 + q 1 a i + q 2 a i 2 + ⋯ + q q a i q ) = − b i a i e {\displaystyle b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e-1}a_{i}^{e-1})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=-b_{i}a_{i}^{e}} <p>resulting in a set of equations which can be solved using linear algebra, with time complexity O ( n 3 ) {\displaystyle O(n^{3})} . </p><p>The algorithm begins assuming the maximum number of errors <i>e</i> = ⌊(<i>n</i>-<i>k</i>)/2⌋. If the equations can not be solved (due to redundancy), <i>e</i> is reduced by 1 and the process repeated, until the equations can be solved or <i>e</i> is reduced to 0, indicating no errors. If Q()/E() has remainder = 0, then F() = Q()/E() and the code word values F(<i>ai</i>) are calculated for the locations where E(<i>ai</i>) = 0 to recover the original code word. If the remainder ≠ 0, then an uncorrectable error has been detected. </p> <h2 id="example">Example</h2> <p>Consider RS(7,3) (<i>n</i> = 7, <i>k</i> = 3) defined in <i>GF</i>(7) with <i>α</i> = 3 and input values: <i>ai</i> = i-1 : {0,1,2,3,4,5,6}. The message to be systematically encoded is {1,6,3}. Using Lagrange interpolation, <i>F(ai)</i> = 3 x2 + 2 x + 1, and applying <i>F(ai)</i> for <i>a4</i> = 3 to <i>a7</i> = 6, results in the code word {1,6,3,6,1,2,2}. Assume errors occur at <i>c2</i> and <i>c5</i> resulting in the received code word {1,5,3,6,3,2,2}. Start off with <i>e</i> = 2 and solve the linear equations: </p> [ b 1 b 1 a 1 − 1 − a 1 − a 1 2 − a 1 3 − a 1 4 b 2 b 2 a 2 − 1 − a 2 − a 2 2 − a 2 3 − a 2 4 b 3 b 3 a 3 − 1 − a 3 − a 3 2 − a 3 3 − a 3 4 b 4 b 4 a 4 − 1 − a 4 − a 4 2 − a 4 3 − a 4 4 b 5 b 5 a 5 − 1 − a 5 − a 5 2 − a 5 3 − a 5 4 b 6 b 6 a 6 − 1 − a 6 − a 6 2 − a 6 3 − a 6 4 b 7 b 7 a 7 − 1 − a 7 − a 7 2 − a 7 3 − a 7 4 ] [ e 0 e 1 q 0 q 1 q 2 q 3 q 4 ] = [ − b 1 a 1 2 − b 2 a 2 2 − b 3 a 3 2 − b 4 a 4 2 − b 5 a 5 2 − b 6 a 6 2 − b 7 a 7 2 ] {\displaystyle {\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}} [ 1 0 6 0 0 0 0 5 5 6 6 6 6 6 3 6 6 5 3 6 5 6 4 6 4 5 1 3 3 5 6 3 5 6 3 2 3 6 2 3 1 5 2 5 6 1 6 1 6 ] [ e 0 e 1 q 0 q 1 q 2 q 3 q 4 ] = [ 0 2 2 2 1 6 5 ] {\displaystyle {\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}} [ 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 ] [ e 0 e 1 q 0 q 1 q 2 q 3 q 4 ] = [ 4 2 4 3 3 1 3 ] {\displaystyle {\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}} <p>Starting from the bottom of the right matrix, and the constraint <i>e2</i> = 1: </p><p> Q ( a i ) = 3 x 4 + 1 x 3 + 3 x 2 + 3 x + 4 {\displaystyle Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4} </p><p> E ( a i ) = 1 x 2 + 2 x + 4 {\displaystyle E(a_{i})=1x^{2}+2x+4} </p><p> F ( a i ) = Q ( a i ) / E ( a i ) = 3 x 2 + 2 x + 1 {\displaystyle F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1} with remainder = 0. </p><p>E(<i>ai</i>) = 0 at <i>a2</i> = 1 and <i>a5</i> = 4 Calculate F(<i>a2</i> = 1) = 6 and F(<i>a5</i> = 4) = 1 to produce corrected code word {1,6,3,6,1,2,2}. </p> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed–Solomon error correction</a></li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="http://people.csail.mit.edu/madhu/FT02/">MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan</a></li> <li><a href="https://web.archive.org/web/20110606191907/http://www.cse.buffalo.edu/~atri/courses/coding-theory/fall07.html">University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra</a></li> <li>Algebraic Codes on Lines, Planes and Curves, An Engineering Approach – Richard E. Blahut</li> <li>Welch Berlekamp Decoding of Reed–Solomon Codes – L. R. Welch</li> <li><a href="https://worldwide.espacenet.com/textdoc?DB=EPODOC&IDX=US4,633,470">US 4,633,470</a>, <a href="/facts/Lloyd_R._Welch/IdP5tqxo">Welch, Lloyd R.</a> & <a href="/facts/Elwyn_Berlekamp/zUTTIlF6">Berlekamp, Elwyn R.</a>, "Error Correction for Algebraic Block Codes", published September 27, 1983, issued December 30, 1986 – The patent by Lloyd R. Welch and Elewyn R. Berlekamp</li></ul>