Berlekamp–Massey algorithm

Not to be confused with Berlekamp's algorithm.

The Berlekamp–Massey algorithm is an algorithm that will find the shortest linear feedback shift register (LFSR) for a given binary output sequence. The algorithm will also find the minimal polynomial of a linearly recurrent sequence in a (restricted) field (mathematics).

Elwyn Berlekamp invented an algorithm for decoding Bose–Chaudhuri–Hocquenghem (BCH) codes. James Massey recognized its application to linear feedback shift registers and simplified the algorithm. Massey termed the algorithm the LFSR Synthesis Algorithm (Berlekamp Iterative Algorithm) (Massey 1969, p. 124), but it is now known as the Berlekamp–Massey algorithm. The algorithm became the key to practical application of the now ubiquitous Reed–Solomon code.

The algorithm for the binary field

The following is the Berlekamp–Massey algorithm specialized for the typical binary finite field F₂ and GF(2). The field elements are 0 and 1. The field operations + and − are identical and become the exclusive or operation (xor). The multiplication operator * becomes the logical and operation. The division operator reduces to the identity operation (i.e., field division is only defined for dividing by 1, and x/1 = x).

1. Let $s_{0},s_{1},s_{2}\cdots s_{n}$ be the bits of the stream.
2. Initialise two arrays $b$ and $c$ each of length $n$ to be zeroes, except $b_{0}\leftarrow 1,c_{0}\leftarrow 1$
3. assign $L\leftarrow 0,m\leftarrow -1$.
4. For $N=0$ step 1 while $N<n$:
   • Let $d$ be $s_{N}+c_{1}s_{N-1}+c_{2}s_{N-2}+\cdots +c_{L}s_{N-L}$.
   • if $d=0$, then $c$ is already a polynomial which annihilates the portion of the stream from $N-L$ to $N$.
   • else:
     • Let $t$ be a copy of $c$.
     • Set $c_{N-m}\leftarrow c_{N-m}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},\dots$ up to $c_{n-1}\leftarrow c_{n-1}\oplus b_{n-N+m-1}$ (where $\oplus$ is the Exclusive or operator).
     • If $L\leq {\frac {N}{2}}$, set $L\leftarrow N+1-L$, set $m\leftarrow N$, and let $b\leftarrow t$; otherwise leave $L$, $m$ and $b$ alone.

At the end of the algorithm, $L$ is the length of the minimal LFSR for the stream, and we have $c_{L}s_{a}+c_{L-1}s_{a+1}+c_{L-2}s_{a+2}+\cdots =0$ for all $a$.

Code sample for the binary field in Java

The following code sample is for a binary field.

    public static int runTest(int[] array) {
        final int N = array.length;
        int[] b = new int[N];
        int[] c = new int[N];
        int[] t = new int[N];
        b[0] = 1;
        c[0] = 1;
        int l = 0;
        int m = -1;
        for (int n = 0; n < N; n++) {
            int d = 0;
            for (int i = 0; i <= l; i++) {
                d ^= c[i] * array[n - i];
            }
            if (d == 1) {
                System.arraycopy(c, 0, t, 0, N)
                int N_M = n - m;
                for (int j = 0; j < N - N_M; j++) {
                    c[N_M + j] ^= b[j];
                }
                if (l <= n / 2) {
                    l = n + 1 - l;
                    m = n;
                    System.arraycopy(t, 0, b, 0, N)
                }
            }
        }
        return l;
    }

Berlekamp–Massey algorithm for fields

The algorithm from Massey (1969, p. 124).

  polynomial(field K) s(x) = ... /* coeffs are s_j; output sequence as N-1 degree polynomial) */
  /* connection polynomial */
  polynomial(field K) C(x) = 1;  /* coeffs are c_j */
  polynomial(field K) B(x) = 1;
  int L = 0;
  int m = 1;
  field K b = 1;
  int n;
  
  for (n = 0; n < N; n++)
    {
      /* calculate discrepancy */
      field K d = s_n + \Sigma_{i=1}^L c_i * s_{n-i};
  
      if (d == 0)
        {
          /* anihilation continues */
          m = m + 1;
        }
      else if (2 * L <= n)
        {
          /* temporary copy of C(x) */
          polynomial(field K) T(x) = C(x);
  
          C(x) = C(x) - d b^{-1} x^m B(x);
          L = n + 1 - L;
          B(x) = T(x);
          b = d;
          m = 1;
        }
      else
        {
          C(x) = C(x) - d b^{-1} x^m B(x);
          m = m + 1;
        }
    }
  return L;

See also

• Reeds–Sloane algorithm, an extension for sequences over integers mod n

References

Reeds, J. A.; Sloane, N. J. A. (1985), "Shift-Register Synthesis (Modulo n)" (PDF), SIAM Journal on Computing, 14 (3): 505–513, doi:10.1137/0214038

External links

• Berlekamp–Massey algorithm at PlanetMath.
• Weisstein, Eric W. "Berlekamp–Massey Algorithm". MathWorld.
• Implementation in Mathematica
• Template:De icon Applet Berlekamp–Massey algorithm