Berlekamp–Massey algorithm

<h2 id="description-of-algorithm">Description of algorithm</h2>
The Berlekamp–Massey algorithm is an alternative to the <a href="/facts/Reed%25E2%2580%2593Solomon_error_correction/HPc3Qj6N">Reed–Solomon Peterson decoder</a> for solving the set of linear equations. It can be summarized as finding the coefficients Λj of a polynomial Λ(x) so that for all positions i in an input stream S:

S
          
            i
            +
            ν
          
        
        +
        
          Λ
          
            1
          
        
        
          S
          
            i
            +
            ν
            −
            1
          
        
        +
        ⋯
        +
        
          Λ
          
            ν
            −
            1
          
        
        
          S
          
            i
            +
            1
          
        
        +
        
          Λ
          
            ν
          
        
        
          S
          
            i
          
        
        =
        0.
      
    
    {\displaystyle S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.}

In the code examples below, C(x) is a potential instance of Λ(x). The error locator polynomial C(x) for L errors is defined as:

C
        (
        x
        )
        =
        
          C
          
            L
          
        
        
          x
          
            L
          
        
        +
        
          C
          
            L
            −
            1
          
        
        
          x
          
            L
            −
            1
          
        
        +
        ⋯
        +
        
          C
          
            2
          
        
        
          x
          
            2
          
        
        +
        
          C
          
            1
          
        
        x
        +
        1
      
    
    {\displaystyle C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1}

or reversed:

C
        (
        x
        )
        =
        1
        +
        
          C
          
            1
          
        
        x
        +
        
          C
          
            2
          
        
        
          x
          
            2
          
        
        +
        ⋯
        +
        
          C
          
            L
            −
            1
          
        
        
          x
          
            L
            −
            1
          
        
        +
        
          C
          
            L
          
        
        
          x
          
            L
          
        
        .
      
    
    {\displaystyle C(x)=1+C_{1}x+C_{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.}

The goal of the algorithm is to determine the minimal degree L and C(x) which results in all <a href="/facts/Decoding_methods/A0x9Dpgq">syndromes</a>

S
          
            n
          
        
        +
        
          C
          
            1
          
        
        
          S
          
            n
            −
            1
          
        
        +
        ⋯
        +
        
          C
          
            L
          
        
        
          S
          
            n
            −
            L
          
        
      
    
    {\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}}

being equal to 0:

S
          
            n
          
        
        +
        
          C
          
            1
          
        
        
          S
          
            n
            −
            1
          
        
        +
        ⋯
        +
        
          C
          
            L
          
        
        
          S
          
            n
            −
            L
          
        
        =
        0
        ,
        
        L
        ≤
        n
        ≤
        N
        −
        1.
      
    
    {\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.}

Algorithm:
C(x) is initialized to 1, L is the current number of assumed errors, and initialized to zero. N is the total number of syndromes. n is used as the main iterator and to index the syndromes from 0 to N−1. B(x) is a copy of the last C(x) since L was updated and initialized to 1. b is a copy of the last discrepancy d (explained below) since L was updated and initialized to 1. m is the number of iterations since L, B(x), and b were updated and initialized to 1.
Each iteration of the algorithm calculates a discrepancy d. At iteration k this would be:

d
        ←
        
          S
          
            k
          
        
        +
        
          C
          
            1
          
        
        
          S
          
            k
            −
            1
          
        
        +
        ⋯
        +
        
          C
          
            L
          
        
        
          S
          
            k
            −
            L
          
        
        .
      
    
    {\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}

If d is zero, the algorithm assumes that C(x) and L are correct for the moment, increments m, and continues.
If d is not zero, the algorithm adjusts C(x) so that a recalculation of d would be zero:

C
        (
        x
        )
        ←
        C
        (
        x
        )
        −
        (
        d
        
          /
        
        b
        )
        
          x
          
            m
          
        
        B
        (
        x
        )
        .
      
    
    {\displaystyle C(x)\gets C(x)-(d/b)x^{m}B(x).}

The xm term shifts B(x) so it follows the syndromes corresponding to b. If the previous update of L occurred on iteration j, then m = k − j, and a recalculated discrepancy would be:

d
        ←
        
          S
          
            k
          
        
        +
        
          C
          
            1
          
        
        
          S
          
            k
            −
            1
          
        
        +
        ⋯
        −
        (
        d
        
          /
        
        b
        )
        (
        
          S
          
            j
          
        
        +
        
          B
          
            1
          
        
        
          S
          
            j
            −
            1
          
        
        +
        ⋯
        )
        .
      
    
    {\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}S_{j-1}+\cdots ).}

This would change a recalculated discrepancy to:

d
        =
        d
        −
        (
        d
        
          /
        
        b
        )
        b
        =
        d
        −
        d
        =
        0.
      
    
    {\displaystyle d=d-(d/b)b=d-d=0.}

The algorithm also needs to increase L (number of errors) as needed. If L equals the actual number of errors, then during the iteration process, the discrepancies will become zero before n becomes greater than or equal to 2L. Otherwise L is updated and the algorithm will update B(x), b, increase L, and reset m = 1. The formula L = (n + 1 − L) limits L to the number of available syndromes used to calculate discrepancies, and also handles the case where L increases by more than 1.

<h2 id="pseudocode">Pseudocode</h2>
The algorithm from Massey (1969, p. 124) for an arbitrary field:

