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?

# Generating Maximum Length Sequence using Galois LFSR

Started by ●July 4, 2009

Posted by ●July 4, 2009

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

Posted by ●July 4, 2009

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 beenloaded> into variable "taps," and that "lfsr" is the variable being used in the > � shift register computation, I am trying to generate the sequenceusing> code similar to that found on Wikipedia at thepagehttp://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 outputarray with L elements,> � � � � // what do I set it equalto 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 MLSsequence> 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

Posted by ●July 4, 2009

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

Posted by ●July 5, 2009

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

Posted by ●July 5, 2009

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.

Posted by ●July 5, 2009

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.) > > SteveYeah, it's kind of an interesting way of doing things.

Posted by ●July 5, 2009

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

Posted by ●July 5, 2009

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

Posted by ●July 5, 2009

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

Posted by ●July 9, 2009

On Jul 9, 9:31�am, robert bristow-johnson <r...@audioimagination.com> wrote:> On Jul 8, 10:23�am, Clay <c...@claysturner.com> wrote: > > > > > > > On Jul 8, 8:36�am, robert bristow-johnson<r...@audioimagination.com>> > wrote: > > > > On Jul 7, 2:08�pm, Clay <c...@claysturner.com> wrote: > > > > ... > > > > > 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. > > > > how does it work? �i cannot imagine it having a period of 2^mwithout> > > it having a state that is at least m bits wide. �does it stroll > > > through 19937 bits repeatedly? > > > Of course it has 19937 bits in memory - that is only 624 words (32 > > bits each). This may be an issue in a memory limited application, but > > on a general computer not a problem at all. It uses a basic shift > > register with feedback, but unlike common schemes, the feed back is > > "twisted." > > > The Wiki article may help describe it for you. The pseudo code is > > pretty simple to follow > > >http://en.wikipedia.org/wiki/Mersenne_twister > > so a pseudo-statement like: > > "int y := 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])" > > means that the 32nd bit of MT[i] remains in the 32nd place in y (the > MSB) and the lower 31 bits of (MT[(i+1) mod 624] go into the lower 31 > bits of y? �and does the multiplication in initializeGenerator() > involve a (long long) or (unsigned long long) type? > > it also appears that extractNumber() is essentially a table lookup > (with a pretty damn big table) in that it is only a function of MT > [index] and it does not affect the generation of MT[]. �is that bit > scrambling really necessary? �then, if it *is* necessary (the words > would not look random enough without the bit scrambling), the question > is, is it sufficient? > > just curious (and ignorant). > > r b-j- Hide quoted text - > > - Show quoted text -Hello Robert, 1st we note that 19937 bits is 623 complete 32 bit words plus 1 extra bit. Basically the MT does bit scrambling on each of the 623 words ontil which time you shift down (but not simple linear shifting) the whole 19937 bits. I would say that both of these stages are necessary to ensure the statistical properties. One of the problems with standard linear congruence modulo generators, was you could take pairs of numbers and then use one as an x value and the other as a y value and plot a spot at (x,y). With an LCM generator, the plotted spots would all appear on straight lines. So there was a strong sample to sample correlation. And a lot has been done to make scramblers to remove this correlation. The MT picks consecutive numbers from different points in the 623 word chain. So this removes the sample to sample correlation. Once you have made 623 picks, then a new 623 word chain is formed. Note the efficiency in this process, that the overall data chain "shifting" occures once every 623 calls! Common "C" implementations of the MT actually run faster than the system supplied rand() function. And yes unsigned 32 bit numbers are being used. In the authors' seminal paper on the MT, the paper's title alludes to the lack of sample to sample correlation for sets of up to 623 - 32 bit samples! IHTH, Clay

Posted by ●July 9, 2009

On Jul 8, 10:23=A0am, Clay <c...@claysturner.com> wrote:> On Jul 8, 8:36=A0am, robert bristow-johnson <r...@audioimagination.com> > wrote: > > > > > On Jul 7, 2:08=A0pm, Clay <c...@claysturner.com> wrote: > > > ... > > > > 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. > > > how does it work? =A0i cannot imagine it having a period of 2^m without > > it having a state that is at least m bits wide. =A0does it stroll > > through 19937 bits repeatedly? > > > Of course it has 19937 bits in memory - that is only 624 words (32 > bits each). This may be an issue in a memory limited application, but > on a general computer not a problem at all. It uses a basic shift > register with feedback, but unlike common schemes, the feed back is > "twisted." > > The Wiki article may help describe it for you. The pseudo code is > pretty simple to follow > > http://en.wikipedia.org/wiki/Mersenne_twisterso a pseudo-statement like: "int y :=3D 32nd bit of(MT[i]) + last 31 bits of(MT[(i+1) mod 624])" means that the 32nd bit of MT[i] remains in the 32nd place in y (the MSB) and the lower 31 bits of (MT[(i+1) mod 624] go into the lower 31 bits of y? and does the multiplication in initializeGenerator() involve a (long long) or (unsigned long long) type? it also appears that extractNumber() is essentially a table lookup (with a pretty damn big table) in that it is only a function of MT [index] and it does not affect the generation of MT[]. is that bit scrambling really necessary? then, if it *is* necessary (the words would not look random enough without the bit scrambling), the question is, is it sufficient? just curious (and ignorant). r b-j

Posted by ●July 8, 2009

On Jul 8, 8:36�am, robert bristow-johnson <r...@audioimagination.com> wrote:> On Jul 7, 2:08�pm, Clay <c...@claysturner.com> wrote: > > > > ... > > > 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. > > how does it work? �i cannot imagine it having a period of 2^m without > it having a state that is at least m bits wide. �does it stroll > through 19937 bits repeatedly? > > r b-jHello Robert, Of course it has 19937 bits in memory - that is only 624 words (32 bits each). This may be an issue in a memory limited application, but on a general computer not a problem at all. It uses a basic shift register with feedback, but unlike common schemes, the feed back is "twisted." The Wiki article may help describe it for you. The pseudo code is pretty simple to follow http://en.wikipedia.org/wiki/Mersenne_twister The paper "Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator" is the one where Makoto Matsumoto and Takuji Nishimura first describe the method. You may find the paper here: http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf Enjoy! Clay

Posted by ●July 8, 2009

On Jul 7, 2:08�pm, Clay <c...@claysturner.com> wrote:>...> > 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.how does it work? i cannot imagine it having a period of 2^m without it having a state that is at least m bits wide. does it stroll through 19937 bits repeatedly? r b-j

Posted by ●July 8, 2009

> > 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. > > ClayThanks Clay; that's a really neat algorithm! It's certainly something to think about when doing statistical tests. The large period is just amazing.

Posted by ●July 7, 2009

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

Posted by ●July 7, 2009

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

Posted by ●July 7, 2009

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

Posted by ●July 7, 2009

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

Posted by ●July 7, 2009

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 beenloaded> into variable "taps," and that "lfsr" is the variable being used in the > � shift register computation, I am trying to generate the sequenceusing> code similar to that found on Wikipedia at thepagehttp://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 outputarray with L elements,> � � � � // what do I set it equalto 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 MLSsequence> with a length of 4095 using the above code? �The loop should repeat4095> times. �What is the "output stream"? Is it simply the lowest bit inthe> 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