LFSR

Formula:-

summation -> E,


a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
maximum number to run -> m - 1
start number to run -> i = 0
m is the degree
f_{i} will be obtained from the function ........f(x)


formula to find the period of sequence -> 2^{m} - 1 , e.g , degree
m=4, so 2^{4} - 1=15


Example: f(x) = 1 + x^{2} +x^{4}, seed given 0010, generate the
sequence


Solution:
Step 1: Get sequence f_{i} from function,
start to put x^{0} until x^{4}
........NOTE: every function by default sure have the last degree
so we ignore the power of 4
f(x) = [_]. x^{0} + [_]. x^{1} + [_].x^{2} + [_]. x^{3} + [_]. x^{4}
...........fill in the blank based on the funciton given [_]
f(x) = [1]. x^{0} + 0]. x^{1} + [1].x^{2} + [0]. x^{3} + [1]. x^{4}
...........so, we get the
f_{0} + f_{1} + f_{2} + f_{3}
1 0 1 0

Step 2: Use formula
a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}


we know this is degree 4 based on function given. m = 4,
p/s:seed is the starting of the sequence
i build initial table
n : 1 2 3 4
a_{n} : 0 0 1 0
..........so we have to find number 5 item, n = 5


a_{n} = ^{m - 1} E _{i = 0} f_{i}a_{n - m + i}
a_{5} = ^{4 - 1} E _{i = 0} f_{i}a_{5 - 4 + i}
a_{5} = f_{0}a_{5 - 4 + 0} +
f_{1}a_{5 - 4 + 1} +
f_{2}a_{5 - 4 + 2} +
f_{3}a_{5 - 4 + 3}
........we susitute f number only so we can find the common formula
a_{5} = 1 x a_{5 - 4 + 0} +
0 x a_{5 - 4 + 1} +
1 x a_{5 - 4 + 2} +
0 x a_{5 - 4 + 3}
........we remove the f with 0 value
a_{5} = 1 x a_{5 - 4 + 0} +
1 x a_{5 - 4 + 2}
........substitue the item value 5 back to n
a_{n} = a_{n - 4 + 0} +
a_{n - 4 + 2}
........we got the formula
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used


Step 3: Generate Sequence

n :1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
a_{n}:0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0

since we know the period of seq is 15 so 20 should be more than enough
a_{n} = a_{n - 4 } + a_{n - 2}.............formula to be used
when n = 5,
a_{5} = a_{5 - 4 } + a_{5 - 2} =a_{1} + a_{3} mod 2
= 0 + 1 = 1 mod 2

repeat until n = 20
when n = 6, a_{6} = a_{6 - 4 } + a_{6 - 2}
= a_{2} + a_{4} mod 2
= 0 + 0 = 0 mod 2