ramdon noise generation

I need to use FPGA to generate a normal distributed noise. Any idea? I
know that we can convert a even distributed ramdon sequence to a
normal distributed one. But I forgot the algorithm and I am not sure
if it is suitable to implement it in a FPGA.

1) Take FPGA and remove its legs.
2) Use a marker to write 'Heads' on one side, 'Tails' on the other.
3) Throw it up in the air.
4) See which side lands face up.
5) Repeat 3) and 4) until you have enough data.

Or try Google / Google Groups for LFSR, Random, etc. ;-)
Also check out the Random article here
http://www.xilinx.com/xlnx/xweb/xil_tx_home.jsp

HTH, Syms.

"linical" <linical@yahoo.com> wrote in message
news:885ef3e9.0407270924.53025943@posting.google.com...
> I need to use FPGA to generate a normal distributed noise. Any idea? I
> know that we can convert a even distributed ramdon sequence to a
> normal distributed one. But I forgot the algorithm and I am not sure
> if it is suitable to implement it in a FPGA.

Symon,

Your method is greatly flawed.  In addition to being very slow, it is 
subject to the imbalance of the weight of the device.  You would first 
have to add weight or trim weight to make sure the toss was fair.

Better to implement something a bit more elegant:

http://support.xilinx.com/xlnx/xweb/xil_tx_home.jsp?sGlobalNavPick=&sSecondaryNavPick=&category=-1209667&iLanguageID=1

"That is So Random!"

Austin

Symon wrote:
> 1) Take FPGA and remove its legs.
> 2) Use a marker to write 'Heads' on one side, 'Tails' on the other.
> 3) Throw it up in the air.
> 4) See which side lands face up.
> 5) Repeat 3) and 4) until you have enough data.
> 
> Or try Google / Google Groups for LFSR, Random, etc. ;-)
> Also check out the Random article here
> http://www.xilinx.com/xlnx/xweb/xil_tx_home.jsp
> 
> HTH, Syms.
> 
> "linical" <linical@yahoo.com> wrote in message
> news:885ef3e9.0407270924.53025943@posting.google.com...
> 
>>I need to use FPGA to generate a normal distributed noise. Any idea? I
>>know that we can convert a even distributed ramdon sequence to a
>>normal distributed one. But I forgot the algorithm and I am not sure
>>if it is suitable to implement it in a FPGA.
> 
> 
> 

Austin,
That's why Actel devices are superior to Xilinx FPGAs in this application.
You can keep blowing fuses until the part 'balances'.
As for the slowness of the method, you guys at Xilinx are always saying how
FPGAs can speed things up using parallel processing. Just get 1000 parts,
and throw them all at the same time.
Cheers, Syms.
p.s. Good TechX article, BTW!
"Austin Lesea" <austin@xilinx.com> wrote in message
news:ce6dhn$r892@cliff.xsj.xilinx.com...
> Symon,
>
> Your method is greatly flawed.  In addition to being very slow, it is
> subject to the imbalance of the weight of the device.  You would first
> have to add weight or trim weight to make sure the toss was fair.
>

There are at least two methods :

1) generate normaly distributed samples (quantized box-muller algorithm),
add a few of them (4 may be enough), according to the central limit
theorem, it increases the generator's precision

here is an interesting paper 
http://lester.univ-ubs.fr:8080/~boutillon/articles/ICECS_00_Emul.pdf


2) set the quantization of the noise you wish to produce, generate tables
storing values of the integrated density of probability (by software).
To generate a noise sample, generate uniformly distributed samples, search
in the tables for the nearest element and return this element's index. The
indexes returned should be normaly distributed. This is sometimes called the
thresholds method.

