ramdon noise generation

L

linical

Guest
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.
Click to expand...
 
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.
Click to expand...
 
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.
Click to expand...
 
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
 
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.
Click to expand...
 
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.
Click to expand...
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
 
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.
Click to expand...
 
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.
Click to expand...
 
On 29 Jul 2004 06:31:30 -0700, linical@yahoo.com (linical) wrote:

how can FPGA tossing give me random number with normal distribution?
Click to expand...
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.
 
Never heard of.

Jonathan Bromley <jonathan.bromley@doulos.com> wrote in message news:<jlvhg0dfn6v8veloup19e0s24mfnmoet1p@4ax.com>...
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.
Click to expand...
 
Heard of Google?
http://www.stat.sc.edu/~west/javahtml/CLT.html

"linical" <linical@yahoo.com> wrote in message
news:885ef3e9.0407291055.7913f75f@posting.google.com...
Never heard of.

Jonathan Bromley <jonathan.bromley@doulos.com> wrote in message
news:<jlvhg0dfn6v8veloup19e0s24mfnmoet1p@4ax.com>...
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?
:)
Click to expand...
 
Also see:
http://www.ee.ucla.edu/~dongu/pub/papers/fccm03_dul98.pdf

Pierre Wadier <peewee@melix.net> wrote in message news:<4106c89b$0$15280$636a15ce@news.free.fr>...
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
Click to expand...
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top