2
\$\begingroup\$

I was wondering how a computer or any other device can generate random numbers. Is there a way to do this using only digital parts(non-programmable parts such as gates)? When I think of it, it seems like there has to be an "analog side" to generate random numbers. How can one make a multi-bit random number?

\$\endgroup\$
  • \$\begingroup\$ I suppose it depends how random of a random number generator you need. \$\endgroup\$ – Tom Carpenter Nov 29 '15 at 21:04
  • 1
    \$\begingroup\$ I want to know how to generate a 1 bit random number that seems random to a person(like electronic dice). Not for industrial applications such as cryptography. \$\endgroup\$ – zack1544 Nov 29 '15 at 21:15
  • 2
    \$\begingroup\$ LFSR then. Pretty easy to make, just a shift register and some XOR gates. \$\endgroup\$ – Tom Carpenter Nov 29 '15 at 21:16
  • 1
    \$\begingroup\$ One early game just sampled a free running counter every time the user pushed a button. For your purposes you could basically use a fast 1-bit counter, ie a toggle. The real randomness comes from the human, at a granularity far below any manual intention (though some sort of button pusher gadget could perhaps be built to defeat it) \$\endgroup\$ – Chris Stratton Nov 29 '15 at 22:47
  • 1
    \$\begingroup\$ 1) All digital gates are made of analog parts. If you operate them outside of the specification they don't react digital or deterministic. 2) Search for TRNG (True Random Number Generator). There are papers describing TRNGs for ASICs and FPGAs. They can be build with selftuning mechanisms to emit a constant qualitiy of random numbers. \$\endgroup\$ – Paebbels Nov 29 '15 at 23:10
6
\$\begingroup\$

See this article

enter image description here

Uncertain Circuits: When transistor 1 and transistor 2 are switched on, a coupled pair of inverters force Node A and Node B into the same state [left]. When the clock pulse rises [yellow, right], these transistors are turned off. Initially the output of both inverters falls into an indeterminate state, but random thermal noise within the inverters soon jostles one node into the logical 1 state and the other goes to logical 0.

Also see the white paper (Respawned Fluff note: This is for an older Intel method, using two free-running oscillators, not the one described above.)

\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks.What is the name of this method? \$\endgroup\$ – zack1544 Nov 29 '15 at 21:29
  • \$\begingroup\$ @zack1544 I guess you would call it a "dual oscillator" method. See the white paper from 1999 for details: rambus.com/wp-content/uploads/2015/08/IntelRNG.pdf \$\endgroup\$ – Math1000 Nov 29 '15 at 22:34
  • \$\begingroup\$ @David This method could always be used to seed a pRNG (as is described in the article). \$\endgroup\$ – Math1000 Nov 29 '15 at 22:52
  • 1
    \$\begingroup\$ I removed my comment as your linked article is very good. However I stand by the general statement that many digital processors do not have a hardware RNG and therefore rely on purely software based pseudorandom mechanisms. \$\endgroup\$ – David Nov 29 '15 at 22:56
  • \$\begingroup\$ Beware that the devil is in the unpublished details in that scheme: "Having subtle differences in the speed or strength of their responses might seem like a mild offense, but in this application, such differences could easily compromise the randomness we were trying to extract from the circuit. To keep the inverters in balance, we built a feedback loop into the new hardware. The circuitry in that loop performs some targeted fiddling until the two possible output values, 0 and 1, each occur roughly half the time." \$\endgroup\$ – Fizz Dec 4 '15 at 1:30
4
\$\begingroup\$

A more "analog" approach is to reverse-bias a PN junction into breakdown or avalanche. Doing so (from a high impedance) causes electricity to conduct fairly randomly, producing a white-noise output which is statistically quite random. This Article by Giorgio Vazzana has to say, "Avalanche noise is the noise produced when a junction diode is operated at the onset of avalanche breakdown. It occurs when carriers acquire enough kinetic energy under the influence of the strong electric field to create additional electron-hole pairs by colliding with the atoms in the crystal lattice. If this process happens to spill over into an avalanche effect, random noise spikes may be observed." enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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