"Jerry Avins" <jya@ieee.org> wrote in message
news:p_udnbalrN_LWvPVnZ2dnUVZ_qHinZ2d@rcn.net...
> John E. Hadstate wrote:
>
> ...
>
>> Either an LFSR or an Xorshift PRNG, with suitable choice of
>> parameters, will generate every possible bit pattern in a
>> group of bits exactly once before repeating the sequence.
>> Thus, uniform distribution is the only possibility.
>
> That's true, but possibly misleading. All zeros (all ones in
> some implementations) is not a possible bit pattern, so there
> is a small bias that can be made evident by integration.
The usable output of the LFSR is a single bit per clock (not
the whole shift register). A maximal-length N-bit LFSR will
generate ((2**N)-1) bits before the sequence repeats. Since
2**N-1 is an odd number, there must always be more zeroes than
ones or vice versa in the output, producing the small bias to
which you referred.
On the assumption that consecutive bits are uncorrelated, there
is an algorithm called the "Von Neumann Corrector" that will
remove this bias at the expense of discarding some of the
original bits. (This algorithm can also be applied to hardware
sources of random numbers, like radioactive decay, which, for
one reason or another, may exhibit bias.)
The Von Neumann Corrector algorithm works on pairs of
consecutive bits, and produces output as follows:
1.. If the input is "00" or "11", the input is discarded (no
output).
2.. If the input is "10", output a "1".
3.. If the input is "01", output a "0".
Further information is available at
http://everything2.com/index.pl?node_id=1467753
and
http://www.helsbreth.org/random/removing_bias.html
Reply by Jerry Avins●July 4, 20082008-07-04
John E. Hadstate wrote:
...
> Either an LFSR or an Xorshift PRNG, with suitable choice of parameters,
> will generate every possible bit pattern in a group of bits exactly once
> before repeating the sequence. Thus, uniform distribution is the only
> possibility.
That's true, but possibly misleading. All zeros (all ones in some
implementations) is not a possible bit pattern, so there is a small bias
that can be made evident by integration.
...
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by John E. Hadstate●July 4, 20082008-07-04
"esfield" <ethanstubblefield@hotmail.com> wrote in message
news:QvWdnVZr1ahas_DVnZ2dnUVZ_tXinZ2d@giganews.com...
> Hello, newbie here in need of some help:
>
> I'm trying to generate white noise. I found a paper online
> called
> "Xorshift RNG's" by George Marsaglia, and found it attractive
> because of
> its simplicity, and its also supposed to generate very good
> random numbers
> that have long periods, pass the diehard randomness tests,
> etc.
First of all, the Xorshift PRNG is not an LFSR, but it has been
proven that for every Xorshift PRNG there is an LFSR that will
generate exactly the same sequence of pseudo-random numbers.
Both families generate uniformly-distributed pseudo-random
numbers (they must) and both can be modelled using the
Berlekamp-Massey algorithm.
http://en.wikipedia.org/wiki/Berlekamp-Massey_algorithm
Because of this, they are not suitable for cryptography, though
they may be very well suited for modeling and simulation and
other DSP applications where security is not an issue.
Either an LFSR or an Xorshift PRNG, with suitable choice of
parameters, will generate every possible bit pattern in a group
of bits exactly once before repeating the sequence. Thus,
uniform distribution is the only possibility. However, when
you subset the parallel output of the Xorshift PRNG, you should
expect to see repetitions in the sequence of numbers that you
would not see if you were considering the whole parallel word.
If this is a problem, there are two alternative solutions.
First, you can cook up a set of parameters for that generate an
Xorshift PRNG with the desired word length, in your case 24
bits. Second, you can create the equivalent LFSR and assemble
the serial output into 24-bit words. (Do not, however, take
the shift register state as your random number--it's not.)
There is another solution, one that might serve you better. T.
G. Lewis and W. H. Payne published a paper called "Generalized
Feedback Shift Register Pseudorandom Number Algorithm", Journal
of the ACM, Vol. 20, No. 3, July, 1973, pp 456-468. In
essence, they choose a polynomial for a long-period LFSR, and
run the same polynomial on N bits in parallel. The trick is
that they initialize the N parallel shift registers to
different pseudo-random values. Then they cycle the LFSRs many
times to insure that they are properly initialized. Below is
the C code that actually computes the parallel pseudo-random
numbers from the L&P GFSR (after initialization). As you can
see, it's likely to be as fast as any Xorshift PRNG, and
decidedly faster than assembling bits from a single serial
LFSR. In the code below, each element of m[] holds the memory
of up to 32 parallel shift registers of length P. Q represents
the position (and exponent) of a single tap. If you want the
complete C source code, send a request to my e-mail address.
It's free and available under LGPL.
/***************************************************\
** **
** YEARS* P Q **
** ------ --- --- **
** 10^17 124 37 **
** 10^31 170 23 **
** 10^55 250 103 **
** 10^94 380 47 **
** 10^140 532 37 **
** **
** * YEARS TO REPEAT CYCLE ASSUMING 1 WORD PER **
** PICOSECOND (10^12 WORDS PER SECOND) -- **
** CURRENT (2002) TECHNOLOGY CAN'T QUITE **
** YIELD 10^9 WORDS PER SECOND USING THIS **
** ALGORITHM. **
** **
** According to Lewis and Payne, avoid designs **
** where Q is close to zero or close to (P-1)/2. **
** By these criteria, P=124, Q=37 appears to be **
** the best design. **
** **
\***************************************************/
#define P 124 /* Polynomial Order */
#define Q 37 /* Polynomial Tap */
unsigned long RandLP_int(unsigned long m[], int *j)
{
int k;
*j += 1;
if (*j >= P) *j = 0;
k = (*j + Q);
if (k >= P) k = k - P;
return (m[*j] ^= m[k]);
}
By the way, if you want to know how bad every Linear
Congruential Generator is, implement one (any one), generate a
few "random numbers", and look at the low-order bit of each
word in your sequence. Then, after you're done throwing-up,
look at the bit next to it. One or two such observations are
likely to cure any illusions you might have about pseudo-random
numbers generated by LCGs.
Reply by Piergiorgio Sartor●July 4, 20082008-07-04
Jerry Avins wrote:
> Given the type of artifacts that he described, I guessed that the OP's are.
Well, maybe he is misusing the LFSR, even
if it is not clear to me if the artifacts
are measured before or after the codec.
Because if they're after, I could imagine
the codec has something to do with it.
bye,
--
piergiorgio
Reply by Piergiorgio Sartor●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 multiplier
Of 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
Reply by SteveSmith●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 robert bristow-johnson●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!
> 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
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.
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 robert bristow-johnson●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 SteveSmith●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 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!
>
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 Jerry Avins●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.
�����������������������������������������������������������������������