8 bit white noise algorithm

John E. Hadstate wrote:
> "Steve Underwood" <steveu@dis.org> wrote in message
> news:ebe1el$v9$1@home.itg.ti.com...
>
> >> There are PRNGs, and then there are crypto-quality PRNGs.
> >> As a practical matter, you're not going to distinguish a
> >> crypto-quality PRNG from random white noise in trillions
> >> of years, no matter how much computing power you have.
> >> As an
> >
> > This greatly overestimates the quality of these
> > algorithms. Most crypto algorithms only achieve high
> > security
>
> [snip rest of bullshit]
>
> Mr. Underwood,
>
> You are holding forth on a subject about which you obviously
> have no expertise.  I suggest you spend a decade or so in
> the study of this subject.  You may find the effort both
> illuminating and rewarding.

I don't wish to get into a discussion on the various crypto qualities
of PRNGs of any type (because I am simply not qualified to discuss the
subject thoroughly), but something not mentioned by the OP is the
purpose for which he needs this white noise generator.

If it's to test a voice communication network, a simple 7-bit LFSR is
sufficient (and indeed has been used for this purpose for decades). If
it's to test something with a 100MHz bandwidth, then obviously that
would not suffice ;)

As an engineer, I like to use the simplest possible solution for any
probem :)

Cheers

PeteS

>sonos <sonos@nospam.com> writes:
>
>> Hi,
>>
>> any suggestions for an 8 bit white noise algorithm?
>
>Perform the following 16-bit linear congruential sequence
>generator:
>
>  x[n] = ((9821 * x[n-1]) + 6925) mod 65535
>
>and then use the upper byte and lower byte. The multiplier
>and addend are from Stephen Park.
>-- 
>%  Randy Yates                  % "Bird, on the wing,
>%% Fuquay-Varina, NC            %   goes floating by
>%%% 919-577-9882                %   but there's a teardrop in his
eye..."
>%%%% <yates@ieee.org>           % 'One Summer Dream', *Face The Music*,
ELO
>http://home.earthlink.net/~yatescr
>

Hi Randy,

I need a random number generator and I came across your 16-bit LCG - by
Stephen Park. It is perfect for my FPGA application (I need two 8-bit
random numbers @ 100MHz). I was wondering do you have a reference for where
you got it...I've looked around on the net to no avail.

Thanks,
MikeC

MikeC <michael.k.crowley@gmail.com> wrote:
<>sonos <sonos@nospam.com> writes:

<>  x[n] = ((9821 * x[n-1]) + 6925) mod 65535

<>and then use the upper byte and lower byte. The multiplier
<>and addend are from Stephen Park.

I would instead recommend a CRC generator, in hardware
known as LFSR, Linear Feedback Shift Register.  The most
popular being CRC32 used, for example, by ethernet.

(I used CRC32 to generate dither when changing the number
of bits of a digital audio signal, for example.)

The Xilinx SRL16 makes it very easy to generate long LFSR
generators, though 32 bits is probably enough for most
random numbers.  All that is needed are shift registers
and XOR gates!  No multiply or divide needed.

-- glen

>MikeC <michael.k.crowley@gmail.com> wrote:
><>sonos <sonos@nospam.com> writes:
>
><>  x[n] = ((9821 * x[n-1]) + 6925) mod 65535
>
><>and then use the upper byte and lower byte. The multiplier
><>and addend are from Stephen Park.
>
>I would instead recommend a CRC generator, in hardware
>known as LFSR, Linear Feedback Shift Register.  The most
>popular being CRC32 used, for example, by ethernet.
>
>(I used CRC32 to generate dither when changing the number
>of bits of a digital audio signal, for example.)
>
>The Xilinx SRL16 makes it very easy to generate long LFSR
>generators, though 32 bits is probably enough for most
>random numbers.  All that is needed are shift registers
>and XOR gates!  No multiply or divide needed.
>
>-- glen
>

Hi Glen,

Thanks for the response. I've used LFSRs before in comms systems for
single-bit random streams for scrambling and yes they are nice, efficient
and fast. But, I don't want to go to the hassle of combining multi-bit
streams into an 8-bit value and making sure that the LFSRs are reasonably
"offset" in their random streams to make the 8-bit value random and
uncorrelated in its bits. 

