Take the 2-minute tour ×
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.

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|improve this question
1  
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
add comment

2 Answers

up vote 2 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|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
add comment

Your answer is correct..Online calculator is giving wrong answer..I have cross checked with an example given in "Handbook of Cryptography"..My MATLAB code is also giving the same answer as yours..

share|improve this answer
    
I'm not sure that I understood what you are saying? The OP got the same LFSR as the on-line calculator. My answer checks the LFSR from the on-line calculator works. How is that a wrong answer? What am I missing? –  Jyrki Lahtonen Apr 24 '12 at 10:29
1  
"Characteristic" polynomials and "Connection" polynomials are not expressed in the same way (but some books and journals are confused over which one is which). You can find one from the other using $C(X) = X^L C'(X^{-1})$. –  jamesj629 Apr 25 '12 at 1:18
add comment

Your Answer

 
discard

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.