white noise generation

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

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

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

"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