Editing Berlekamp–Massey algorithm (section)

== Pseudocode ==

The algorithm from {{Harvtxt|Massey|1969|p=124}} for an arbitrary field:
<!-- Notes: notation changes from Massey:
Massey     Here
N          n       count 0 to n-1
x          m       count
D          x       formal variable
B(D)       B(x)    polynomial
C(D)       C(x)    polynomial
T(D)       T(x)    polynomial
-->
<div class="mw-highlight mw-highlight-lang-c mw-content-ltr">
    polynomial(field ''K'') s(x) = ... <span class="cm">/* coeffs are s<sub>j</sub>; output sequence as N-1 degree polynomial) */</span>
    <span class="cm">/* connection polynomial */</span>
    polynomial(field K) C(x) = 1;  <span class="cm">/* coeffs are c<sub>j</sub> */</span>
    polynomial(field K) B(x) = 1;
    int L = 0;
    int m = 1;
    field K b = 1;
    int n;
    <span class="cm">/* steps 2. and 6. */</span>
    <span class="k">for</span> (n = 0; n < N; n++) {
        <span class="cm">/* step 2. calculate discrepancy */</span>
        field K d = s<sub>n</sub> +  {{math|&sum;{{su|p=L|b=i=1}} c<sub>i</sub> s<sub>n - i</sub>}} <!--Σi=1Lci⋅sn−i;-->
    
        <span class="k">if</span> (d == 0) {
            <span class="cm">/* step 3. discrepancy is zero; annihilation continues */</span>
            m = m + 1;
        } <span class="k">else</span> <span class="k">if</span> (2 * L <= n) {
            <span class="cm">/* step 5. */</span>
            <span class="cm">/* temporary copy of C(x) */</span>
            polynomial(field K) T(x) = C(x);
    
            C(x) = C(x) - d b<sup>−1</sup> x<sup>m</sup> B(x);
            L = n + 1 - L;
            B(x) = T(x);
            b = d;
            m = 1;
        } <span class="k">else</span> {
            <span class="cm">/* step 4. */</span>
            C(x) = C(x) - d b<sup>−1</sup> x<sup>m</sup> B(x);
            m = m + 1;
        }
    }
    <span class="k">return</span> L;
</div>

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.
{{sxhl|2=c|1=<nowiki/>
    /* ... */
    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;
        }
    /* ... */
}}