polynomial(field K) s(x) = ... /* coeffs are sj; output sequence as N-1 degree polynomial) */
 /* connection polynomial */
 polynomial(field K) C(x) = 1; /* coeffs are cj */
 polynomial(field K) B(x) = 1;
 int L = 0;
 int m = 1;
 field K b = 1;
 int n;
 /* steps 2. and 6. */
 for (n = 0; n < N; n++) {
 /* step 2. calculate discrepancy */
 field K d = sn + ∑Li=1 ci sn - i 
 
 if (d == 0) {
 /* step 3. discrepancy is zero; annihilation continues */
 m = m + 1;
 } else if (2 * L <= n) {
 /* step 5. */
 /* temporary copy of C(x) */
 polynomial(field K) T(x) = C(x);
 
 C(x) = C(x) - d b−1 xm B(x);
 L = n + 1 - L;
 B(x) = T(x);
 b = d;
 m = 1;
 } else {
 /* step 4. */
 C(x) = C(x) - d b−1 xm B(x);
 m = m + 1;
 }
 }
 return L;

In the case of binary GF(2) BCH code, the discrepancy d will be zero on all odd steps, so a check can be added to avoid calculating it.

 /* ... */
 for (n = 0; n < N; n++) {
 /* if odd step number, discrepancy == 0, no need to calculate it */
 if ((n&1) != 0) {
 m = m + 1;
 continue;
 }
 /* ... */

<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>
<li><a href="/facts/Reeds%25E2%2580%2593Sloane_algorithm/xuAu6JHP">Reeds–Sloane algorithm</a>, an extension for sequences over integers mod n</li>
<li><a href="/facts/Nonlinear-feedback_shift_register/spWLt8bb">Nonlinear-feedback shift register</a> (NLFSR)</li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://www.encyclopediaofmath.org/index.php?title=Berlekamp-Massey_algorithm">"Berlekamp-Massey algorithm"</a>, <a href="/facts/Encyclopedia_of_Mathematics/WC6mGtPm">Encyclopedia of Mathematics</a>, <a href="/facts/European_Mathematical_Society/B3h7b672">EMS Press</a>, 2001 [1994]</li>
<li><a href="https://planetmath.org/BerlekampMasseyAlgorithm">Berlekamp–Massey algorithm</a> at <a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a>.</li>
<li><a href="/facts/Eric_W._Weisstein/FbMuVDep">Weisstein, Eric W.</a> <a href="https://mathworld.wolfram.com/Berlekamp-MasseyAlgorithm.html">"Berlekamp–Massey Algorithm"</a>. <a href="/facts/MathWorld/yc1jodbq">MathWorld</a>.</li>
<li><a href="https://code.google.com/p/lfsr/">GF(2) implementation in Mathematica</a></li>
<li>(in German) <a href="http://www.informationsuebertragung.ch/indexAlgorithmen.html">Applet Berlekamp–Massey algorithm</a></li>
<li><a href="https://berlekamp-massey-algorithm.appspot.com/">Online GF(2) Berlekamp-Massey calculator</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Reeds & Sloane 1985, p. 2 - Reeds, J. A.; Sloane, N. J. A. (1985), "Shift-Register Synthesis (Modulo n)" (PDF), SIAM Journal on Computing, 14 (3): 505–513, CiteSeerX 10.1.1.48.4652, doi:10.1137/0214038 <a href="http://neilsloane.com/doc/Me111.pdf" target="_blank">http://neilsloane.com/doc/Me111.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Reeds, J. A.; Sloane, N. J. A. (1985), "Shift-Register Synthesis (Modulo n)" (PDF), SIAM Journal on Computing, 14 (3): 505–513, CiteSeerX 10.1.1.48.4652, doi:10.1137/0214038 <a href="/wiki/N._J._A._Sloane" target="_blank">/wiki/N._J._A._Sloane</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Berlekamp, Elwyn R. (1967), Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy{{citation}}: CS1 maint: location missing publisher (link) <a href="/wiki/Elwyn_Berlekamp" target="_blank">/wiki/Elwyn_Berlekamp</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Berlekamp, Elwyn R. (1984) [1968], Algebraic Coding Theory (Revised ed.), Laguna Hills, CA: Aegean Park Press, ISBN 978-0-89412-063-3. Previous publisher McGraw-Hill, New York, NY. <a href="978-0-89412-063-3" target="_blank">978-0-89412-063-3</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Massey, J. L. (January 1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127, doi:10.1109/TIT.1969.1054260, S2CID 9003708 <a href="/wiki/James_Massey" target="_blank">/wiki/James_Massey</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ben Atti, Nadia; Diaz-Toca, Gema M.; Lombardi, Henri (April 2006), "The Berlekamp–Massey Algorithm revisited", Applicable Algebra in Engineering, Communication and Computing, 17 (1): 75–82, arXiv:2211.11721, CiteSeerX 10.1.1.96.2743, doi:10.1007/s00200-005-0190-z, S2CID 14944277 <a href="http://hlombardi.free.fr/publis/ABMAvar.html" target="_blank">http://hlombardi.free.fr/publis/ABMAvar.html</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Massey 1969, p. 124 - Massey, J. L. (January 1969), "Shift-register synthesis and BCH decoding" (PDF), IEEE Transactions on Information Theory, IT-15 (1): 122–127, doi:10.1109/TIT.1969.1054260, S2CID 9003708 <a href="http://crypto.stanford.edu/~mironov/cs359/massey.pdf" target="_blank">http://crypto.stanford.edu/~mironov/cs359/massey.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Berlekamp–Massey algorithm open-in-new

Berlekamp–Massey algorithm