I'm trying to use the Berlekamp-Massey algorithm on the following bit sequence:

0 1 0 0 1 0 0 1 0 1

I have the correct answer and most of the approach to get there, but I'm unable to fill in what I don't have, in other words I don't understand how it works.

I create a table, written horizontally here just for convenience:

N: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 S_N: Ø, ... f_N: 1, ... L_N: 0, ...

Where ... means the values I should determine using the BM algorithm. Ø is the empty set.

I have already filled in the values for S_0, f_0 and L_0, as these are trivial.

My first step is to calculate f_1:

This is the formula that I use, this is directly copied from some printed lecture notes, so it should be correct.

$$f_1 = \begin{cases} f_N + X^{2L-N-1}\cdot f_m, & \mbox{if } L > N/2 \\ X^{N-2L+1}\cdot f_N + f_m, & \mbox{if } L \leq N/2 \end{cases}$$

We see that for the case of f_1, L = 0 and N = 0, hence we use the lower case:

$$f_1 = X^{N-2L+1}\cdot f_N + f_m = X^{0-2\cdot 0+1}\cdot 1 + 1 = X + 1$$

However, from my known solution I know f_1 should be 1. I have double checked this, why do I get X + 1 when I just mechanically follow this simple formula? Is there something more to this that I'm overlooking?

  • $\begingroup$ What is $f_m$, you never define $m$. $\endgroup$
    – kodlu
    Sep 10, 2016 at 0:33


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.