On Jul 4, 12:55*am, Nicholas Kinar <n.ki...@usask.ca> wrote:
> Hello--
>
> I am trying to generate a Maximum Length Sequence (MLS) using a Linear
> Feedback Shift Register (LFSR). *Assuming that the taps have been loaded
> into variable "taps," and that "lfsr" is the variable being used in the
> * shift register computation, I am trying to generate the sequence using
> code similar to that found on Wikipedia at the pagehttp://en.wikipedia.org/wiki/Linear_feedback_shift_register. *Here is a
> code snippet:
>
> // generate sequence
> for(int i = 0; i < L; i++)
> {
> * * * * lfsr = (lfsr >> 1) ^ (-(lfsr & 1u) & taps);
>
> * * * * // if I have an output array with L elements,
> * * * * // what do I set it equal to in this loop?
> * * * * // output[i] = ??
>
> }
>
> However, how do I determine the output of the LFSR? *For m = 12, it
> follows that L = (2^m) - 1 = 4095. *How would I generate an MLS sequence
> with a length of 4095 using the above code? *The loop should repeat 4095
> times. *What is the "output stream"? Is it simply the lowest bit in the
> sequence? *Is this the bit that is fed back into the sequence after
> passing through the logic gates?
>
> Is there a way to test if my output is an MLS? *Does the Galois LFSR
> generate exactly the same output as a Fibonacci LFSR?

Hello Nicholas,

When I think about generating a MAXIMUM length sequence, I woudn't
even consider something so short as just 4095 states before repeating.
I often use a Mersenne Twister, which has a period of 2^19937. Yes
that's correct. And it is easy to implement and free code exist on the
web for it. The inventor (Makoto Matsumoto ) put it (code and
algorithm) into the public domain, so you are free to use it without
worry about IP issues. And statistically, the Twister's output fairs
better on statistics tests than stuff from a simple loopback of a
shift register with some exclusive ors. You may want to look into
this.

Clay