Error in Berlekamp-Massey Algorithm?

Question

I'm confused about the example given in James Massey's paper on what is now known as the Berlekamp-Massey Algorithm.

The example is the sequence $s_0, s_1, s_2, s_3, s_4 = 1, 0, 1, 0, 0$,

with

• $N=0: C = 1, B = 1, d=1 (=c_0s_0), L=0, x=1$

  $\implies C \leftarrow C - DB = 1+D $ and since $2L \leq N$, $B \leftarrow 1$, $L \leftarrow N+1-L = 1$.

• $N=1: C = 1+D, B=1, d=1 (=c_0s_1 + c_1s_0), L=1, x=1$

  $\implies C \leftarrow C - DB = 1 $ and since $2L > N$, $B$ and $L$ are unchanged and $x \leftarrow x+1 = 2$.

• $N=2: C = 1, B = 1, d=1 (=c_0s_2), L=1, x=2$

  $\implies C \leftarrow C - D^2B = 1 + D^2 $ and since $2L \leq N$, $B \leftarrow 1$, $L \leftarrow N+1-L = 2$, $x \leftarrow 1$.

• $N=3: C = 1+D^2, B = 1, d=0 (=c_0s_3 + c_1s_2 + c_2s_1), L=2, x=1$ $\implies x \leftarrow x+1 = 2$, but since $d=0$ the values $C, B, L$ are unchanged.

• $N=4: C = 1+D^2, B = 1, d=1 (=c_0s_4 + c_1s_3 + c_2s_2), L=2, x=2$ $\implies C \leftarrow C - D^2B = 1$ and since $2L \leq N$, $B \leftarrow 1+D^2$, $L \leftarrow N+1-L = 3$, $x \leftarrow 1$.

I'm confused about steps $N=2$ and $N=4$ where the connection polynomial $C=1$; this doesn't generate a pattern of LFSR outputs that matches the sequence $1,0,1,0,0$. What am I missing?

Answer 1

Oh, my mistake was in thinking it was a maximal length LFSR, which it's not --- for example with $C = 1, L=3$ (at step $N=4$) this represents a shift register with no feedback and 3 shift cells, so the output of $1, 0, 1, 0, 0, 0, 0, 0, 0, \ldots$ is possible if the shift cells are preloaded with a 101 pattern.