3
$\begingroup$

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 :

$f(X)=(\sum_{i=0}^{n}{a_iX^{-(i+1)}}+\sum_{i=n}^{\infty}{b_iX^{-(i+1)}})g(X)$,

Why this last expression?

  • 1
    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?2011-11-23
  • 0
    @Dilip Sarwate thanks by your response, I edit the question, ... with your suggestions, I like too a design to general case to this problem please ....2011-11-24
  • 0
    @Dilip Sarwate thanks by your response, I edit the question, ... with your suggestions, I like too a design to general case to this problem please ...., about your response F(X) = f(X)?, where are $a_i$ values?2011-11-24
  • 0
    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}$2011-11-23
  • 0
    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.2011-11-23
  • 0
    Hi Jyrki, the minimal polynomial is $x^4 + x + 1$2011-11-23
  • 0
    @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.2011-11-24
  • 0
    Hi Dilip thanks by your response, I test if $x^4+x+1$, is irreducible in SAGE, that program say yes is irreducible, ... you can me which factor have $x^4+x+1$ ?2011-11-24
  • 0
    @Juan: Over $GF(16)$ we have the factorization $$x^4+x+1=(x+a)(x+a^2)(x+a^4)(x+a^8)=(x+a)(x+a^2)(x+a+1)(x+a^2+1).$$ This polynomial is irreducible over $GF(2)$ though. Your $g(x)$ has $1$, $a^{10}$, $a^7$ and $a^6$ as zeros, so I'm a bit curious as to why are you doing this? For example, it doesn't look like a generator polynomial of an RS-code. Meanwhile, Dilip has given a good answer. I seem to have missed the boat more or less :-)2011-11-24
  • 0
    @Jyrki: Is this what you had in mind?2011-11-24
  • 0
    sorry the g(X) = X^4 + (a + 1)*X^3 + (a^3 + a)*X^2 + a*X + 1 and R= (a^3 + a^2 + 1)*X + a^2 + a + 1 please I need a design for this LFSR2011-11-24

1 Answers 1

5

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$.

  • 0
    I understand your explication, but I don't know how design2011-11-24
  • 0
    I understand your explication, but I don't know how design, pdta: I edit question, ... See my other question please2011-11-24
  • 0
    @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.SE2011-11-25
  • 0
    +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.2011-11-27
  • 0
    @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.2011-11-27
  • 0
    @Dilip Thanks for that extra bit! Makes sense.2011-11-27