2
$\begingroup$

I have some questions about the Linear Feedback Shift Register=LFSR. Let $C(X)=c_0+c_1X+...+c_{K-1}X^{K-1}+X^K$ be the feedback polynomial for a LFSR over $\mathbb F_q$ where $c_0\not=0$. There are two things I do not see (in a formal way). The first thing is, why is the output stream $(x_j)$ periodic? The second thing is that there is a $K\times K$ matrix $M$ with $(x_j,x_{j+1},...,x_{j+K-1})=M^j(x_0,...,x_{K-1})$ for $j=0,1,2,...$ I do not see where this comes from?

$\endgroup$
5
  • $\begingroup$ Unfortunate typo. $\endgroup$
    – mjqxxxx
    Nov 25, 2013 at 4:19
  • $\begingroup$ It's not just in the title. $\endgroup$
    – 2'5 9'2
    Nov 25, 2013 at 4:22
  • 5
    $\begingroup$ Shift happens... $\endgroup$ Nov 25, 2013 at 4:22
  • $\begingroup$ Sorry for that. $\endgroup$
    – Alkibiades
    Nov 25, 2013 at 4:22
  • 2
    $\begingroup$ The output is determined by the $K$ previous inputs, for which there are only finitely many possibilities. Once the inputs repeat, they must repeat forever. $\endgroup$ Nov 25, 2013 at 4:24

1 Answer 1

2
$\begingroup$

Take the Fibonacci sequence as a small example, $F_n = F_{n-1} + F_{n-2}$. Each term is the sum of the previous two. Here we have the matrix equation, it needs to be two dimensional in this case $$\pmatrix{1 & 1 \\ 1 & 0}\pmatrix{F_{n-1} \\ F_{n-2}} = \pmatrix{F_n \\ F_{n-1}}$$

Each iteration of the sequence is found from the previous iteration by multiplication with the matrix. If $F_0 = F_1 = 1$ then we have $F_2 = 2$ $$\pmatrix{1 & 1 \\ 1 & 0}\pmatrix{1 \\ 1} = \pmatrix{2 \\ 1}$$ and in general $$\pmatrix{1 & 1 \\ 1 & 0}^n\pmatrix{1 \\ 1} = \pmatrix{F_{n+1} \\ F_{n}}$$

In your case you have $$C(X)=c_0+c_1X+...+c_{K-1}X^{K-1}+c_K X^K$$ which gives your recursion as $$ c_0x_K = -c_1x_{K-1} - c_2x_{K-2} - \ldots - c_{K-1}x_{ 1} - c_Kx_{0}$$ or $$ x_K = -c_0^{-1}c_1x_{K-1} - c_0^{-1}c_2x_{K-2} - \ldots - c_0^{-1}c_{K-1}x_{0} - c_0^{-1}c_Kx_{0}$$ which in matrix form looks like $$\pmatrix{-c_0^{-1}c_1 & - c_0^{-1}c_2 & \ldots &-c_0^{-1}c_{K-1} & -c_0^{-1}c_K \\ 1 & 0 & \ldots & 0 & 0\\ 0 & 1 & \ldots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0& \ldots & 1 &0}\pmatrix{x_{K-1} \\ x_{K-2} \\ \vdots \\ x_{1} \\ x_{0}} = \pmatrix{x_{K} \\ x_{K-1} \\ \vdots \\ x_{2} \\ x_{1}}$$

where you can see that the vector of values is shifted by one when multiplied once with the matrix, hence the name linear feedback shift.

$\endgroup$
3
  • $\begingroup$ Thanks for our answer, but how does this is related to my matrix $M$? $\endgroup$
    – Alkibiades
    Nov 25, 2013 at 20:14
  • $\begingroup$ Thanks, one last thing. How can I evaluate the characteristic and minimal polynomials fr $M$? $\endgroup$
    – Alkibiades
    Nov 26, 2013 at 0:29
  • $\begingroup$ That is a different question, maybe it would be good to post it. But you may want to look at http://en.wikipedia.org/wiki/Companion_matrix $\endgroup$
    – adam W
    Nov 26, 2013 at 0:34

You must log in to answer this question.

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