Generating multi-bit pseudo random sequence
in [DSP]
|
Prev: dsp engineer salary
Next: lms implementation: need help
From: gretzteam on 10 May 2010 08:14 Hi, Say I use a 16-bit LFSR set up to generate a maximum length pseudo-random sequence. According to property (3) here: 'The modulo-2 sum of an m-sequence and another phase of the same sequence yields yet a third phase of the sequence'. Does this mean that I can generate say 4 different phase of the sequence, concatenate them, and this becomes a 4-bit wide pseudo random sequence? Are there any rules to follow about the phase difference of each sequence? Thanks!
From: Vladimir Vassilevsky on 10 May 2010 08:49 gretzteam wrote: > Hi, > Say I use a 16-bit LFSR set up to generate a maximum length pseudo-random > sequence. According to property (3) here: > > 'The modulo-2 sum of an m-sequence and another phase of the same sequence > yields yet a third phase of the sequence'. > > Does this mean that I can generate say 4 different phase of the sequence, > concatenate them, and this becomes a 4-bit wide pseudo random sequence? Do you mean M-sequence in GF(2^4) ? Then not. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
From: gretzteam on 10 May 2010 16:00 >gretzteam wrote: >> Hi, >> Say I use a 16-bit LFSR set up to generate a maximum length pseudo-random >> sequence. According to property (3) here: >> >> 'The modulo-2 sum of an m-sequence and another phase of the same sequence >> yields yet a third phase of the sequence'. >> >> Does this mean that I can generate say 4 different phase of the sequence, >> concatenate them, and this becomes a 4-bit wide pseudo random sequence? > >Do you mean M-sequence in GF(2^4) ? Then not. So what is the length of the new sequence? Does it depends on the chosen phase of the original m-sequence? Ask another way, how does one generate a 4-bit wide random sequence of length M? Thanks
From: glen herrmannsfeldt on 10 May 2010 17:07 gretzteam <gretzteam(a)n_o_s_p_a_m.yahoo.com> wrote: > Say I use a 16-bit LFSR set up to generate a maximum length pseudo-random > sequence. According to property (3) here: > 'The modulo-2 sum of an m-sequence and another phase of the same sequence > yields yet a third phase of the sequence'. > Does this mean that I can generate say 4 different phase of the sequence, > concatenate them, and this becomes a 4-bit wide pseudo random sequence? Are > there any rules to follow about the phase difference of each sequence? As you don't say what you want to use the results for, it is hard to say. To start, 16 bits is a little short for many uses, but maybe enough for some. Likely not enough for cryptographic applications, but maybe enough for a simulated dice game. Using phases the way you suggest will result in some possible correlations in the sequences, as will using four bits of the LFSR itself. Better would be four LFSR with mutually relatively prime periods, but it might be that you don't need that much randomness. Though four phases of a 64 bit generator is probably about as good as four different 16 bit generators. -- glen
From: gretzteam on 10 May 2010 18:03
>As you don't say what you want to use the results for, it is >hard to say. > >To start, 16 bits is a little short for many uses, but maybe >enough for some. Likely not enough for cryptographic applications, >but maybe enough for a simulated dice game. Using phases the way >you suggest will result in some possible correlations in the >sequences, as will using four bits of the LFSR itself. > >Better would be four LFSR with mutually relatively prime periods, >but it might be that you don't need that much randomness. > >Though four phases of a 64 bit generator is probably about >as good as four different 16 bit generators. > >-- glen Ok I see what you mean...my application is far from cryptography! I'm trying to dither the phase of a DDS. The NCO is 24 bits, and gets quantized to 10 bits going in the ROM. From my simulations, I need about 4 bits of dither to make the spurs go away. Thanks. |