On 2008-07-03, Jerry Avins <jya@ieee.org> wrote:> > The best implementation will will use 24 separate random-bit generators...of different lengths and/or taps! Hate to see the OP make 24 identical LFSRs...> Truncating bits reduces the sequence repeat length in a non-obvious way.Even if he retains the full length in the register? A subset of m bits of an n-bit max-len LFSR repeats more frequently than every 2^n-1? -- Ben Jackson AD7GD <ben@ben.com> http://www.ben.com/
white noise generation
Started by ●July 3, 2008
Reply by ●July 3, 20082008-07-03
Reply by ●July 4, 20082008-07-04
The xorshift generator I'm using has three xor operations and three shift
operations; which, if I understand correctly, are supposed to work together
to create a 32-bit random number.
Here is the code (I'm doing an asm version of this):
unsigned long xor(){
static unsigned long y=2463534242; //seed
yˆ=(y<<13); y^=(y>>17); return (yˆ=(y<<5)); }
When you refer to the xorshift method only producing one random bit at a
time, are you referring to the output of a *single* xorshift operation?
Thanks for the help so far, everyone. I'd probably get more out of it if
I knew the first thing about probability and/or statistics.
Another question: If I'm measuring the power spectrum, how "flat" should
my spectrum look at any given time? I know it should be flat on average,
but would I have to sample over the entire period of the RNG output to see
a *truly* flat spectrum??
I guess a little context would help: Ultimately, I want to create a *very
rudimentary* room eq. (I say that because I only have an octave-band
graphic eq to work with - yes, ugh!) I already have algorithms to split
the mic input into octave bands and to measure the power in the bands. I
assume I have to average the power results in each band over a period of
time? I also have a pinking filter that I got from this group somewhere..
it produces a very accurate -3dB per octave. So, if I can just get some
decent white noise I *should* be in business!
Reply by ●July 4, 20082008-07-04
Piergiorgio Sartor wrote:> Jerry Avins wrote: > >> Whoa! Shift-register random-bit generators output a bit at a time. >> They are very good at producing a stream of random bits. They are very >> bad at producing random numbers. (With a shift register, each number >> is very > > Well, if you get good random bits, then you get > also good random numbers. > >> much like the previous one, just shifted a bit. How about that?!) > > Only if you, wrongly, read the shift register. > > What you've to do is to read one bit at time, > until you fill your word. > For example, read 8 bits to get a random byte, > then read *next* 8 bits and so on.I thought that that's what I wrote as one alternative. Somehow, it's not there.> Two consecutive bytes are _not_ one a shifted > version of the other.Given the type of artifacts that he described, I guessed that the OP's are. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 4, 20082008-07-04
esfield wrote:> The xorshift generator I'm using has three xor operations and three shift > operations; which, if I understand correctly, are supposed to work together > to create a 32-bit random number. > > Here is the code (I'm doing an asm version of this): > unsigned long xor(){ > static unsigned long y=2463534242; //seed > y�=(y<<13); y^=(y>>17); return (y�=(y<<5)); } > > When you refer to the xorshift method only producing one random bit at a > time, are you referring to the output of a *single* xorshift operation?You get one random bit per shift with the XOR-shifts I know. The internal state of the shift register sets up the next bit, but is not itself very random. As I wrote earlier, a linear congruential generator is simpler and ought to be quite adequate for your application. I didn't work through your code. There may be something clever that randomizes all the bits in the register, but I doubt it. ... Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 4, 20082008-07-04
Ben Jackson wrote:> On 2008-07-03, Jerry Avins <jya@ieee.org> wrote: >> The best implementation will will use 24 separate random-bit generators > > ...of different lengths and/or taps! Hate to see the OP make 24 identical > LFSRs... > >> Truncating bits reduces the sequence repeat length in a non-obvious way. > > Even if he retains the full length in the register? A subset of m bits > of an n-bit max-len LFSR repeats more frequently than every 2^n-1?It can. One needs to determine that for each configuration. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 4, 20082008-07-04
>I guess a little context would help: Ultimately, I want to create a*very>rudimentary* room eq. (I say that because I only have an octave-band >graphic eq to work with - yes, ugh!) I already have algorithms to split >the mic input into octave bands and to measure the power in the bands.I>assume I have to average the power results in each band over a period of >time? I also have a pinking filter that I got from this groupsomewhere..>it produces a very accurate -3dB per octave. So, if I can just get some >decent white noise I *should* be in business! >If your goal is to create audio white noise you might want to rethink the method you are using. You probably want the noise to have a gaussian distribution, not the rectangular distribution your approach will give. Doesn't your programming language have a built-in random number generator funtion? Here's a link that describes the generation of gaussian distributed white noise- it may be of help. As a previous post suggested, this uses the CLT for added rectangular distributions. Regards, Steve http://www.dspguide.com/ch2/6.htm
Reply by ●July 4, 20082008-07-04
On Jul 4, 9:48�am, Jerry Avins <j...@ieee.org> wrote:> esfield wrote: > > The xorshift generator I'm using has three xor operations and three shift > > operations; which, if I understand correctly, are supposed to work together > > to create a 32-bit random number. � > > > Here is the code (I'm doing an asm version of this): > > unsigned long xor(){ > > static unsigned long y=2463534242; //seed > > y^=(y<<13); y^=(y>>17); return (y^=(y<<5)); }wow, i nearly can understand this, but not quite. the shift-register sequence operation i was thinking of is sorta described at http://www.dspguru.com/info/tutor/mls.htm now maybe your operation above can be broken down into a normal looking LFSR sequence, the operation would be (in C code) static primitive_poly = 0x82D4E1B8; static int state = 1; // can be anything non-zero int random_bit(void) { if (state&0x00000001) { state = (state>>1)^primitive_poly; } else { state = state>>1; } return state&0x00000001; } an operation similar to that, is what i understand to be a pseudorandom shift register sequence. the LSB of "state" are bits that are virtually white in their correlation (except for DC), but " "state" itself, taken as a binary PCM value, does not make for a good, white random number.> > When you refer to the xorshift method only producing one random bit at a > > time,...> I didn't work through your code. There may be something clever that > randomizes all the bits in the register, but I doubt it.yeah, i'm skeptical too. but i also hadn't worked through it. maybe these 3 shift and XOR operations can be shown to be equivalent to the LFSR code above for a primitive polynomial that is somehow implied. i'll have to look more closely after the holiday. r b-j
Reply by ●July 4, 20082008-07-04
On Jul 4, 12:13�pm, "SteveSmith" <Steve.Smi...@SpectrumSDI.com> wrote:> > �I also have a pinking filter that I got from this group > somewhere.. > >it produces a very accurate -3dB per octave. �So, if I can just get some > >decent white noise I *should* be in business!this path has been trod before you. http://www.firstpr.com.au/dsp/pink-noise/> If your goal is to create audio white noise you might want to rethink the > method you are using. �You probably want the noise to have a gaussian > distribution, not the rectangular distributionSteve, if the OP is putting the white noise into a pinking filter, it will be at least a 3rd-order IIR, and because of all of the adding of RNs (and the central limit theorem), it won't much matter if the input to the pinking filter has a gaussian p.d.f. or not. what will come out will be filtered and virtually gaussian. he just needs to make some good white pseudo-noise and filter it with a good filter. i'd be curious what the filter he has with "very accurate -3dB per octave" performance is. care to share it? r b-j
Reply by ●July 4, 20082008-07-04
>Steve, if the OP is putting the white noise into a pinking filter, it >will be at least a 3rd-order IIR, and because of all of the adding of >RNs (and the central limit theorem), it won't much matter if the input >to the pinking filter has a gaussian p.d.f. or not. what will come >out will be filtered and virtually gaussian.Probably true -- ah, the everpresent CLT! Steve
Reply by ●July 4, 20082008-07-04
robert bristow-johnson wrote:> i think that needs to be justified. the bits coming out of a maximum- > length shift register sequence can be proven to be virtually white > (the autocorrelation is a spike at 0 with a small amount of DC). but, > unless you do some scrambling of the bits, they make lousy white > random numbers.I did not comment on the LFSR quality as PRNG, I did comment on *how* to use the output of those things.> so, for 24-bit numbers, you would have the shift register sequence > (with XOR-ing in the feedback path) clunk out 24 bits for each pseudo- > random number? makes it a little slower than linear congruence. at > least if you have a multiplierOf course it is slow, even if it depends on the clock, if it runs a 1GHz, maybe it is not that slow. But, again, that's not the issue.> okay, but i dunno if that is what the OP intended.He referenced Marsaglia, who is an authority in the field of random numbers. So I can be quite confident his (Marsaglia) approach will be well explained in pros and cons. bye, -- piergiorgio
