Berlekamp-Massey to construct minimal LFSR

Question

Given the sequence 0010001111 (or any other, not homework, but exam practice), how do you use the Berlekamp-Massey algorithm to construct a minimal LFSR?

I have read several definitions of how Berlekamp-Massey works, but I'm missing some simple example that actually demonstrates the algorithm in use.

Trying to use the following http://en.wikipedia.org/wiki/Berlekamp-Massey#The_algorithm_for_the_binary_field this is how far (or short) I get:

1. Let $s_0, s_1, \dots, s_9$ be the bits 0,0,1,0,0,0,1,1,1,1.

2. Let the arrays b and c, each of length 10, be: b = {1,0,0,0,0,0,0,0,0,0}, c = {1,0,0,0,0,0,0,0,0,0}

3. Let L = 0, m = -1

4. Iterate 10 times:

Iteration 0:

$$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$

Already at this first iteration (0) I run into problems. What are these negative subscript s variables?

I'm using the formula on Wikipedia, which is:

$$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$

Is there a fault in this formula? Earlier at step 3, the algorithm states L = 0, hence the final term with:

$$c_Ls_{N-L}$$

makes no intuitive sense if it is taken literally? I assume that the subscript of this s variable should keep decreasing and for c it should keep increasing? If taken as the formula states it, these would be just 0?

But regardless, there is this problem with the negative s variables.

Answer 1

There are no issues with negative indices, even the first (or zero-th depending on how you want to count them) iteration.

The quantity $d$ is called the discrepancy. During the $N$-th iteration, $d$ is the difference between $s_N$, the $N$-th bit of the given sequence for which you are finding the LFSR, and the bit computed by the LFSR that you have synthesized thus far. If $d=0$, the bit produced by the LFSR is the same as the bit in the given sequence and so the current LFSR, which is guaranteed to produce $s_0, s_1, \ldots, s_{N-1}$, need not be changed: it is producing $s_N$ also. On the other hand, if $d \neq 0$, then the current LFSR needs to be updated, that is, you need to find the shortest LFSR that produces not just $s_0, s_1, \ldots, s_{N-1}$ but also $s_N$. How to go about doing this is the crux of the Berlekamp-Massey algorithm. Note that it is easy to find an LFSR that will produce $s_0, s_1, \ldots, s_{N}$: the trick lies in finding the shortest LFSR that will do so.

With that as background, and the further information that $L$ is an upper bound on the number of stages in the current LFSR, consider the discrepancy calculation $$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ which really ought to be expressed as $$d = c_0s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ but the simpler version works because $c_0 = 1$ always (see the initialization). Now, we begin with $c_0 = 1$ and all other $c_i = 0$, that is, a trivial LFSR with no stages that will produce $0$s for all eternity if you ask it to. In the very first calculation when $L=0$ and $N=0$, we have $$d = c_0 s_0 = s_0.$$ If you want to use the full-fledged form $$d = s_0 + c_1s_{-1} + c_2s_{-2} + \cdots + c_9s_{-9}$$ that is fine, as long as you remember that $c_1=c_2=\cdots=c_9 = 0$, and the values you choose to ascribe to $s_{-1}, s_{-2}, \ldots, s_{-9}$ don't affect the computation at all. But more realistically, you should note that $L=0$ and $N=0$, and so the term $c_Ls_{N-L}$ that makes no sense to you is just $c_0s_{0-0}=c_0s_0=s_0$, just it ought to be.

In the form $$d = s_N + c_1s_{N-1} + c_2s_{N-2} + \cdots + c_Ls_{N-L}$$ correctly interpreted, you never run out of bits because $c_{L+1}, c_{L+2}, \ldots$ are all guaranteed to be $0$ and $L$ is upper bounded by $N$ and so $s_{N-L}$ can reach down to $s_0$, the leading bit of the given sequence, but no farther.

There are no negative subscripts on $s$ (or $c$) that we ever need to worry about.