Electronic – Random number generation with skewed distribution

digital-logicrandom number

I would like to implement a fully-digital circuit that can generate a random variable X with P(1)=p, P(0)=1-p (where, ideally, the probability p would be configurable with a programmable parameter).

An LFSR is useful for pseudo-random number generation and for getting a random variable in which probabilities to be at 0 or 1 are (almost) equal: this is not what I am looking for.

The ideas I was thinking about:

  • I could 'AND' the outputs of several LFSRs, but given that in my application p will often be <0.1, the number of required LFSRs would be unpractical.
  • I could also try to add a comparator and compare the contents of the LFSR to some configurable threshold to get the probability p. But given that an LFSR 'shifts' its contents, wouldn't the successive outputs of the comparator be too similar or predictable? I am unfamiliar with these concepts, so I am not sure.

I need the successive values of the generated random variable to be as independent as possible, but it is not a problem if the pattern of successive values is cyclic in the very long term (as for any LFSR output). Thank you in advance for any improvement of the above ideas or any totally different idea that could solve my problem.

EDIT – A microcontroller is out of the scope of this question for two reasons:

  • This implementation targets an ASIC
  • I am limited in resources and I might have to instantiate this circuit a couple of times, a µC is just overkilling
  • this has to be high-speed random number generation (a µC would would require several clock cycles)

Best Answer

You don't need to XOR many LSFRs to get something that looks much more random (less shifty) than a single LSFR. Other techniques to improve the output of LSFRs are to cache the output in a small 2 port RAM, reading out and then replacing a random bit each time, that random address given by another LSFR of different length.

Given several short LSFR-based streams, you could construct a multibit number each clock cycle that goes into your comparator against \$p\$, making sure that at least a few MSBs are from the better sources.

None of this mucking about will get you to cryptographic levels of random goodness, but it will mitigate against the most obvious shortcomings of the LSFR.

Related Topic