Hi Robert--

Thank you for your reply! The code that I found on Wikipedia was
different enough to make me wonder exactly what was happening. There's
additional reference code for MLS sequence generation that can be found
here:

http://libmls0.sourceforge.net/



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



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


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


There are a few resources on "primitive polynomials" currently on the
web, but perhaps you are thinking about the following paper?

Stahnke, W. 1973. "Primitive Binary Polynomials," Mathematics of
Computation 27(124): 977-980.

The paper gives a table of exponents of terms of primitive binary
polynomial terms up to m = 168, where the length of the sequence is L =
(2^m) - 1. I've tested this table up to m = 30, and it seems to
generate an MLS.


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


You know, that's an interesting way of checking whether something is 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?
>


Perhaps a quick test of whether the sequence is an MLS could be found here:

http://www.libinst.com/mlsmeas.htm


A shifted version of the sequence is simply lined up and multiplied.
There's probably also a theoretical way of proof regarding whether
something is an MLS, but that can be left to the mathematicians. It
just makes me wonder how you would test your own code.

Thanks, Robert.