random generator in hardware

[ALuPin]

Hi,

I want to implement the following in hardware:

A ROM with 168 8bit entries is read out in a random manner. For the
generation
of the random ROM addresses I do have several clock cycles. How can I
build such randomness in hardware ? There are several functional
random generators for simulation but they are not synthesizable.

Rgds
Andre

 

[KJ]

Hi,

I want to implement the following in hardware:

A ROM with 168 8bit entries is read out in a random manner. For the
generation
of the random ROM addresses I do have several clock cycles. How can I
build such randomness in hardware ? There are several functional
random generators for simulation but they are not synthesizable.

Rgds
Andre

It will of course depend on your how truly 'random' the numbers must appear,
but an LFSR is the basis for many pseudo-random number generators. Unless
you can rely on some truly random event that is happening 'outside' (i.e.
quantum effects, thermal noise, radiation decay, etc.) to provide some true
randomness you'll never be able to achieve true randomness, just an
approximation. From what you've posted though, I'm suspecting that a
pseudo-random sequence might be sufficient in which case you should google
for LFSR (linear feedback shift register) and pseudo-random number
sequences.

Kevin Jennings

 

[David R Brooks]

It will of course depend on your how truly 'random' the numbers must appear,
but an LFSR is the basis for many pseudo-random number generators. Unless
you can rely on some truly random event that is happening 'outside' (i.e.
quantum effects, thermal noise, radiation decay, etc.) to provide some true
randomness you'll never be able to achieve true randomness, just an
approximation. From what you've posted though, I'm suspecting that a
pseudo-random sequence might be sufficient in which case you should google
for LFSR (linear feedback shift register) and pseudo-random number
sequences.

Kevin Jennings

LFSR is the obvious method for this, however it will generate 255
possible values. The OP will need to define what should happen when it
generates one outside the 168 values allowed. Some possibilities:
1. Take the modulo-168 of the PRBS output (ie divide & use remainder)
2. Expand the ROM to 255 entries, & duplicate some existing ones
3. Hit the PRBS again if it generates a value out of range
I'm sure there are more...

BTW, from Schneier's "Applied Cryptography", a usable set of taps for an
8-bit LFSR is (8,4,3,2,0)
Such a LFSR will repeat its sequence after 255 clocks: to have a longer
period, use a longer register, & choose any 8 bits from it.

 

[Ray Andraka]

LFSR is the obvious method for this, however it will generate 255
possible values. The OP will need to define what should happen when it
generates one outside the 168 values allowed. Some possibilities:
1. Take the modulo-168 of the PRBS output (ie divide & use remainder)
2. Expand the ROM to 255 entries, & duplicate some existing ones
3. Hit the PRBS again if it generates a value out of range
I'm sure there are more...

BTW, from Schneier's "Applied Cryptography", a usable set of taps for an
8-bit LFSR is (8,4,3,2,0)
Such a LFSR will repeat its sequence after 255 clocks: to have a longer
period, use a longer register, & choose any 8 bits from it.

Actually, the LFSR should only be used to produce one bit per clock
cycle because the other bits in the shift register are time-shifted
copies of the first bit. They are therefore not independent, or even
pseudo-independent. YOu can take more than one bit at a time out of an
LFSR, but you need to clock in n times between grabs for an n bit grab
in order to not have a dependency on previously grabbed values. For
example, the 8 bit example you gave should only be sampled every 8th shift.

Take the 4 bit LFSR sequence for taps=1100 for example:
0000
0001
0011
0111
1110
1101
1011
0110
1100
1001
0010
0101
1010
0100
1000
note how the upper bits are copies of the lower bits from previous
times. This results in a decidely non-random output.


Xilinx has a listing in XAPP052 of tap settings for maximal length
sequences for 4 to 168 bit LFSRs. A maximal length sequence is one that
has 2^k-1 states in the sequence (i.e. the number of bits before it
repeats) for a k bit shift register.

 

[Ray Andraka]

Ray Andraka wrote:

One more thing, another possible way to reduce the set which retains the
uniform probability is to discard samples that are outside of the
desired range. That however, requires the random numbers be generated
faster than they are needed and good ones be stored in a fifo where they
are kept until needed.

Using a table to remap the data to a smaller set will generally result
in a probability distribution that is no longer uniform, which can mess
up your application pretty badly.

Note that the probability distribution for the bit output out of an
unmodified LFSR is not quite 50-50 because there are always an odd
number of states in the sequence. There is some gating you can do to
extend the sequence to include the "illegal state" that will also
balance the distribution: it is basically detecting the all '0's state
and using that to insert the all '1's state into the sequence. I
believe one of the Xilinx app notes also has a note regarding this
(might be XAPP052, or it might be another one, there were two in the
late '90s addressing LFSRs).

If you need some distribution other than a uniform distribution, you
need to perform some transformation, either by using the uniform
distribution to address a PDF table or by performing some computation
(for example, a gaussian distribution can be derived by summing samples
from a uniform distribution using the central limit theorem).

I address these techniques to some degree in my 1998 paper "An FPGA
based processor yields a real time high fidelity radar environment
simulator", which is available for free on my website at
http://www.andraka.com/papers.htm. That design was done on eight
XC4025's, without the benefit of on-chip BRAM or multipliers. The whole
thing could probably be put into a single XCV4SX55 today, with
considerably less total design effort.

 

[ALuPin]

Hi,

thank you for your good suggestions.

Rgds
Andre

 

[kennheinrich]

Hi,

thank you for your good suggestions.

Rgds
Andre

If you're happy to live with an 8-bit LFSR generating addresses, then
you may as well just permute the order of the data in the ROM (do this
offline, in your source code), then just index the data with a simple
counter. This will give you the same degree of "randomness".

If you want data that's "more random", i.e. exhibits a longer interval
between repeating, you'll need a longer LFSR.

Also, note that 168 = 169-1 = 13*13 - 1. So an LFSR operating over
GF(13^2), or equivalently a degree-2 LFSR over GF(13) LFSR (note that
this is different than GF2^13 ) will directly give you a maximal-
length LFSR with 168 unique non-zero states. But you'll still
typically implement this in a pair of 4-bit registers (= 8 bits), then
you have to map down (presumably) to a fixed interval 0..167. So
you're no better off than you were before. Just use a really long
binary LFSR if you want more coverage.

HTH,

- Kenn