1
\$\begingroup\$

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)
\$\endgroup\$
10
  • \$\begingroup\$ "fully-digital circuit" so why not take a µC and implement it in any nice programming language there? \$\endgroup\$
    – PlasmaHH
    Jul 21, 2017 at 8:56
  • \$\begingroup\$ Thanks for your comment. Unfortunately, a µC would be unpractical, I edited my base post with the justification. \$\endgroup\$
    – C_Computing
    Jul 21, 2017 at 9:02
  • 1
    \$\begingroup\$ random numbers are no trivial thing, I would not call a single chip µC overkill when the discrete digital implementation would likely be many many chips. Also how fast is "high-speed" for you? µCs are pretty fast, and there are some with built in random number generators. Also an option is an fpga, but that is even more fancy but might be even higher speed... \$\endgroup\$
    – PlasmaHH
    Jul 21, 2017 at 9:06
  • \$\begingroup\$ My target is a full-custom digital IC and I need to update my circuit values with this random number generation (might be 32 in parallel) in only one clock cycle at high speed (e.g. 100MHz). On-chip µCs will not be fast enough, require programming each single unit (constraints the IOs of the global chip), and require far more area than, for example, instances of LFSR + comparator (not the best idea as described in my post, but gives the order of magnitude I expect). \$\endgroup\$
    – C_Computing
    Jul 21, 2017 at 9:13
  • 2
    \$\begingroup\$ How much resolution do you need on the value of "p"? A simple LFSR generates only one new bit per clock, but it's simple to extend the concept to generate 4, 8 or more new bits per clock, which eliminates the correlation between successive values. Look at how high-speed CRC generators work -- it's the same underlying concept. There are also many other ways to generate uniformly-distributed multi-bit random numbers in one clock. Have you researched the literature at all? \$\endgroup\$
    – Dave Tweed
    Jul 21, 2017 at 12:11

2 Answers 2

Reset to default
2
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ Great, it seems very close to what I am looking for! Do you have any resource/paper with this 2-port RAM approach? \$\endgroup\$
    – C_Computing
    Jul 21, 2017 at 21:01
  • \$\begingroup\$ How do you see this comparator idea working for p=0.037? \$\endgroup\$
    – Paul Uszak
    Jul 21, 2017 at 21:10
  • \$\begingroup\$ @PaulUszak if you construct a 10 bit multibit number, that gives resolution of \$p\$ to 0.001, if you construct a 20bit number, that gives resolution to 0.000001. You seem to be suggesting there's a problem somewhere. \$\endgroup\$
    – Neil_UK
    Jul 22, 2017 at 6:09
  • \$\begingroup\$ @C_Computing It's one of those things I came across a loooong time ago in a dead-tree text book. Googling for 'shuffle bag random' brings up some things that look close, but don't address the specific case. The shuffle bag completely fills and empties, while the algorithm I suggest works a bit at a time. If the replace address is pseudo random, then no bit waits in the RAM longer than its period. The important thing is (obviously) to have different periods on the original sequence and the shuffle. This is good, includes tests. \$\endgroup\$
    – Neil_UK
    Jul 22, 2017 at 6:28
  • \$\begingroup\$ @C_Computing In fact, referring to that source, bottom of 3rd page, you might find the shift add version of the 32 bit KISS generator is easy enough to implement that it beats out a mess of combined LSFRs. \$\endgroup\$
    – Neil_UK
    Jul 22, 2017 at 6:32
1
\$\begingroup\$

Overlapping distribution

Have two normally distributed generators (or one & pipeline ) but with different probability density & more importantly different Mean.

If the 2ns generator has a lower density but a slightly more positive mean, the overall skew will be negatively biased

The summation of the two sources will provide a skewed distribution

\$\endgroup\$
2
  • \$\begingroup\$ This is an interesting idea. I have two questions. 1. For the "and more importantly different Mean": how would you realize that with LFSRs (given that they always have a mean of 0.5, equal probability between 0 and 1)? 2. Do you have some detailed paper/resource with this theory so that I can have a look at it? \$\endgroup\$
    – C_Computing
    Jul 21, 2017 at 9:47
  • \$\begingroup\$ google.co.uk/url?sa=t&source=web&rct=j&url=http://… \$\endgroup\$
    – user16222
    Jul 21, 2017 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.