Sign in

Not a member? | Forgot your Password?

Search compdsp

Search tips


Free PDF Downloads

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

C++ Tutorial

Discussion Groups

FIR Filter Design Software

Free Online Books

See Also

Embedded SystemsFPGA

Discussion Groups | Comp.DSP | Generating Maximum Length Sequence using Galois LFSR

There are 30 messages in this thread.

You are currently looking at messages 1 to .


Is this discussion worth a thumbs up?

0

Generating Maximum Length Sequence using Galois LFSR - Nicholas Kinar - 2009-07-04 00:55:00

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

_____________________________
 Free pdf download: Complex Digital Signal Processing in Telecommunications.


STUPIDENT::Re: Generating Maximum Length Sequence using Galois LFSR - Vladimir Vassilevsky - 2009-07-04 12:12:00

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

_____________________________
 Free pdf download: Digital Signal Processor Fundamentals and System Design.


Re: Generating Maximum Length Sequence using Galois LFSR - robert bristow-johnson - 2009-07-04 19:59:00

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?

fuck if i know.

r b-j

_____________________________
 Free pdf download: Digital Signal Processing Maths.


Re: Generating Maximum Length Sequence using Galois LFSR - Steve Pope - 2009-07-04 20:02:00

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.

Steve

_____________________________
 Free pdf download: Digital Signal Processor Fundamentals and System Design.


Re: Generating Maximum Length Sequence using Galois LFSR - Steve Pope - 2009-07-05 02:55:00

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

>you need to select your taps word correctly.  first of all, for m,
>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, 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:

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

_____________________________
 Free pdf download: Digital Signal Processing Maths.


Re: Generating Maximum Length Sequence using Galois LFSR - Nicholas Kinar - 2009-07-05 10:26:00

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

_____________________________
 Free pdf download: Complex Digital Signal Processing in Telecommunications.


Re: Generating Maximum Length Sequence using Galois LFSR - Nicholas Kinar - 2009-07-05 10:31:00

Thanks, Steve!


> Here is the simplest one for m:
> 
> 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.

_____________________________
 Free pdf download: Complex Digital Signal Processing in Telecommunications.


Re: Generating Maximum Length Sequence using Galois LFSR - Steve Pope - 2009-07-05 16:18:00

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

>Thanks, Steve!

No problemo.

>> Here is the simplest one for m:
>> 
>> 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

_____________________________
 Free pdf download: Digital Signal Processor Fundamentals and System Design.


Re: Generating Maximum Length Sequence using Galois LFSR - robert bristow-johnson - 2009-07-05 17:16:00

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,
> > 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, 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                  r...@audioimagination.com

"Imagination is more important than knowledge."

_____________________________
 Free pdf download: Digital Signal Processing Maths.


Re: Generating Maximum Length Sequence using Galois LFSR - Steve Pope - 2009-07-05 17:40:00

robert bristow-johnson  <r...@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

_____________________________
 Free pdf download: Digital Signal Processing Maths.


| 1 | | 3 |