Finding generating function of LFSR Hey I have one sequence which I need to create from LFSR. I need to find the generating function from that sequence. How can I do that? Sequence is 001011011101000000.
Thanks
 A: The general approach for finding the generating function from an LFSR, is given as follows:
Let's assume you have an LFSR that goes from right to left, with initial conditions a-1,a-2,...a-r and the feedback coefficients are c1,c2,...cr (from left to right). Note that for LFRS, we work in mod 2, so all feedback coefficients are either 1 or 0.
Once you set your reccurence relation for the the sequence {an}, you get something like this:
an= c1*an-1+c2*an-2+...+cr*an-r......(1)
the generationg function for this reccurence relation, for the given LFRS, is given as follows:
G(x)= [c1*x^1*(a-1*x^-1)+c2*x^2*(a-2*x^-2+a-1*x^-1)+...+crx^r(a-r*x^-r+...+a-1*x^-1)]/[1-(c1*x^1+c2*x^2+...+cr*x^r)]........(2)
(here x^-r refers to the reciprocal of x, i.e. 1/x^r)
this formula can be found by inserting the reccurence relation (1) in the general formula for generating functions which is given by : 
G(x)= SUM(an*x^n) (from n=0 to n=infinity).
Then playing with the indices and rearranging we get (2).
Example: Let's say, you are given 1-x-x^3-x^4 with initial conditions 1100.
and find the generating function for this LFRS?
Solution:  here the initial conditions a-1=1, a-2=1, a-3=0 and a-4=0. and note the feedback coefficients can be found as c1=1, c2=0, c3=1, c4=1. To see how we got this I will try to draw the LFRS as follows:
              ---|c1=1| |c2=0| |c3=1| |c4=1|
             |      |      |      |     |
              -->|a-1=1|a-2=1|a-3=0|a-4=0|----->

This corresponds to  1-x-x^3-x^4 (this is the characteristic polynomial of the reccurrence). 
The reccurence can eaisly be found from that characteristic equation as follows:
        an= an-1+an-3+an-4 and compare this with 

        an= c1*an-1+c2*an-2+c3*an-3+c4*an-4

so the feed back coefficients are found as c1=1,c2=0,c3=1,c4=1.
Now all you have to do is to insert these values in the formula (2) and you get:
G(x)= [x(1/x)+x^3(1/x+1/x^2)+x^4(1/x+1/x^2)]/[1-(x+x^2+x^3+x^4)]
then,
G(x)= (1+x+x^3)/(1+x+x^3+x^4) is the generating function of the given LFSR.
Note: remember you are in mod 2, so -1=1 in this space. You can replace your -'s with +'s.
You can now do your calculations for the given sequence: 001011011101000000.
I guess that these are the initial conditions right?
And you also need the characteristic formula, to calculate the generating function. What is your characteristic function? Your question may be lack of this information. 
