don't mind Vlad. he's sorta mean. at least with inferiors (i'm sure
glad i don't work for him).

On Jul 4, 12:55*am, Nicholas Kinar <n.ki...@usask.ca> wrote:
>
> 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);

i dunno what the minus sign is for. i don't think it belongs there.
normally, if the shift register state is zero (all zero bits), the
shift and conditional XOR operation should return you to the same zero
state. if it's an MLS, that zero state is the *only* state not in the
MLS. i.e. if it's an MLS *any* non-zero state is an acceptable
initial state and *all* other non-zero states will occur before you
get back to your original non-zero state.

> * * * * // if I have an output array with L elements,
> * * * * // what do I set it equal to in this loop?
> * * * * // output[i] = ??
>
> }
>

your L "elements" are single bits. the "S" of MLS is a sequence of
*bits*, not of words.

> However, how do I determine the output of the LFSR?

pick any bit of the shift register (your "lfsr") and use it. i
usually pick the same bit that falls off the edge

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

you need to select your taps word correctly. first of all, for m=12,
then taps > 2048, but there is more to it. somewhere on the web,
there is a resource of "primitive polynomials". find that and use one
of them (ignore the least significant bit, which is always 1, the
other m bits of the primitive polynomial are the m bits of your taps
word). for m=12, you could write a program that guesses at a 12-bit
word, try it out (see if it goes through all 2^12 - 1 non-zero
states), and if it fails, try another word for taps.

> *The loop should repeat [after] 4095 times.

yes. that's how you confirm it's MLS. start with a state of 0x0001
and count how many iterations it takes to get back to 0x0001. if it's
4095 and your "taps" word has zeros in the bits other than the least-
significant 12 bits, then it's an MLS

> *What is the "output stream"? Is it simply the lowest bit in the
> sequence?

sure. any bit will do.

> *Is this the bit that is fed back into the sequence after
> passing through the logic gates?

it's the bit that triggers the XOR operation in your code, so in that
way, it feeds back.

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

**** if i know.

r b-j