What is "Fibonacci" about the Fibonacci LFSR? If I read right, Fibonacci LFSR means that it depends on its two last states, but from the example in Wikipedia it doesn't look like two states are taken in consideration (ie. XORing the taps in the current state, shifting and inputing the left bit..). What am I missing?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
"In computing, a linear-feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state." wiki quote.
Its output depends on state and polynomial, not two states.
The name come (afair) from Fibonacci work on recurence relation, his sequence, and further interest in characteristic polynomials of generating sequences, but the one who gave closed form solution to Fibonacci numbers and researched characteristic equation (the one used in generator with possibly minimal monic to make longest period), was Lucas. I cannot find any reference why it is called Fibonacci LFSR, but it is inventors will to name it.
The same stands for LFG - lagged Fibonacci generator was (in multiplicative form) introduced by Marsaglia to overcome deffects of additive one.
The real interest in random generation was started by Galton (if it matters Romans did toss coins and stored bits), random numbers by Pearson, first PRNG is attributed to von Neuman, first working one to Lehmer, as for Fibonacci his insights are nice, but he started his sequences to count rabbits with no connection to PRNG whatsoever.
Of you are interested in history of PRNG, History of uniform random number generation is nice.
$\begingroup$
$\endgroup$
If you take the "standard" Fibonacci sequence, starting with $0,1$, and take the terms modulo $2$ (or, equivalently, $x_n=x_{n-1}+x_{n-2} \mod 2$) then you get
$0,1,1,0,1,1, \dots$
and from this sequence you can read off the values of a $2$-bit LFSR: $01\rightarrow 11 \rightarrow 10 \rightarrow 01$ (MSB first).
Longer LFSRs can be constructed in a similar manner using recursion rules that look further back in the sequence e.g. $x_n=x_{n-2}+x_{n-3} \mod 2$ gives a $3$-bit LFSR:
$0,0,1,0,1,1,1,0,0,1, \dots\\ 001 \rightarrow 010 \rightarrow 101 \rightarrow 011 \rightarrow 111 \rightarrow 110 \rightarrow 100 \rightarrow 001$
