LFSR: Galois and Fibonacci

Chris Ward

unread,

Feb 7, 2003, 11:46:28 AM2/7/03

to

I am correct in thinking Galois and Fibonacci LFSRs are mathematically
equivalent?

If I have a generator polynomial and I implement the two architectures
do I need to do anything different to obtain the same sequences from
the two?

Thanks
Chris

Bob Perlman

unread,

Feb 7, 2003, 1:37:00 PM2/7/03

to

Hi -

On 7 Feb 2003 08:46:28 -0800, chris....@ntlworld.com (Chris Ward)
wrote:

A Google search for "Fibonacci LFSR" returns the following link:

http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm

There's a very nice explanation of Fibonacci and Galois LFSRs that
seems to answer your question.

I'm continually amazed at how useful Google is.

Bob Perlman
Cambrian Design Works

Allan Herriman

unread,

Feb 9, 2003, 1:49:30 AM2/9/03

to

On Fri, 07 Feb 2003 18:37:00 GMT, Bob Perlman
<bobsre...@hotmail.com> wrote:

>Hi -
>
>On 7 Feb 2003 08:46:28 -0800, chris....@ntlworld.com (Chris Ward)
>wrote:
>
>>I am correct in thinking Galois and Fibonacci LFSRs are mathematically
>>equivalent?
>>
>>If I have a generator polynomial and I implement the two architectures
>>do I need to do anything different to obtain the same sequences from
>>the two?
>>
>>Thanks
>>Chris
>
>A Google search for "Fibonacci LFSR" returns the following link:
>
>http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm
>
>There's a very nice explanation of Fibonacci and Galois LFSRs that
>seems to answer your question.

The program that you can download from this page:
http://www.logiccell.com/~jean/LFSR/
also shows the equivalence between the two forms of LFSR.

Regards,
Allan.

Chris Ward

unread,

Feb 10, 2003, 4:21:30 AM2/10/03

to

I've been searching around google and had not found a link to somewhere that
described how to translate the polynomial from one architecture to another,
not sure how I missed it.

That link's just what I was looking for though.

Thanks.

Chris.

"Allan Herriman" <allan_herrim...@agilent.com> wrote in message
news:lcub4vs3qagb47gdn...@4ax.com...

Chris Ward

unread,

Feb 17, 2003, 10:11:21 AM2/17/03

to

Thanks for the link but I'm still having some problems.

Specifically I have two questions:

(1) Can I use a Fibonacci architecture to yield an equivalent
output/register state to my Galois architecture?

(2) If I translate the polynomial (as per the link posted previously)
what translation must I apply to the initial state of the register?

A lot of the information I can find seems to avoid these questions.

Thanks,
Chris.

Allan Herriman

unread,

Feb 17, 2003, 11:08:33 PM2/17/03

to

On 17 Feb 2003 07:11:21 -0800, chris....@ntlworld.com (Chris Ward)
wrote:

>Thanks for the link but I'm still having some problems.

>
>Specifically I have two questions:
>
>(1) Can I use a Fibonacci architecture to yield an equivalent
>output/register state to my Galois architecture?

Yes. The state of the registers will be related by a linear function
(where a "linear function" is a sea of XOR gates).
For a polynomial of width N bits, you will need roughly N N/2 input
XOR gates (IIRC). You can work out how many LUT4s (or whatever gates
you are using) that is.

>(2) If I translate the polynomial (as per the link posted previously)
>what translation must I apply to the initial state of the register?

See above. Working out the exact function is left as an exercise for
the reader (which is another way of saying I don't know right now).
But if it's a small polynomial (say, 16 bits or less) then it's easy
enough to use a brute force method in software to create a big lookup
table to do the translation.

But since both the Fibbonacci and Galois versions produce the same
sequence, you could encode the difference as an integer that
represents the number of times you would need to iterate the
Fibbonacci FSM to get it to the same point in the sequence as the
Galois one, given the same starting state.
This would take more time, but less hardware than the previous method.

>A lot of the information I can find seems to avoid these questions.

Probably because it's not something that's done that often. Why are
you interested in the exact start value? We use LFSRs for a lot of
things (BERT, etc.) but we usually don't care about the start value.

Regards,
Allan.

Chris Ward

unread,

Feb 18, 2003, 6:47:40 AM2/18/03

to

Allan,

The application is for a CRC calculation engine.

I have an existing Galois design which I would like to implement using
a Fibonacci architecture. (If you're interested, I'm doing this
because I am experimenting with moving the design into a DSP which
provides for Fibonacci LFSRs within its instruction set.)

Specifically, I need to determine:

(1) the poly
(2) the start state for the Fibonacci design
(3) the linear function to transfrom the final state to that
of the Galois (to yield the CRC).

However, I am beginning think that I may not be able to do this for
two reasons:

(I) In the non-autonomous LFSRs, mapping the input bit
'connection' of one architecture to the other requires a
non-singular 'connection' (I think)

(II) the need to apply a linear function to translate the final
state could require a fairly large LUT.

Chris.