Re: white noise generation


"Jerry Avins" <jya@xxxxxxxx> wrote in message news:p_udnbalrN_LWvPVnZ2dnUVZ_qHinZ2d@xxxxxxxxxx
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



.

Relevant Pages

  • Re: white noise generation
    ... will generate every possible bit pattern in a group of bits exactly once before repeating the sequence. ... uniform distribution is the only possibility. ... All zeros is not a possible bit pattern, so there is a small bias that can be made evident by integration. ...
    (comp.dsp)
  • Re: ID vs. non-ID - Predictable Pattern Limits
    ... algorithmically random with respect to all reference computers. ... pattern based on the detected bias, with determining the origin of the ... knowledge of bias or predictive value based on the detection of bias ...
    (talk.origins)
  • Re: ID vs. non-ID - Predictable Pattern Limits
    ... though the vast majority of possible sequences can be proved to be ... In the same line, bias ... pattern or "bias" is actually noticed. ... You confuse the ability to detect bias and make predictions as to ...
    (talk.origins)
  • Re: bias cut skirt
    ... sometimes you have to slew it round if the stretch is down the fabric ... folded piece into a front and back and marked a bias. ... fullness in even worse if it has a pattern or nap. ... cutting orientation. ...
    (uk.rec.crafts.sewing)
  • Re: bias cut skirt
    ... folded piece into a front and back and marked a bias. ... fullness in even worse if it has a pattern or nap. ... A bias skirt inevitably means buying a larger piece of ... cutting orientation. ...
    (uk.rec.crafts.sewing)