Berlekamp–Massey algorithm

Not to be confused with Berlekamp's algorithm.

The Berlekamp–Massey algorithm is an algorithm for finding the shortest linear feedback shift register (LFSR) for a given output sequence. Equivalently, it is an algorithm for finding the minimal polynomial of a linearly recurrent sequence.

The algorithm was invented by Elwyn Berlekamp in 1968. Its connection to linear codes was observed by James Massey the following year. It became the key to practical application of the now ubiquitous Reed–Solomon code.

The algorithm

1. Let ${\displaystyle s_{0},s_{1},s_{2}...s_{n}}$  be the bits of the stream.
2. Initialise three arrays ${\displaystyle b}$ , ${\displaystyle c}$  and ${\displaystyle t}$  each of length ${\displaystyle n}$  to be zeroes, except ${\displaystyle b_{0}\leftarrow 1,c_{0}\leftarrow 1}$ ; assign ${\displaystyle N\leftarrow 0,L\leftarrow 0,m\leftarrow -1}$ .
3. While ${\displaystyle N}$  is less than ${\displaystyle n}$ :
   • Let ${\displaystyle d}$  be ${\displaystyle s_{N}+c_{1}s_{N-1}+c_{2}s_{N-2}+...+c_{L}s_{N-L}}$ .
   • If ${\displaystyle d}$  is zero, then ${\displaystyle c}$  is already a polynomial which annihilates the portion of the stream from ${\displaystyle N-L}$  to ${\displaystyle N}$ ; increase ${\displaystyle N}$  by 1 and continue.
   • If ${\displaystyle d}$  is 1, then:
     • Let ${\displaystyle t}$  be a copy of ${\displaystyle c}$ .
     • Set ${\displaystyle c_{N-m}\leftarrow c_{N-m}\oplus b_{0},c_{N-m+1}\leftarrow c_{N-m+1}\oplus b_{1},...}$  up to ${\displaystyle c_{n-1}\leftarrow c_{n-1}\oplus b_{n-N+m-1}}$  (where ${\displaystyle \oplus }$  is the Exclusive or operator).
     • If ${\displaystyle L\leq {\frac {N}{2}}}$ , set ${\displaystyle L\leftarrow N+1-L}$ , set ${\displaystyle m\leftarrow N}$ , and let ${\displaystyle b\leftarrow t}$ ; otherwise leave ${\displaystyle L}$ , ${\displaystyle m}$  and ${\displaystyle b}$  alone.
     • Increment ${\displaystyle N}$  and continue.

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

Code Sample in C#

        byte[] b, c, t, s;
        int N, L, m;
        int position = 0;

        public BerlekampRegistryTester(int sequenceLenght)
        {
            b = new byte[sequenceLenght];
            c = new byte[sequenceLenght];
            t = new byte[sequenceLenght];
            s = new byte[sequenceLenght];
            for (int i = 0; i < sequenceLenght; i++) 
            {
                b[i] = c[i] = t[i] = 0;
            }
            b[0] = c[0] = 1;
            N = L = 0;
            m = -1;
        }

        private void runTest() 
        {
            int d;
            while (N < s.Length)
            {
                //STEP 1
                d = 0;
                for (int i = 0; i <= L; i++) 
                {
                    d += s[N-i] * c[i];
                }
                d = d % 2;

                //STEP 2
                if (d == 0)
                {
                    N++;
                    continue;
                }
                //STEP 3
                else
                {
                    //3.1
                    t = (byte[])c.Clone();
                    //3.2
                    for (int i = 0; i <= s.Length + m - 1 - N; i++)
                    {
                        c[N - m + i] = (byte)(c[N - m + i] ^ b[i]);
                    }
                    //3.3
                    if (L <= (N / 2))
                    {
                        L = N + 1 - L;
                        m = N;
                        b = (byte[])t.Clone();
                    }
                    else
                    {
                        //leave m,l,b alone
                    } 
                    N++;
                }
                
            }
        }

See also

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

External links

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