Fibonacci linear feedback shift register - connection to polynomials

Question

Operation and behaviour of linear feedback shift register (LFSR) can be viewed as some operations on polynomials.

For Galois LFSR the link between the LFSR and polynomials is quite simple and straightforward.
If $n$ is the number of bits in the register, then current state of the Galois LFSR is equivalent to polynomial $p(x) = b_nx^n + b_{n-1}x^{n-1} + ... + b_1x + b_0$, where $b_i$ is the value of $i$-th bit of the register. The tapped positions are described by a polynomial $q(x) = x^{n+1} + c_nx^n + c_{n-1}x^{n-1} + ... + c_1x + c_0$, where $c_i = 1$ if $i$-th bit is tapped, $0$ otherwise. The change of the state of the register is then defined by equation:

$$p'(x) = xp(x) + \alpha q(x)$$

where $p'(x)$ is a polynomial equivalent to the new state of the register and $\alpha = b_n$ (the coefficient of $x^n$ in $p(x)$).

My question is about analogous relation for Fibonacci LFSR - what is the polynomial that describes current register state? what polynomial is defined by taps positions? what is the equation that defines the relationship between new and current state?

Answer 1

I answered this question in my post: Fibonacci LFSR - Multiplication in the dual of the polynomial basis. I was wondering the same as you.

In short:

• the polynomial is represented in the dual of the polynomial basis,
• the multiplication by $x$ is computed in the dual of the polynomial basis (which gives the below reccurence relation),
• you take the same characteristic polynomial as the Galois LFSR (but some would prefer the reflected polynomial),
• the recurrence relation depends on which coefficient you take as an output for the LFSR.

I assume that you are in $GF(2^{n+1})$. For example, let $p^{*}(x)$ be the polynomial $p(x)$ expressed in the dual basis. If you take the value of its coefficent $b^{*}_{0}$ as an output, the coefficients for the following state $p^{\prime \: *}(x)$ are: \begin{align} b^{\prime \: *}_{i} &= b^{*}_{i+1} \: \text{ for } i \in [0,n-1], i \in \mathbb{N},\\ b^{\prime \: *}_{n} &= Tr(p^{∗}(x) \cdot x_{n+1}) \: \text{ which corresponds to the taps,} \end{align} and $Tr$ is the trace (see Wikipedia - Field trace).

However, I have seen the order reversed. In that case, the value of the coefficient $b^{*}_{n}$ is taken as the Fibonacci's LFSR output. For this, we thus have the following recurrence relation: \begin{align} b^{\prime \: *}_{i} &= b^{*}_{i-1} \: \text{ for } i \in [1,n], i \in \mathbb{N},\\ b^{\prime \: *}_{0} &= Tr(p^{∗}(x) \cdot x_{n+1}) \: \text{ which corresponds to the taps.} \end{align}