Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading a paper and say this

"The idea is to load $f(X)$ into LFSR to multiply by $X$ mod $g(X)$(primitive polynomial deg $g=n$). We next compute a polynomial h(X) whose coefficients are given by successive values of a particular cell of register".

and say "$h(Y)=\sum_{i=0}^{n-1}{a_iY^i}$, where $a_i$ is a coefficient of $X^{n-1}$ in $X^if(X)$ mod $g(X)$"

My question, Please help me How design this LFSR? and The paper too say :


Why this last expression?

share|improve this question
Hi thanks by your response,here a an example For example: $K_2[a] = GF(2^4),F[X] = {\rm Polynomial Ring}(K_2[a])$ Give: $g(X) = (X + 1) * (X + a^2 + a + 1) * (X + a^3 + a + 1) * (X + a^3 + a^2)$ $\eqalign{f(X) &= a^2*X^3 + (a^3 + a)*X^2 + (a^3 + 1)*X\cr}$ –  juaninf Nov 23 '11 at 15:15
What's the minimal polynomial of $a$? I will return to this later, but will be off-air for a few hours. If this is urgent, hopefully somebody else can answer. –  Jyrki Lahtonen Nov 23 '11 at 15:30
Do you want to know how to design the LFSR, or how to compute the coefficients of the polynomial $h(X)$? Also, please edit your question a little. Did you write "$x \bmod g(X)$" instead of $X \bmod g(X)$"? Is $h(X)$ a polynomial in $X$ as the name suggests, or is it a polynomial in $y$ as $\sum a_i y^i$ seems to indicate? –  Dilip Sarwate Nov 23 '11 at 19:16
Hi Jyrki, the minimal polynomial is $x^4 + x + 1$ –  juaninf Nov 23 '11 at 21:57
@Juan $x^4 + x + 1$ is not irreducible over $GF(2^4)$. Again I ask you, please edit your question so that it is less ambiguous. –  Dilip Sarwate Nov 24 '11 at 1:42

1 Answer 1

In this question, the LFSR is a Galois-field LFSR. If $F(X) = \sum_{i=0}^{n-1} f_iX^i$, where $f_i \in \mathbb F_q$, then the initial contents of the LFSR can be interpreted as the element $$\beta = f_0 +f_1\alpha + \cdots + f_{n-1}\alpha^{n-1} \in \mathbb F_{q^n}$$ where $\alpha$ is a primitive element of $\mathbb F_{q^n}$ whose minimal polynomial is $g(X)$. Then the next contents of the shift register are $XF(X) \bmod g(X)$ which is just the element $\beta\alpha$, and so on, with the $i$-th contents being $X^iF(X) \bmod g(X)$ which is the element $\beta\alpha^i$.

Turning to the mechanics of the LFSR, the initial contents are $F(X)$. Now, $g(X) = X^n + g_{n-1}X^{n-1} + \cdots + g_1X + g_0$ and so $$\begin{align*} XF(X) &= f_0X + f_1X^2 + \cdots + f_{n-2}X^{n-1} + f_{n-1}X^n\\ &\equiv -f_{n-1}g_0 + (f_0-f_{n-1}g_1)X + \cdots + (f_{n-2}-f_{n-1}g_{n-1})X^{n-1} \bmod g(X) \end{align*} $$ where the second equation is obtained from the first by subtracting $f_{n-1}g(X)$ from the right side of the first. Note that the individual symbols in the LFSR change instead of just shifting over with a new symbol being introduced at one end as happens in Fibonacci LFSRs. In more detail, if the LFSR contains $$ \mathbf f^{(i)} = (f_0^{(i)}, f_1^{(i)}, \cdots, f_{n-1}^{(i)}) $$ after $i$ iterations (initial contents $\mathbf f^{(0)} = (f_0, f_1, \cdots, f_{n-1})$), then the LFSR contents after $i+1$ iterations are $$\begin{align*} \mathbf f^{(i+1)} &= (f_0^{(i+1)}, f_1^{(i+1)}, \cdots, f_{n-1}^{(i+1)})\\ &= (-f_{n-1}^{(i)}g_0, f_0^{(i)}-f_{n-1}^{(i)}g_1, \cdots, f_{n-2}^{(i)}-f_{n-1}^{(i)}g_{n-1}). \end{align*} $$ Thus, $\mathbf f^{(i+1)} = \mathbf f^{(i)}\mathbf G$ where $\mathbf G$ is the companion matrix of $g(X)$. The output of the LFSR is the contents of the rightmost cell, i.e., $h_i = f_{n-1}^{(i)}$, and the sequence $(h_0, h_1, \ldots)$ is an m-sequence of period $q^{n}-1$ over $\mathbb F_q$.

share|improve this answer
I understand your explication, but I don't know how design –  juaninf Nov 24 '11 at 20:52
I understand your explication, but I don't know how design, pdta: I edit question, ... See my other question please –  juaninf Nov 24 '11 at 21:16
@Juan The design is essentially specified in the last few sentences in my answer. If you need help in implementing the LFSR in MATLAB or C or on a specific DSP chip, or in electrical circuits, or if you need to implement Galois field adders and multipliers, then please ask on sister sites dsp.SE or electronics.SE –  Dilip Sarwate Nov 25 '11 at 17:08
+1 Nothing to add. I fumbled this one. With the help of multipliers we could design a circuitry that resembles a Fibonacci LFSR, but the direction of the flow of the symbols has to be reversed, because upon multiplication by $x$ the highest degree term overflows, and yields additions to several (if not all) other terms. –  Jyrki Lahtonen Nov 27 '11 at 20:29
@Jyrki Fibonacci LFSRs and Galois-field LFSRs with primitive feedback polynomials both have the property that the contents are successively $\beta$, $\beta\alpha$, $\beta\alpha^2$, $\ldots\in\text{GF}(q^n)$, where $\alpha$ is a root of $g(x)$. In the Galois-field LFSR case, these elements are represented with respect to the standard polynomial basis $\{1,\alpha,\ldots,\alpha^{n-1}\}$ while in Fibonacci LFSRs, it is with respect to the dual of the polynomial basis. It is possible to keep the same direction of flow and use a Fibonacci LFSR, but the details are too long to fit in this comment. –  Dilip Sarwate Nov 27 '11 at 21:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.