Linear Feedback Shift Register over $\mathbb F_q$

Question

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?

Answer 1

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.