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.^[1] Its connection to linear codes was observed by James Massey the following year.^[2] 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 sequenceLength)
        {
            b = new byte[sequenceLength];
            c = new byte[sequenceLength];
            t = new byte[sequenceLength];
            s = new byte[sequenceLength];
            for (int i = 0; i < sequenceLength; 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++;
                }
                
            }
        }

Code sample in Java

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

See also

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

References

1. Algebraic Coding Theory, New York: McGraw-Hill, 1968. Revised ed., Aegean Park Press, 1984, ISBN 0894120638.
2. J. L. Massey, Shift-register synthesis and BCH decoding, IEEE Trans. Information Theory, IT-15 (1969), 122-127.

External links

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