Re: [oc] Again! modulo arithmetic hardware

[Tobin Fricke <tobin@splorg.org>]

On Mon, 11 Mar 2002, Marko Mlinar wrote:

> > 2) Generate a random number of 9 bits (or larger) in width. Use a >
> logic core that inputs of 9 bits and outputs the count of bits > set.

> I am not an expert in random math, but I would say this new distribution
> is not random anymore.

You're right, too.  Actually, the output of this process will be random,
but the distribution won't be flat.  Some numbers will be much more
probable than others.  A simple simulation should show this quite readily.

It turns out that this scheme generates the binomial distribution.

( http://mathworld.wolfram.com/BinomialDistribution.html )

It's pretty easy to compute the probability for each of the outputs { 0,
1, ... 9 }.  To get X as an ouput, we need to have exactly X bits set out
of 9.  The probability of getting X is then the number of combinations of
nine bits with exactly X set multiplied by the probability of each
combination.  The number of combinations is given by the binomial function
y!/(x!(y-x)!) with y=9 and each combination has probability (1/2)^9.

The resulting probabilities are:

0: 0.00195
1: 0.01758
2: 0.07031
3: 0.16406
4: 0.24609
5: 0.24609
6: 0.16406
7: 0.07031
8: 0.01758
9: 0.00195

Note that it is, for example, 126 times more likely to get a 4 or a 5 than
it is a 0 or a 9.

I suggest the original poster refer to Knuth who wrote extensively on
psuedorandom sequence generation.

Tobin



--
To unsubscribe from cores mailing list please visit http://www.opencores.org/mailinglists.shtml