2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – rschwieb
    Feb 5, 2013 at 19:17
  • $\begingroup$ 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.. $\endgroup$
    – geo909
    Feb 5, 2013 at 22:43
  • 2
    $\begingroup$ 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 :-) $\endgroup$ Feb 6, 2013 at 20:17
  • $\begingroup$ 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)? $\endgroup$
    – geo909
    Feb 6, 2013 at 23:25

1 Answer 1

3
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ Thank you sir for helping me one more time with my understanding of LFSRs! $\endgroup$
    – geo909
    Feb 22, 2013 at 18:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .