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:
Let $s_0, s_1, \dots, s_9$ be the bits 0,0,1,0,0,0,1,1,1,1.
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}
Let L = 0, m = -1
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.