Electronic Dice ( 3 die ) In VHDL

[Jonathan Bromley]

"Symon" <symon_brewer@hotmail.com> wrote in message
news:a28bc07f.0310141330.6158537d@posting.google.com...

Jonathan,
Please pay attention to the OPs spec. He/she said 'randomly'. This
implies the measurement of some random process, I suggest radioactive
decay measurement is the preferred solution.

My humblest apologies to all, and the OP in particular. You are
of course quite correct.

Unfortunately, this makes the problem even harder. As I'm sure
you're aware, standard methods for detecting the randomness of
radioactive decay mandate the use of a cat, a sealed box and
a vial of some toxic substance. Since the cat has a 0.5
probability of survival in each measurement to determine one
bit, and a 6-position die requires an average of approximately
2.5849625007211561814537389439478 bits of data, it's clear
that this mechanism will entail a mean loss of
1.2924812503605780907268694719739 cats per displayed value,
or nearly 4 cats per 3-dice roll. In order to achieve this
with a 20% margin of spare bandwidth, it's clearly
necessary to use CAT-5 cable for all the interfaces.

This is why Xilinx offer radiation hardened devices
specifically so people can make reliable unbiased dice.
(It's no coincidence the chips are also called 'dice'.)
Note these parts are not usually offered in BGA packages,
but in leaded ones. The lead protects against radiation.

Superb. ROFL.
--
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, Hampshire, 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.

 

[PO Laprise]

How about using one LFSR per die pip? Using the SRL16s in Xilinx chips (don't know A, sorry), that would mean somewhere around 9 slices (for 3x6 pips), plus overhead, decoding logic, etc..., if I'm not mistaken? Incidentally, would using different polynomials effectively (as far as the human is concerned) decorrelate the LFSRs? Or would varying lengths (16, 32, etc...) do the trick? Or even, would different seeds be enough? I've never gotten around to studying the math, and never been great with statistics anyway... <p>Pierre-Olivier <p>-- to contact me directly, remove the obvious from my email --

 

[John_H]

"Vinh Pham" &lt;a@a.a&gt; wrote in message
news:ft4jb.12621$ZH4.10910@twister.socal.rr.com...

It's a seven segment display, so it might be up to 1d16

...

between 1d2 and 1d16. Bonus points for only allowing configurations
where an actual polygon would make a legal die (all sides the same
area).

Whew. I was freaking out for a moment there. I thought there was a gap
in
my gaming lore, that I had somehow gone through life ignorant of the
16-sided die :_)

Just because 16 sided dice aren't used doesn't mean they can't be done. I
could supply three different types of 16 sided polyhedra, all with equal
faces.

I was, after all, responsible for getting the 30 sided die on the market
(back in the summer of '82).

Now it's FPGA design for me.

- John_H

 

[Vinh Pham]

An LFSR output is only "random" for a single bit out per clock. The
remaining bits are delayed copies of the first bit. In order to use an

There are two forms of an LFSR. One where the bits are just delayed
versions and you have a huge adder that feeds the chain (good ol' Google
says this is called the Fibonacci form). And there's another one where
there are adders inbetween the registers so that the bits are not delayed
versions of each other (called the Galois form).

Even in the case of the Fibonacci form, I have a feeling that grabbing a few
adjacent bits will still produce a "random" number. Of course it depends on
what you consider random, and I don't know much about the measurements they
use for that.

it 3x per die. If you go further to reject 'illegal' combinations, then
you are skewing the probabilities of the legal combinations so that they
are no longer uniform.

Rejecting illegal combinations should be okay. The legal combinations will
remain uniform. Unfortunately I don't know a good way to explain this. But
you can take a six sided dice, reject values of 5 and 6, and have it act
like a uniform four sided dice.

The only problem with the rejection method is you're not guaranteed a valid
value every clock cycle, which is no big deal in this human operated push
button application, but for some deterministic applications, you can't
afford to wait for a "reroll" of the number.


--Vinh

 

[Ray Andraka]

You could either use 3 copies of a long LFSR with unique
seeds that are placed sufficiently far apart to produce
uncorrelated sequences *within the observation period*, or
you could use LFSRs with 3 different relatively prime
lengths. There is a very limited set of polynomials that
will produce an LFSR of a given length, and the resulting
sequence is usually a permutation of the same sequence, so
it does not provide much randomness.

PO Laprise wrote:

How about using one LFSR per die pip? Using the SRL16s in
Xilinx chips (don't know A, sorry), that would mean
somewhere around 9 slices (for 3x6 pips), plus overhead,
decoding logic, etc..., if I'm not mistaken? Incidentally,
would using different polynomials effectively (as far as
the human is concerned) decorrelate the LFSRs? Or would
varying lengths (16, 32, etc...) do the trick? Or even,
would different seeds be enough? I've never gotten around
to studying the math, and never been great with statistics
anyway...

Pierre-Olivier

-- to contact me directly, remove the obvious from my
email --

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin
Franklin, 1759

 

[Ray Andraka]

Well, not really an adder. It is an XOR or XNOR combination of the terms in the
polynomial. In either case, grabbing adjacent bits will give a random as long
as you let N clocks go by between successive samples (N is the number of bits
taken from the LFSR). Note that this is the same as taking one bit at a time
and filling a shift register. The restriction is that you get one new bit for
each time you clock the LFSR, the remaining bits are shifted copies of the first
bit. If you take more bits out per sample than you have clocks per sample, you
will get a correlation between successive samples.

Vinh Pham wrote:

An LFSR output is only "random" for a single bit out per clock. The
remaining bits are delayed copies of the first bit. In order to use an

There are two forms of an LFSR. One where the bits are just delayed
versions and you have a huge adder that feeds the chain (good ol' Google
says this is called the Fibonacci form). And there's another one where
there are adders inbetween the registers so that the bits are not delayed
versions of each other (called the Galois form).

Even in the case of the Fibonacci form, I have a feeling that grabbing a few
adjacent bits will still produce a "random" number. Of course it depends on
what you consider random, and I don't know much about the measurements they
use for that.

it 3x per die. If you go further to reject 'illegal' combinations, then
you are skewing the probabilities of the legal combinations so that they
are no longer uniform.

Rejecting illegal combinations should be okay. The legal combinations will
remain uniform. Unfortunately I don't know a good way to explain this. But
you can take a six sided dice, reject values of 5 and 6, and have it act
like a uniform four sided dice.

The only problem with the rejection method is you're not guaranteed a valid
value every clock cycle, which is no big deal in this human operated push
button application, but for some deterministic applications, you can't
afford to wait for a "reroll" of the number.

--Vinh

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Bob Perlman]

On Tue, 14 Oct 2003 17:56:31 +0100, "Jonathan Bromley"
&lt;jonathan.bromley@doulos.com&gt; wrote:

"Amstel" &lt;lange360@hotmail.com&gt; wrote in message
news:56f7756d.0310140824.7d8fe744@posting.google.com...
I'm trying to make an electronic dice (3 die). Basically the dice has
3 seven-segment displays and the 3 dice values will run randomly so
that we would always get different values combinations. However I
tried and was unable to write the program in VHDL .

Do you have any idea how incredibly hard this is?

Mind-boggling detailed discussion snipped

Superb answer, Jonathan. I suspect that, even as you read this,
someone is talking to their dean about transferring from electrical
engineering to political science or animal husbandry.

And should you need it, I can give you the name of an excellent
removing-tongue-from-cheek surgeon.

Take care,
Bob Perlman
Cambrian Design Works

 

[jetmarc]

An LFSR output is only "random" for a single bit out per clock. The
remaining bits are delayed copies of the first bit. In order to use an
LFSR and really have a random stream of 3 bit numbers you'd need to clock
it 3x per die. If you go further to reject 'illegal' combinations, then
you are skewing the probabilities of the legal combinations so that they
are no longer uniform.

I agree that you have to implement the full PRNG and not just use some
bits of the LFSR, to get the full quality of the PRNG.

However, rejecting illegal values is IMHO a "good" thing to do, meaning
that it doesn't bias. After all, each and every output value of the
PRNG is "unpredictable" (within the quality limits of the PRNG). Thus,
rejecting all 0x6 and 0x7 doesn't reveal more information than that the
final output won't ever be 0x6 or 0x7. Still, an attacker can't predict
any output value, given that he couldn't predict them already before we
added the reject circuit.

It's a consequence of the lack of feedback into the PRNG. The PRNGs
internal state is only changed through the intended means - by going
from state n to n+1 (next value) etc. All cryptographic study that
the PRNG design has received, inherently also applies to the
combination of PRNG and rejection circuit.

The only disadvantage of this method is that the execution time is not
predictable. Although highly unprobable, the PRNG could output 0x6 / 0x7
for a lot of cycles in sequence. Thus you don't know how long it takes
to get an acceptable (legal) output. In this particular application
(dice) however, I don't think that it will be a problem of significance.

Marc

 

[Jim Granville]

Ray Andraka wrote:

Why seven segment LEDs though? It would be more appropriate to use 7 LEDs arranged
like the 'six' and 'one' sides of the die superimposed.

Correct - and the design also does not have to have Mod 6 counting -&gt;
Decoder;
it is possible to count directly in either 7 segment Font patterns, or
in Ray's Dice-Font pattern.

I have actually done a design that counts directly in 7
segment Font patterns (0..9) - the student can explain why that
might be a good idea.

-jg

 

[Ray Andraka]

I did a similar 3 die design way back when (ca 1976) using TTL parts. It could easily be
done in a small CPLD and a short time with current tools.

Jim Granville wrote:

Ray Andraka wrote:


Why seven segment LEDs though? It would be more appropriate to use 7 LEDs arranged
like the 'six' and 'one' sides of the die superimposed.

Correct - and the design also does not have to have Mod 6 counting -
Decoder;
it is possible to count directly in either 7 segment Font patterns, or
in Ray's Dice-Font pattern.

I have actually done a design that counts directly in 7
segment Font patterns (0..9) - the student can explain why that
might be a good idea.

-jg

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Ray Andraka]

As long as you discard all the bits for each illegal value it is uniform. Some
reason I was thinking the OP was looking at discarding a bit until the right
one came in. Must have been before my coffee.

jetmarc wrote:

An LFSR output is only "random" for a single bit out per clock. The
remaining bits are delayed copies of the first bit. In order to use an
LFSR and really have a random stream of 3 bit numbers you'd need to clock
it 3x per die. If you go further to reject 'illegal' combinations, then
you are skewing the probabilities of the legal combinations so that they
are no longer uniform.

I agree that you have to implement the full PRNG and not just use some
bits of the LFSR, to get the full quality of the PRNG.

However, rejecting illegal values is IMHO a "good" thing to do, meaning
that it doesn't bias. After all, each and every output value of the
PRNG is "unpredictable" (within the quality limits of the PRNG). Thus,
rejecting all 0x6 and 0x7 doesn't reveal more information than that the
final output won't ever be 0x6 or 0x7. Still, an attacker can't predict
any output value, given that he couldn't predict them already before we
added the reject circuit.

It's a consequence of the lack of feedback into the PRNG. The PRNGs
internal state is only changed through the intended means - by going
from state n to n+1 (next value) etc. All cryptographic study that
the PRNG design has received, inherently also applies to the
combination of PRNG and rejection circuit.

The only disadvantage of this method is that the execution time is not
predictable. Although highly unprobable, the PRNG could output 0x6 / 0x7
for a lot of cycles in sequence. Thus you don't know how long it takes
to get an acceptable (legal) output. In this particular application
(dice) however, I don't think that it will be a problem of significance.

Marc

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759

 

[Vinh Pham]

Well, not really an adder. It is an XOR or XNOR combination of the terms
in the

Yeah adder isn't the best word, because the adders we normally think of have
a carry chain. Modulo-2 addition has no carry, so it simplifies to an XOR.

 

[Nial Stewart]

Peter Alfke &lt;peter@xilinx.com&gt; wrote in message
news:3F8C5BC4.641FA8DA@xilinx.com...

I admit, my "irony detector" was temporarily asleep, and the German
seriousness took over...

Coming from Northern Ireland my 'irony detector' is stuck at
10.


Nial
------------------------------------------------
Nial Stewart Developments Ltd
FPGA and High Speed Digital Design
www.nialstewartdevelopments.co.uk

 

[Symon]

Then you've seen www.portadownnews.com ? The 'Drumcree VII' edition,
featuring "Vatican sends Holy Water Cannon", is a favourite!
cheers, Syms.

Coming from Northern Ireland my 'irony detector' is stuck at
10.


Nial

 

[Jim Granville]

Ray Andraka wrote:

I did a similar 3 die design way back when (ca 1976) using TTL parts. &gt; It could easily be done in a small CPLD and a short time with
current tools.

With some care (challenge for todays students ?) I believe one
can pack 2 dice into a 16V8 - smallest/cheapest programmable logic
device made.

Ideal for backgammon etc....

What games need 3 dice ?

-jg

 

[Ray Andraka]

It was for a bar game, although there are several board games that use more than 2 dice. Yahtzee, for example uses 5 as I recall.

Jim Granville wrote:

Ray Andraka wrote:

I did a similar 3 die design way back when (ca 1976) using TTL parts. &gt; It could easily be done in a small CPLD and a short time with
current tools.

With some care (challenge for todays students ?) I believe one
can pack 2 dice into a 16V8 - smallest/cheapest programmable logic
device made.

Ideal for backgammon etc....

What games need 3 dice ?

-jg

--
--Ray Andraka, P.E.
President, the Andraka Consulting Group, Inc.
401/884-7930 Fax 401/884-7950
email ray@andraka.com
http://www.andraka.com

"They that give up essential liberty to obtain a little
temporary safety deserve neither liberty nor safety."
-Benjamin Franklin, 1759