[email protected] <[email protected]> wrote:

>On Jul 6, 12:15*am, spop...@speedymail.org (Steve Pope) wrote:

>> In Golomb, _Shift Register Sequences_, Chapter 3 Section 2.8,
>> there is a discussion of how the polynomial P = 1 - x - x^2
>> generates a Fibonacci sequence (e.g., 1/P is an infinite
>> polynomial with Fibonacci numbers as coefficients). *But
>> in a field of characteristic 2 this reduces to a sequence
>> of length three (every third Fibonacci number is even, the
>> others odd). * So I do not immediately see how this leads to
>> the above Fibonacci nomenclature.

>The Fibonacci numbers (or Fibonacci numbers)
>are generated by a linear recurrence:

>F_{n} = F_{n-1} + F_{n-2}

>whose characteristic polynomial is 1 - x - x^2, and
>so LFSRs whose m-bit *contents* are successive
>overlapping m-tuples from a binary sequence are
>called Fibonacci LFSRs even though the recurrence
>is of degree m instead of 2 and over GF(2) (or over
>GF(q) in general) instead of the integers.

Thanks.

(Is it not still true that each m-tuple represents a field element,
in some basis?)

>As Steve
>has noted several times in this thread (and as is also
>noted in the much-denigrated Wikipedia entry (to which
>I have not contributed anything, by the way, and so
>I have no axe to grind here)), Galois LFSRs generate
>the *same* sequences as Fibonacci LFSRS (output
>= contents of latch at the output end of the register).
>However, generally speaking, the *register contents*
>of the Galois LFSR are different from those of the
>Fibonacci LFSR at any time, even when their output
>bits are the same *sequence*.

So I'll retract my negative rambling about the Wiki page,
given that the above terminology seems semi-widespread.
I just had not encountered it in texts such as Golomb, Berlekamp,
McEliece, or internally on any projects. Obviously there's
a subset of the community using this lingo. I still think
the "Galois LFSR" discussion could be made... much more clear
if the concept of dividing polynomials was covered.

>All the code snippets posted simulate Galois LFSRs.
>Simulation of a Fibonacci LFSR is not quite so easy
>to program in C since one needs to know if there are
>an even number or odd number of 1s in certain
>specific locations in a word. The bits are easily
>extracted via an AND operation with a mask but
>determining if an odd number of those happen to be
>1 is more problematic. (The information *is* usually
>available as the parity bit of the masked word at
>the assembly or machine language level; can it be used
>in C?)

The answer to the last question is no -- C gives no access
to parity bits, overflow bits and the like, at least not
natively as part of the language. Perhaps they can
generate a signal or exception in some systems but one
should not use exceptions just to construct logic. (IMO)

>If you really want the gory details of the relationship
>between Galois LFSRs and Fibonacci LFSRs [..]
>(http://groups.google.com/group/sci.m...thread/thread/
>28df95bf019230c7/35b22eae280a7368?lnk=gst&q=Sarwate
>+Yates#35b22eae280a7368)

Thanks

Steve