I may not be very clear but it works perfectly (I've tried it)

Pierre

In article <ce6dhn$r892@cliff.xsj.xilinx.com>,
Austin Lesea  <austin@xilinx.com> wrote:
>Symon,
>
>Your method is greatly flawed.  In addition to being very slow, it is 
>subject to the imbalance of the weight of the device.  You would first 
>have to add weight or trim weight to make sure the toss was fair.

Nah, a biased coin is perfectly fine:

Flip twice:
HH -> try again
HT -> Heads
TH -> Tails
TT -> try again.
-- 
Nicholas C. Weaver                                 nweaver@cs.berkeley.edu

Symon,

Gosh, I never thoguht of that:  throw a million devices into the air at 
once!

Austin

Symon wrote:
> Austin,
> That's why Actel devices are superior to Xilinx FPGAs in this application.
> You can keep blowing fuses until the part 'balances'.
> As for the slowness of the method, you guys at Xilinx are always saying how
> FPGAs can speed things up using parallel processing. Just get 1000 parts,
> and throw them all at the same time.
> Cheers, Syms.
> p.s. Good TechX article, BTW!
> "Austin Lesea" <austin@xilinx.com> wrote in message
> news:ce6dhn$r892@cliff.xsj.xilinx.com...
> 
>>Symon,
>>
>>Your method is greatly flawed.  In addition to being very slow, it is
>>subject to the imbalance of the weight of the device.  You would first
>>have to add weight or trim weight to make sure the toss was fair.
>>
> 
> 
> 

Yup,

But I was trying to deal with the original generator! But you are 
absolutely correct!  Nice to remember if you suspect someone has an 
unfair coin......

Best to test the original random number generator (as close to the core 
of its function).

Then one can add correction for 1/0 density, as you suggest.  That does 
not solve for frequency effects, however.

The NIST suite of tests, or Diehard tests are best applied to the core 
generator, so you can see its problems.  Then there are known and 
accepted techniques to use a biased generator, or even a RNG with 
frequency problems to create a better TRNG.

Austin

Nicholas Weaver wrote:
> In article <ce6dhn$r892@cliff.xsj.xilinx.com>,
> Austin Lesea  <austin@xilinx.com> wrote:
> 
>>Symon,
>>
>>Your method is greatly flawed.  In addition to being very slow, it is 
>>subject to the imbalance of the weight of the device.  You would first 
>>have to add weight or trim weight to make sure the toss was fair.
> 
> 
> Nah, a biased coin is perfectly fine:
> 
> Flip twice:
> HH -> try again
> HT -> Heads
> TH -> Tails
> TT -> try again.

Sounds a little complicated. Any random number generator 101 for me?
Plus, how can FPGA tossing give me random number with normal distribution?

Austin Lesea <austin@xilinx.com> wrote in message news:<ce8dob$r8a2@cliff.xsj.xilinx.com>...
> Yup,
> 
> But I was trying to deal with the original generator! But you are 
> absolutely correct!  Nice to remember if you suspect someone has an 
> unfair coin......
> 
> Best to test the original random number generator (as close to the core 
> of its function).
> 
> Then one can add correction for 1/0 density, as you suggest.  That does 
> not solve for frequency effects, however.
> 
> The NIST suite of tests, or Diehard tests are best applied to the core 
> generator, so you can see its problems.  Then there are known and 
> accepted techniques to use a biased generator, or even a RNG with 
> frequency problems to create a better TRNG.
> 
> Austin
> 
> Nicholas Weaver wrote:
> > In article <ce6dhn$r892@cliff.xsj.xilinx.com>,
> > Austin Lesea  <austin@xilinx.com> wrote:
> > 
> >>Symon,
> >>
> >>Your method is greatly flawed.  In addition to being very slow, it is 
> >>subject to the imbalance of the weight of the device.  You would first 
> >>have to add weight or trim weight to make sure the toss was fair.
> > 
> > 
> > Nah, a biased coin is perfectly fine:
> > 
> > Flip twice:
> > HH -> try again
> > HT -> Heads
> > TH -> Tails
> > TT -> try again.

On 29 Jul 2004 06:31:30 -0700, linical@yahoo.com (linical) wrote:

> how can FPGA tossing give me random number with normal distribution?

sheesh, haven't you heard of the Central Limit Theorem?
 :-)
-- 
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223          mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573                Web: http://www.doulos.com

The contents of this message may contain personal views which 
are not the views of Doulos Ltd., unless specifically stated.