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. 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*.

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?)

If you really want the gory details of the relationship
between Galois LFSRs and Fibonacci LFSRs, see a
thread in this newsgroup in March 2002 titled Pseudo
Random Binary Sequences. Google Groups finds it
in sci.math for some reason

(http://groups.google.com/group/sci.m...thread/thread/
28df95bf019230c7/35b22eae280a7368?lnk=gst&q=Sarwate
+Yates#35b22eae280a7368)

(I searched for "Sarwate Yates" in comp.dsp on Google
Groups), but all the participants are the usual suspects
from comp.dsp: Jerry Avins, Eric Jacobsen, Robert
Bristow-Johnson, Randy Yates, Raymond Toy, Ray
Andraka, etc., and not forgetting, yours truly,

Hope this helps

--Dilip Sarwate