FPGA Central

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 page
http://en.wikipedia.org/wiki/Linear_...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?

Nicholas Kinar 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 page
> http://en.wikipedia.org/wiki/Linear_...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?
>
>
>

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

robert bristow-johnson <rbj@audioimagination.com> wrote:

>On Jul 4, 12:55*am, Nicholas Kinar <n.ki...@usask.ca> wrote:

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

Looks right to me. Read the code again.

Steve

robert bristow-johnson <rbj@audioimagination.com> wrote:

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

Here is the simplest one for m=12:

0x05eb

It is probably bit reversed from the OP's set-up,
The leadign coefficient of one is deleted from
this constant.

(Unlike the OP, I always put the LS term of the polynomial
in the lsb of a binary word, but after looking at OP's
code it seems more compact to do it his way.)

Steve

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.

Thanks, Steve!


> Here is the simplest one for m=12:
>
> 0x05eb
>
> It is probably bit reversed from the OP's set-up,
> The leadign coefficient of one is deleted from
> this constant.
>

Yes, it appears that the Galois shift register requires bit reversed
versions.


> (Unlike the OP, I always put the LS term of the polynomial
> in the lsb of a binary word, but after looking at OP's
> code it seems more compact to do it his way.)
>
> Steve

Yeah, it's kind of an interesting way of doing things.

Nicholas Kinar <n.kinar@usask.ca> wrote:

>Thanks, Steve!

No problemo.

>> Here is the simplest one for m=12:
>>
>> 0x05eb
>>
>> It is probably bit reversed from the OP's set-up,
>> The leading coefficient of one is deleted from
>> this constant.

>Yes, it appears that the Galois shift register requires bit reversed
>versions.

The way you're doing it, yes.

>> (Unlike the OP, I always put the LS term of the polynomial
>> in the lsb of a binary word, but after looking at OP's
>> code it seems more compact to do it his way.)

>Yeah, it's kind of an interesting way of doing things.

It's good to keep track of the algebra. For a generating
polynomial G of degree m over GF(2), you are computing the remainder

x^n mod G

for a series of values n=0, n=1,....

This remainder is a polynomial over GF(2) of (at most) degree m-1.
How you represent it in a bit field is totally up to you,
and your method is as correct as any.

Steve

On Jul 4, 8:02 pm, spop...@speedymail.org (Steve Pope) wrote:
> robert bristow-johnson <r...@audioimagination.com> wrote:
>
> >On Jul 4, 12:55 am, Nicholas Kinar <n.ki...@usask.ca> wrote:
> >> 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.
>
> Looks right to me. Read the code again.

yeah, you're right. the code is correct. i almost went and changed
it at Wikipedia, but thought better.



On Jul 5, 10:26 am, Nicholas Kinar <n.ki...@usask.ca> wrote:
>
>
> > 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

