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 am looking into sequences generated by LFSRs (linear shift register sequences). I was wondering if sequences corresponding to reciprocal connection polynomials (that is, corresponding to shift registers with the taps reversed) are equivalent.

When I say "equivalent" I mean that they are shift-equivalent (one is equal to some shift of the other) and produced by maybe different states.

All the baby-examples that I did by hand were confirming that this is true, however I don't know if that is the case with bigger examples.. I also could not prove something theoretically.

share|improve this question
    
I wish you would have asked me four or five years ago: I could probably have told you the answer right away :) Are you learning about it in the context of convolutional codes? –  rschwieb Feb 5 '13 at 19:17
    
Ah, no. I am studying LFSRs for their own sake, possibly later I'll see some applications in cryptography. In particular I was studying the Berlekamp-Massey algorithm which returns the connection polynomial of a given a sequence if enough elements of the sequence are given. The implementation in sage seems to return the reciprocal and I'm trying to figure out what gives.. That said, I find it kind of an interesting question on its own.. –  geo909 Feb 5 '13 at 22:43
2  
Reciprocal should yield reverse order sequences. Like binary $m$-sequences of length 7: $1001011(1001011)$ vs $1001110(1001110)$. One is generated by $1+D+D^3$ the other by the reciprocal $1+D^2+D^3$. But which is which? I can't tell except by checking out the definition :-) Which end of the LFSR are the bits exiting from again? I always go back to first principles when encountering a problem like this, because IIRC there are two reasonable ways of thinking about it leading to reciprocal results. I guess one is standard, but I always double check which way it goes :-) –  Jyrki Lahtonen Feb 6 '13 at 20:17
    
Thanks for the feedback! The definition according to the paper that I am reading ("Shift-Register Synthesis and BCH Decoding", by J.L. Masssey) is that the leading coefficient corresponds to the output bit. Now, regarding the reciprocal thing: Do you have any reference or hints about the proof? And furthermore, are you sure that this holds for non-maximal sequences (i.e. when the corresponding polynomial is non-primitive)? –  geo909 Feb 6 '13 at 23:25

1 Answer 1

up vote 3 down vote accepted

Expanding on @JyrkiLahtonen's comment, suppose that an LFSR with feedback polynomial $\Lambda(z) = 1 + \lambda_1z + \cdots + \lambda_Lz^L$ of degree $L$ (meaning that $\lambda_L\neq 0$) generates a sequence $S_0, S_1, \ldots, S_{2L-1}, \ldots$. This sequence satisfies the linear recurrence: $$S_{i} + \lambda_{1}S_{i-1} + \lambda_2S_{i-2} + \cdots + \lambda_LS_{i-L} = 0, ~ i = L, L+1, \ldots $$ with $S_L = -\left(\lambda_Ls_0 + \lambda_{L-1}s_1 + \cdots + \lambda_1s_{L-1}\right)$ being the first element that is computed from the initial contents $(S_0, S_1, \ldots, S_{L-1})$ of the LFSR and fed back into the right end of the LFSR as the contents shift left by one place. The symbol $S_0$ on the left falls off the end of the register and is the output of the shift register. Note that the output will in succession have value $S_0, S_1, S_2, \ldots$. In a finite field, the sequence generated by an LFSR is periodic with the period depending on the irreducible factors of $\Lambda(z)$ as well as the initial loading of the LFSR.

The reverse polynomial of $\Lambda(z)$ is $$\tilde{\Lambda}(z) = z^L\Lambda(z^{-1}) = \lambda_L + \lambda_{L-1}z + \cdots + \lambda_1z^{L-1} + z^L$$ which has the same coefficients as $\Lambda(z)$ but running in reverse order. Now suppose that $K \gg L$ is some fixed positive integer. Then, we have that $$\begin{align} S_{K} + \lambda_{1}S_{K-1} + \lambda_2S_{K-2} + \cdots + \lambda_{L-1}S_{K-L+1} + \lambda_LS_{K-L} &= 0\\ (\lambda_L^{-1})S_K + (\lambda_L^{-1}\lambda_{1})S_{K-1} + (\lambda_L^{-1}\lambda_2)S_{K-2} + \cdots + (\lambda_L^{-1}\lambda_{L-1})S_{K-L+1} + S_{K-L} &= 0\\ \end{align}$$ and so $S_{K-L} = -\left((\lambda_L^{-1})S_K + (\lambda_L^{-1}\lambda_{1})S_{K-1} + (\lambda_L^{-1}\lambda_2)S_{K-2} + \cdots + (\lambda_L^{-1}\lambda_{L-1})S_{K-L+1}\right).$ Working our way out of this thicket of subscripts, let us consider an LFSR whose feedback polynomial is the scalar multiple $$\lambda_L^{-1}\tilde{\Lambda}(z)= 1 + (\lambda_L^{-1}\lambda_{L-1})z + \cdots + (\lambda_L^{-1}\lambda_1)z^{L-1} + (\lambda_L)^{-1}z^L$$ of $\tilde{\Lambda}(z)$, and whose initial loading is $(S_K, S_{K-1}, \ldots, S_{K-L+1})$. The term $S_{K-L}$ is computed and fed back into the right end of the LFSR register, etc. Thus the output of this LFSR whose feedback polynomial is a scalar multiple of the reverse polynomial of $\Lambda(z)$ will, in succession, be $$S_K, S_{K-1}, S_{K-2}, \ldots, S_1, S_0, \ldots$$ that is, a sequence that is shift-equivalent to the reverse of the sequence $S_0, S_1, \ldots, $ generated by the LFSR with feedback polynomial $\Lambda(z)$.

share|improve this answer
    
Thank you sir for helping me one more time with my understanding of LFSRs! –  geo909 Feb 22 '13 at 18:05

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.