Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Galois VS Fibonacci LFSR, more computer-friendly but what else?

Tags:

algorithm

math

According the Linear feedback shift register page on Wikipedia,

Beside that the Galois LFSR is more computer-friendly, can you tell what are the real advantages of using a Galois one over a Fibonacci one ?

In other words, I am already satisfied with the results of the Fibonacci LFSR but in what the Galois one can be even better ?

Thank you :-)

like image 593
aybe Avatar asked Sep 03 '25 15:09

aybe


1 Answers

If you are implementing it in an FPGA it does matter. The maximum clocking frequency of the shift register is determined strongly by the maximum propagation delay of the circuit. Fibonacci LFSRs have to XOR several bits together requiring either cascaded 2-input XOR gates or multiple-input XOR gates, whereas Galois LFSRs use 2-input XOR gates, so their propagation delay is minimized, and can run at a faster frequency.

If you are using multiple bits at once, Fibonacci LFSRs have the advantage that the next N bits are immediately visible in the shift register, because all the shift register stages (except for the first one) get their input only from the previous stage.

like image 127
Jason S Avatar answered Sep 05 '25 14:09

Jason S