Re: [oc] Again! modulo arithmetic hardware

["Jim Dempsey" <tapedisk@ameritech.net>]

----- Original Message -----
From: "Tobin Fricke" <tobin@splorg.org>
To: <cores@opencores.org>
Sent: Monday, March 11, 2002 4:35 AM
Subject: Re: [oc] Again! modulo arithmetic hardware


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

Thanks for correcting me. The error is quite obvious after a little
inspection. Given a 3 bit number the probability of number of bits

    0 = 1/8
    1 = 3/8
    2 = 3/8
    3 = 1/8

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

Pseudorandom sequence generation usualy is done multiplication and shift.
An example of generating an 8-bit random number.

    WORD    seed = SEED_PRIME_NUMBER;    // 16-bit any prime number .gt. 2
    UBYTE    multiplier = MULTIPLIER_PRIME_NUMBER;;    // 8-bit any prime
number .gt. 2

    UBYTE randomUBYTE()
    {
        // Prime numbers .gt. 2 are always odd numbers
        // odd numbers multiplied by odd numbers always produce odd numbers
        // compute new odd number and
        // return the middle 8 bits of the product
        // the result is a pseudo random number
        return (UBYTE)((seed *= multiplier) >> 4);
    }

Multiplication can be slower than what you need.
Since this is a PLD you could make a specialzed multiplier for use only by
the random number generator. Assuming you do something with the result and
that what you do takes more than 8 clock cycles then you could do the 16 x 8
multiplication for the next result in the 8 clock cycles after each result
is read.

Jim Dempsey


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

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