# Linear Feedback Shift Register over $\mathbb F_q$

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?

• Unfortunate typo. Nov 25, 2013 at 4:19
• It's not just in the title. Nov 25, 2013 at 4:22
• Shift happens... Nov 25, 2013 at 4:22
• Sorry for that. Nov 25, 2013 at 4:22
• 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. Nov 25, 2013 at 4:24

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}}$$
• Thanks for our answer, but how does this is related to my matrix $M$? Nov 25, 2013 at 20:14
• Thanks, one last thing. How can I evaluate the characteristic and minimal polynomials fr $M$? Nov 26, 2013 at 0:29