i forgot to mention that to get a virtually zero-mean MLS signal for
the purposes of measuring impulse response (or just for some noise
that is guaranteed to be "white" in some sense of the word), then you
take that bit, (we'll call it a[n] where n is discrete time) which is
0 or 1 and create this signed MLS signal:

x[n] = (-1)^a[n]

so, it's nearly zero mean. there are L/2 ones and L/2-1 zeros in a[n]
(because the zero state in the shift register is the only state
missing and if it were included, there would be an equal L/2 ones and
zeros, but it's not). then there is one more -1 than +1 in x[n] over
L samples. the mean is -1/L

this way, when you autocorrelate, you get


Rx[k] = MEAN{ x[n] * x[n+k] }

( "*" means simple multiplication.)

which is

Rx[k] = MEAN{ (-1)^a[n] * (-1)^a[n+k] }

= MEAN{ (-1)^(a[n] + a[n+k]) }

which happens to be the same as

Rx[k] = MEAN{ (-1)^(a[n] XOR a[n+k]) }


now it turns out that if you take that periodic MLS bit sequence, copy
it, circularly rotate one of the copies by k samples, and XOR the two
MLSes together, it turns out that you can show that the same recursive
generating algorithm that produces the MLS also governs that XOR
product of two with a lag in between. except, we know for MLS, the
zero state gets mapped back to the zero state. for an MLS, those are
the two loops; zero goes straight to zero, but any non-zero state of
the shift register goes through the whole MLS, which are all the other
non-zero states, before it gets back to your original non-zero state.
so that MEAN above for k not a multiple of L (nor zero), is -1/L. but
the mean for k=0 or any other integer multiple of L is the mean of a
sequence of ones.


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

right, and you will see m+1 "coefficients" (that are either 0 or 1) in
the primitive polynomial. but the two end bits are always 1 and the
bit-reverse sequence can be shown to also be a primitive polynomial.
so, depending on which direction you're shifting, you leave off one of
the bits. you were shifting right so the "1" bit in the left is kept,
and you use the m most-significant bits on your word "taps" (right
justified).


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

it's similar to a recent experience i had where i missed that the
simplest and obvious way to display the step response of a filter (IIR
or FIR), assuming you know the coefficients, is to simple bang a step
input to a simulated filter with the same coefficients. somebody at
music-dsp had to point that out to me, where i was thinking of doing
Heaviside partial fraction expansion of the transfer function times 1/
(z-1), inverse Z transform, and getting it from there.


> Thanks, Robert.

FWIW

BTW, if you Google "Maximum Length Sequence" and look at the link
right below the one you referred to, there is a Little MLS Tutorial
that explains the math behind most of this. it doesn't derive
primitive polynomials, but does prove how MLS can get your time-
aliased impulse response from where you can get your frequency
response.



--

r b-j rbj@audioimagination.com

"Imagination is more important than knowledge."

robert bristow-johnson <rbj@audioimagination.com> wrote:

>yeah, you're right. the code is correct. i almost went and changed
>it at Wikipedia, but thought better.

It's a pretty weak Wikipedia page. It does not mention, for
example, that one is calculating a remainder. I do not
know anyone who uses the terminology Fibonacci LFSR,
and the polynomial in the "Fibonacci" section is reversed
from any normal usage. There is no mathematical difference
between the sequences described in the "Fibonacci" and
"Galois" sections of this article. The article refers
to the "conventional LFSR" as though it is something different
than the "Galois" one, which it calls "alternate".

Maybe I will input a complaint on the talk page.

Steve

I wrote,

[Wikipedia page on LFSR]

> It does not mention, for example, that one is calculating
> a remainder. I do not know anyone who uses the terminology
> Fibonacci LFSR, and the polynomial in the "Fibonacci" section
> is reversed from any normal usage.

A little more investigation and I have found other references
to the Fibonacci vs. Galois terminology distinction, including
in one paper by professor David Wagner at U.C. Berkeley.
So I guess it's a real bit of terminology.

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.

Steve

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

dvsarwate@yahoo.com <dvsarwate@gmail.com> 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

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

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

Yes, in a Galois LFSR, the m-tuple represents a field element
in the standard polynomial basis. If the initial loading of the
LFSR is 100....0 or 00....1 (depending on whether you are a
big-endian or a little-endian) representing the field element 1
(multiplicative identity), then successive m-tuple contents of
the Galois LFSR are alpha, alpha^2, alpha^3, .... or, for those
who dislike the Greek alphabet, x, x^2, x^3, etc, all modulo
the characteristic polynomial. The contents of the Fibonacci
LFSR are also the same sequence of increasing powers of
alpha, but the field elements are represented in the dual basis
of the standard polynomial basis. For further details, read
the thread from 7 years ago that has been cited earlier.

--Dilip Sarwate

> It's good to keep track of the algebra. For a generating
> polynomial G of degree m over GF(2), you are computing the remainder
>
> x^n mod G
>
> for a series of values n=0, n=1,....
>
> This remainder is a polynomial over GF(2) of (at most) degree m-1.
> How you represent it in a bit field is totally up to you,
> and your method is as correct as any.
>
> Steve

In my C++ implementation, I use an std::vector<bool>v to keep track of
the zeros and the ones, so I can simply generate an MLS without having
to worry about bit-shifting a uint32_t or uint16_t or similar variable.
To do the rotation, I simply pop a bit off the back of the vector, do
the XOR with the taps, and then insert the resulting bit at the front of
the vector. It works quite well, but for embedded hardware, it might be
a little bit too slow for a quick implementation.


Nicholas

> i forgot to mention that to get a virtually zero-mean MLS signal for
> the purposes of measuring impulse response (or just for some noise
> that is guaranteed to be "white" in some sense of the word), then you
> take that bit, (we'll call it a[n] where n is discrete time) which is
> 0 or 1 and create this signed MLS signal:
>
> x[n] = (-1)^a[n]
>
> so, it's nearly zero mean. there are L/2 ones and L/2-1 zeros in a[n]
> (because the zero state in the shift register is the only state
> missing and if it were included, there would be an equal L/2 ones and
> zeros, but it's not). then there is one more -1 than +1 in x[n] over
> L samples. the mean is -1/L
>
> this way, when you autocorrelate, you get
>
>
> Rx[k] = MEAN{ x[n] * x[n+k] }
>
> ( "*" means simple multiplication.)
>
> which is
>
> Rx[k] = MEAN{ (-1)^a[n] * (-1)^a[n+k] }
>
> = MEAN{ (-1)^(a[n] + a[n+k]) }
>
> which happens to be the same as
>
> Rx[k] = MEAN{ (-1)^(a[n] XOR a[n+k]) }
>
>
> now it turns out that if you take that periodic MLS bit sequence, copy
> it, circularly rotate one of the copies by k samples, and XOR the two
> MLSes together, it turns out that you can show that the same recursive
> generating algorithm that produces the MLS also governs that XOR
> product of two with a lag in between. except, we know for MLS, the
> zero state gets mapped back to the zero state. for an MLS, those are
> the two loops; zero goes straight to zero, but any non-zero state of
> the shift register goes through the whole MLS, which are all the other
> non-zero states, before it gets back to your original non-zero state.
> so that MEAN above for k not a multiple of L (nor zero), is -1/L. but
> the mean for k=0 or any other integer multiple of L is the mean of a
> sequence of ones.
>
>

Thanks, Robert! I had read before that the binary sequence is converted
to -1 and +1, but this really explains why it is beneficial to do this
operation.


> it's similar to a recent experience i had where i missed that the
> simplest and obvious way to display the step response of a filter (IIR
> or FIR), assuming you know the coefficients, is to simple bang a step
> input to a simulated filter with the same coefficients. somebody at
> music-dsp had to point that out to me, where i was thinking of doing
> Heaviside partial fraction expansion of the transfer function times 1/
> (z-1), inverse Z transform, and getting it from there.
>

Ah - what a good idea!


>
> BTW, if you Google "Maximum Length Sequence" and look at the link
> right below the one you referred to, there is a Little MLS Tutorial
> that explains the math behind most of this. it doesn't derive
> primitive polynomials, but does prove how MLS can get your time-
> aliased impulse response from where you can get your frequency
> response.
>

There are a lot of good links on the web, and these do a terrific job of
quickly informing the reader. For more in-depth stuff concerning the
mathematics, it is probably best to turn to a book such as the one by
Golomb, which is infused with proofs.

Nicholas

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

Great thread; thanks Dilip!

dvsarwate@yahoo.com <dvsarwate@gmail.com> wrote:

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

[Fibonacci LFSR]

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

>Yes, in a Galois LFSR, the m-tuple represents a field element
>in the standard polynomial basis. If the initial loading of the
>LFSR is 100....0 or 00....1 (depending on whether you are a
>big-endian or a little-endian) representing the field element 1
>(multiplicative identity), then successive m-tuple contents of
>the Galois LFSR are alpha, alpha^2, alpha^3, .... or, for those
>who dislike the Greek alphabet, x, x^2, x^3, etc, all modulo
>the characteristic polynomial. The contents of the Fibonacci
>LFSR are also the same sequence of increasing powers of
>alpha, but the field elements are represented in the dual basis
>of the standard polynomial basis. For further details, read
>the thread from 7 years ago that has been cited earlier.

Thanks. I read through the cited thread.

I assume this is perhaps the same dual basis that Berlekamp used
to develop his bit-serial RS encoder.

I am still curious about the origin and dissemination of the
"Fibonacci LFSR" vs. "Galois LFSR" terminology -- there isn't
anything less "Galois" about the Fibonacci version; it uses a
different basis, sure, but the register contents are still Galois
field elements. So I see it as a confusing choice of terms for
this distinction.

Unless this terminology is really and truly ingrained,
I'd advocate spiking it.

Just my opinion of course.

Steve

Nicholas Kinar <n.kinar@usask.ca> replies to my post,

>> It's good to keep track of the algebra. For a generating
>> polynomial G of degree m over GF(2), you are computing the remainder
>>
>> x^n mod G
>>
>> for a series of values n=0, n=1,....
>>
>> This remainder is a polynomial over GF(2) of (at most) degree m-1.
>> How you represent it in a bit field is totally up to you,
>> and your method is as correct as any.
>>
>> Steve

>In my C++ implementation, I use an std::vector<bool>v to keep track of
>the zeros and the ones, so I can simply generate an MLS without having
>to worry about bit-shifting a uint32_t or uint16_t or similar variable.
> To do the rotation, I simply pop a bit off the back of the vector, do
>the XOR with the taps, and then insert the resulting bit at the front of
>the vector. It works quite well, but for embedded hardware, it might be
>a little bit too slow for a quick implementation.

Methods on std::vector<bool> are notorious for being slow,
since this object has packed the boolean bits into chars,
to save memory space.

Steve

Steve Pope wrote:
> Nicholas Kinar <n.kinar@usask.ca> replies to my post,
>
>>> It's good to keep track of the algebra. For a generating
>>> polynomial G of degree m over GF(2), you are computing the remainder
>>>
>>> x^n mod G
>>>
>>> for a series of values n=0, n=1,....
>>>
>>> This remainder is a polynomial over GF(2) of (at most) degree m-1.
>>> How you represent it in a bit field is totally up to you,
>>> and your method is as correct as any.
>>>
>>> Steve
>
>> In my C++ implementation, I use an std::vector<bool>v to keep track of
>> the zeros and the ones, so I can simply generate an MLS without having
>> to worry about bit-shifting a uint32_t or uint16_t or similar variable.
>> To do the rotation, I simply pop a bit off the back of the vector, do
>> the XOR with the taps, and then insert the resulting bit at the front of
>> the vector. It works quite well, but for embedded hardware, it might be
>> a little bit too slow for a quick implementation.
>
> Methods on std::vector<bool> are notorious for being slow,
> since this object has packed the boolean bits into chars,
> to save memory space.
>
> Steve

If only 'C' bit fields had had *DEFINED* behavior....

*Sigh*.

--
Les Cargill

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

Clay <clay@claysturner.com> wrote:

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

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

Turns out that engineering requirements come in all forms
and sometimes you do not want, or cannot use, the more
elaborate solution.

For example, with a maximal-length sequence formed from a
polynomial over GF(2), it's often practical to jump to
a prescribed point in the middle of the sequence, or to
examine the register contents and figure out where you
are in the sequence. Can a Mersenne twister do that?

Steve

On Jul 7, 2:53*pm, spop...@speedymail.org (Steve Pope) wrote:
> Clay *<c...@claysturner.com> wrote:
> >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).
> >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.
>
> Turns out that engineering requirements come in all forms
> and sometimes you do not want, or cannot use, the more
> elaborate solution.
>
> For example, with a maximal-length sequence formed from a
> polynomial over GF(2), it's often practical to jump to
> a prescribed point in the middle of the sequence, or to
> examine the register contents and figure out where you
> are in the sequence. *Can a Mersenne twister do that?
>
> Steve

Hello Steve,

Yes you can start the twister anywhere you want in the sequence.
Likewise a small number (compared to the length) of observations can
tell you the starting state. It is not for cryptographic use because
of these properties. I'm not sure how one would measure the distance a
current state is away from a defined starting state without clocking
it through all of the intervening states. Here its long period makes
it take a while!

Clay

Clay <clay@claysturner.com> wrote:

>On Jul 7, 2:53*pm, spop...@speedymail.org (Steve Pope) wrote:

>> For example, with a maximal-length sequence formed from a
>> polynomial over GF(2), it's often practical to jump to
>> a prescribed point in the middle of the sequence, or to
>> examine the register contents and figure out where you
>> are in the sequence. *Can a Mersenne twister do that?

>Yes you can start the twister anywhere you want in the sequence.
>Likewise a small number (compared to the length) of observations can
>tell you the starting state. It is not for cryptographic use because
>of these properties. I'm not sure how one would measure the distance a
>current state is away from a defined starting state without clocking
>it through all of the intervening states. Here its long period makes
>it take a while!

Thanks.

I've never used the Twister acutally. If I need something
stronger or more random than an LFSR I usually go with DES or AES, or
something derived from them.

Steve

On Jul 7, 3:42*pm, spop...@speedymail.org (Steve Pope) wrote:
> Clay *<c...@claysturner.com> wrote:
> >On Jul 7, 2:53*pm, spop...@speedymail.org (Steve Pope) wrote:
> >> For example, with a maximal-length sequence formed from a
> >> polynomial over GF(2), it's often practical to jump to
> >> a prescribed point in the middle of the sequence, or to
> >> examine the register contents and figure out where you
> >> are in the sequence. *Can a Mersenne twister do that?
> >Yes you can start the twister anywhere you want in the sequence.
> >Likewise a small number (compared to the length) of observations can
> >tell you the starting state. It is not for cryptographic use because
> >of these properties. I'm not sure how one would measure the distance a
> >current state is away from a defined starting state without clocking
> >it through all of the intervening states. Here its long period makes
> >it take a while!
>
> Thanks.
>
> I've never used the Twister acutally. *If I need something
> stronger or more random than an LFSR I usually go with DES or AES, or
> something derived from them. *
>
> Steve

I use it quite a bit. It works very well as a random number generator
for games. Also I use it for all sorts of monte carlo testing. It is
even good for monte carlo integration.

Clay