Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence:

0110010101101 producing LFSR $\langle{}7, 1 + x^3 + x^4 + x^6\rangle{}$

i.e. coefficients $c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, c_6 = 1, c_7 = 0$

however, when using the recurrence relation \begin{equation} s_j = (c_1s_{j-1} + c_2s_{j-2} + \cdots + c_Ls_{j-L}) \mbox{ for } j \geq L. \end{equation} to check the result, I get back:

0110010001111, which is obviously not right.

Using the online calculator here they say the (I believe) characteristic polynomial should be $x^7 + x^4 + x^3 + x^1$. Which, according to my paper working, the reciprocal should indeed be $1 + x^3 + x^4 + x^6$.

What am I doing wrong? / Where is my understanding lacking?

share|cite|improve this question
Could you post a link to the Berlekamp-Massey algorithm that is not behind IEEE's paywall? – Dilip Sarwate Apr 20 '12 at 22:08
Massey paper – jamesj629 Apr 20 '12 at 22:14
If a sequence can be generated by a shift register of length $t$, the Berlekamp-Massey algorithm is guaranteed to find the register and its feedback connections from knowledge of $2t$ successive symbols. Your bit sequence is of length $13$? – Dilip Sarwate Apr 21 '12 at 1:16
Cross-posted on CS.SE. Please don't cross-post. That fragments answers and violates site rules. – D.W. May 12 '14 at 22:22
up vote 3 down vote accepted

It seems to me that something went wrong, when you tried to regenerate the sequence. When the linear span is $7$ and the feedback polynomial is $1+x^3+x^4+x^6$, we have the recurrence relation $$ s_j=s_{j-3}+s_{j-4}+s_{j-6} $$ for all $j\ge 7$.

Your sequence has $s_0=0$, $s_1=1$, $s_2=1$, $s_3=0$, $s_4=0$, $s_5=1$, $s_6=0$ as the initial segment. Using the above recurrence relation gives $$ \begin{aligned} s_7&=s_4+s_3+s_1=1,\\ s_8&=s_5+s_4+s_2=0,\\ s_9&=s_6+s_5+s_3=1,\\ s_{10}&=s_7+s_6+s_4=1,\\ s_{11}&=s_8+s_7+s_5=0,\\ s_{12}&=s_9+s_8+s_6=1, \end{aligned} $$ recovering the remaining of your input.

Hopefully this helps you in locating the bug, if any.

share|cite|improve this answer
There was indeed a bug in the code that generated the sequence back from the recurrence, which didn't show in any of the other test cases. Thank you. – jamesj629 Apr 25 '12 at 1:22

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.