I have plenty of (17-bit) hard multipliers free in my device. Thats why I
want to use an LCG. When I looked at OP above I thought the modulus was
2^16 which is just a truncation but it is 2^16-1 which implies extra work.

So I am settling on the Grogono LCG which - although it has been
disparaged in various scientific papers - I hope should be good enough for
my application and was used for many years as a random number generator in
software libs (according to google).

The generation equation is:

x[n] = ((25173 * x[n-1]) + 13849) mod 2^16

which is multiply followed by add at 100MHz. Not a problem.

I am porting a software app (which used the Mersenne Twister - a
highly-recommended but hardware intensive algorithm) to an FPGA but I think
the Twister was overkill and that the LCG above should be enough. I'll soon
see though!

Thanks,
Mike.

MikeC wrote:

> I have plenty of (17-bit) hard multipliers free in my device.
> Thats why I want to use an LCG. When I looked at OP above I
> thought the modulus was 2^16 which is just a truncation but it
> is 2^16-1 which implies extra work. 
> 
> So I am settling on the Grogono LCG which - although it has been
> disparaged in various scientific papers - I hope should be good
> enough for my application and was used for many years as a
> random number generator in software libs (according to google).

You may be interested in these papers:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.2556
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.1024


Martin

-- 
Quidquid latine scriptum est, altum videtur.

MikeC wrote:

[...]

Here is the ultimately simple 8bit LCG without multiplications or 
divisions:

u8 rnd8(void)
{
static u16 seed = 0;

seed = (seed << 7) - seed + 251;

return (u8)(seed + (seed>>8));
}

Optimized for 8-bit CPU, will work for CPLD/FPGA as well.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

>
>
>MikeC wrote:
>
>[...]
>
>Here is the ultimately simple 8bit LCG without multiplications or 
>divisions:
>
>u8 rnd8(void)
>{
>static u16 seed = 0;
>
>seed = (seed << 7) - seed + 251;
>
>return (u8)(seed + (seed>>8));
>}
>
>Optimized for 8-bit CPU, will work for CPLD/FPGA as well.
>
>
>Vladimir Vassilevsky
>DSP and Mixed Signal Design Consultant
>http://www.abvolt.com
>

Hi Vladimir,

Thanks. This would be very efficient.

But, I did a quick plot and histogram of this for 20000 values and it
heavily used certain values 0 -> 255 and didn't use others at all. I'm not
sure if 20000 is statistically a good enough sample period. Is this
home-brew or can you point to some statistical analysis?

Thanks again,
Mike.

MikeC wrote:

>>
>>MikeC wrote:
>>
>>[...]
>>
>>Here is the ultimately simple 8bit LCG without multiplications or 
>>divisions:
>>
>>u8 rnd8(void)
>>{
>>static u16 seed = 0;
>>
>>seed = (seed << 7) - seed + 251;
>>
>>return (u8)(seed + (seed>>8));
>>}
>>
> Thanks. This would be very efficient.
> 
> But, I did a quick plot and histogram of this for 20000 values and it
> heavily used certain values 0 -> 255 and didn't use others at all.

????

The statistics over 20k values is very uniform, nearly ideal. Check your 
implementation.



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

>
>
>MikeC wrote:
>
>>>
>>>MikeC wrote:
>>>
>>>[...]
>>>
>>>Here is the ultimately simple 8bit LCG without multiplications or 
>>>divisions:
>>>
>>>u8 rnd8(void)
>>>{
>>>static u16 seed = 0;
>>>
>>>seed = (seed << 7) - seed + 251;
>>>
>>>return (u8)(seed + (seed>>8));
>>>}
>>>
>> Thanks. This would be very efficient.
>> 
>> But, I did a quick plot and histogram of this for 20000 values and it
>> heavily used certain values 0 -> 255 and didn't use others at all.
>
>????
>
>The statistics over 20k values is very uniform, nearly ideal. Check your

>implementation.
>
>
>
>Vladimir Vassilevsky
>DSP and Mixed Signal Design Consultant
>http://www.abvolt.com
>


Yep. I foozed up. I'm at home so I had to use Excel to plot and casted
incorrectly. It is pretty uniform. Super-easy to implement in FPGA too. 

Nice.

Thanks,
Mike.