In the book,
Netlab Loligo, repeated calls are made for true random number generators (
TRNGs) to be included in all
CPUs, or at least in those that are intended for use in neural network applications. Naturally, I was very excited to see a headline about Intel having developed one with general purpose use in mind.
IEEE has
an article about a new “true” random number generator from Intel that has been 10 years in development. Its primary advantage is that, while it is a true RNG, it operates entirely in digital mode using digital devices to obtain randomness from hardware. The slow, energy hogging, analog technology normally needed to glean randomness from Quantum phenomena has been eliminated. It has a few quirks, such as the need to force the outputs of its two mutex inverters high, and the seemingly unavoidable need to compensate using averaging techniques. I expand just a little on these quirks below.
In the spirit of not critiquing something without also offering, at least, a sincere attempt at a solution, I've forwarded a quick (if dirty) attempt at an “all logic gates” DTRNG (Digital True Random Number Generator) below. Only the equations were scratched out at the IEEE blog, I've since produced a circuit diagram graphic, which is included here as well.
First off, let me make clear that I think the Intel design is very cool. It is a great idea and it solves a very real technical problem that I wasn't even aware existed before reading the article. Specifically, putting a "true," general purpose, random-number register into a CPU has been a problem because random number generators relied on power-hungry analog circuits to amplify the various phenomena caused by quantum uncertainty (thermal noise, for example). The reliance on analog circuits also made the old RNGs very slow, only able to produce a few thousand numbers a second.
It all makes sense now! This explains why, in today's world of billion-transistor IC's, there have been few processors with random-registers.
The Intel design is based on eliminating the analog from the design completely, and using only digital. Realistically, all digital circuits spend some time in analog range, though, and that is exploited in this innovation. The Intel circuit still seems to depend on that analog—sort of—but the time it spends biased in that range is very short. Because it spends no more time in analog than any other digital circuit, the power and speed issues associated with analog schemes are effectively eliminated. Also, because it uses only the normal CMOS circuitry that is used for everything else on the chip, the added manufacturing steps needed to add the amplifier stages is no longer required in fabrication.
The Intel design employs two elements that I would characterize as fudging mechanisms.
- They need to do a strange trick where they are forcing the outputs of both inverters high simultaneously. They need to do this to set up the contention cycle where a "winner" is chosen. According to the article, they have specially designed the inverters so that they are able to take this "abuse." The scheme also requires extra circuitry in order to artificially drive the two inverters into this unnatural state. The two discrete transistors needed to do this makes the design require more than just logic gates to implement. Is this really necessary? I'll explore this in my suggestion below.
- They do correction as well, which they say is needed to calibrate for slight differences in the characteristics between the two inverters. This is done by adding compensating bias, which is usually based on the ratio of ones and zeros in the output stream. This scheme seems to be part of every "serious" random number generator. It seems wrong, but I'm not sure how to fix it. I talk about it in the next section.
I'm asking, really. It seems bad enough that the term "random number" is filled with contradiction, in that we're attempting to use numbers—which are inherently ordered—to represent randomness. To make matters worse, many random number generator schemes, if not all, are forced to include a seemingly inescapable scheme that imposes even more order on their outputs.
The bias function described in the second bullet above is an example of this. Some variation of this scheme is often seen in random number generators of all kinds. This one works by keeping the number of ones and zeros approximately even over an arbitrarily selected "large" number of samples
[1]. One way this is done is to simply count the ones and zeros that occur in some pre-determined window of samples, and to adjust the circuit a little so that it produces more of the state that is deemed to be too scarce.
This, in my opinion, is a
big problem regarding random number generation because it introduces order bias. Specifically, the constraint that adds order-bias is the enforced assumption that the number of zeros and ones WILL be approximately equal over 'N' samples — where 'N' must (by necessity) be something less than infinity.
I could be wrong about this, but it is my understanding that there is nothing in true, natural, randomness that says it can't get
way out of balance over huge numbers of samples, representing long periods of time. In fact, it seems to be the nature of actual randomness that such states will occasionally occur. In other words, with natural randomness, out-of-balance states are inevitable. With compensation schemes that artificially try to keep the number of ones and zeros balanced over a pre-selected number of samples (or time-period) such a state of characteristic imbalance can never occur.
Why can't we do something like this instead?
[2]
A = /B
B = /C
C = (/A.X)+(A./X)
X is the control signal. Pulse it high (to 1) for a very short time to put the circuit into indeterminacy. Bring it low to make it stable again.
In this case, we're gleaning randomness from
temporal jitter in the gate delays when a contentious inverter is removed from the chain, rather than from jitter in noise as contending inverters settle out of analog range. . .
This immediately causes a cute name for the circuit to spring to mind, "Musical Gates"
Here's the schematic representation for the above circuit.
| Musical Gates — A schematic diagram of the above circuit. When X=1, a third inverter is added to the ring, causing the entire circuit to oscillate at gate-delay speeds. | |
The above circuit was scratched out quickly in a blog response at IEEE, but it can be simplified a little bit. That is, a single inverter can be in contention with itself, and a second inverter can be ADDED into the circuit (controlled by X) in order to stabilize it.
Like this:
A = /( (A./X)+(/A.X) )
Note here that unlike the above circuit, this one is placed in indeterminacy by making X=0 (not 1). It is stable as long as X is held at 1. Again, this is the opposite of the above control. Here's the circuit diagram.
| One Way to Slightly Simplify Musical Gates — This also shows that any number of inverters can be included in the ring. It is really about making a circuit that can select between an odd number of inverters (indeterminate), and an even number of inverters (stable) in the ring. | |
As stated in the caption, this also points out that more inverters may be just as easily added to the ring. The actual concept is simply the ability to switch between having an odd number of inverters in the ring for indeterminate state, and an even number in the ring for stable state.
Well... Theoretically, you can probably say this is true digital, since it is is composed only of logic gates and it is based on capturing randomness in
temporal jitter as the gate delays settle out. That
may be enough to say it is technically all digital. In practice, however, while this circuit is in indeterminacy state, it will be spending a huge fraction of its time in the slew-states (i.e., in the transitions from high to low, and low to high).
Will it work? I can't see any problem with this circuit, but, of course, I haven't yet fully tested it.
|
Post Script: It seems that something very similar to this has already been done (circa 2006 ?). I probably should have done a search before spending the time breadboarding it. The circuit described here has some practical operational differences as compared to the circuits described in the existing literature (their avoidance of split infinitives for example); but it is, essentially, the same idea.
This blog entry will be kept as a place to gather and maintain information and resources on the subject of randomness. I'll probably continue breadboarding the circuit also. Who knows? It may still be a little fun, even though it's a re-invented wheel.
|
|
|
. . . . . . .
Still Needs Auto-Calibration?
It produces random (unpredictable) sequences of ones and zeros but it seems to be easily biased, producing more zeros than ones when tested. The "more zeros" bias seems to be caused by the logic probe (my old oscilloscope has smoked out).
I haven't checked the output sequences in a randomness checker; it has just been an eyeballing conclusion. That is, you're lucky to get three ones in a row, and even luckier if you get 4 ones in a row, but you'll see sequences of 3 and 4 zeros on a regular basis. You'll also see groups of 6 zeros (one in 64 odds) more than once in a sample of a few hundred.
How do I know the observed "more-zeros" bias is being added by the probe and not inherent in the circuit? If I move the the probe to the the other side of the inverter (the input), the recorded "more zeros" is still seen on this non-inverted stream. Got that? The problem moves with the probe.
. . . . . . .
Too Soon
There are a number of problems with my test at this point. I've already mentioned that I haven't run the sequences produced through a randomness tester. Perhaps I just got a naturally out-of-balance sequence (lucky me). The bias "seems" real to me though, just eyeballing it.
It's not really clear, at this point, if the problem is the probe's input impedance or its input capacitance. Timing, via gate delays, is the mechanism by which we are gleaning randomness here. In that case, the "zero bias" added by the probe may be more a function of its capacitance than of its impedance.
As stated, the oscilloscope is down (and probably out), so these observations are through a glass darkly using only a logic probe. Finally, I used mixed technologies to construct the current circuit. Standard TTL was used for the AND and OR gates, but LS (low power) TTL was used for the inverters. The inability to deal with the probe capacitance may also be a function of the lower output-driving capability of the LS. In any case, I'm waiting for some CMOS parts to arrive, and will rebuild the whole thing when they do.
. . . . . . .
So, will it work?
The bias issues are disappointing because they hint that compensation of some form may still be required. It is entirely digital though, and made with
only logic gates. It is promising that it is producing ones and zeros regularly and un-predictably (even if probe-biased), but it is still too early to tell if there's a way to get rid of the need for compensation.
Like any idea, until it is subjected to consistent and repeatable experimentation and observation, it is just a thought, and nothing more. Well, it also presents a fun challenge for anyone, if there is an overlooked flaw to be found.
=======
Notes:
[1] It's not always based on an even number of ones and zeros in a sample-window, sometimes it is a set of mathematical calculations that ensure that the numbers produced, over a large number of samples, are spread evenly over the range of possible numbers. In either case, it has the same problem. If the sample is not infinity (or approaching infinity) the enforced evenness is itself a form of order.
[2] The extra variables (B and C) are superfluous. They were just helpful to me when thinking about the problem. It could have been expressed in terms of only the output and the control input (A and X):
A = //(A./X+/A.X)
Finally managed to slosh enough junk around to clear the table in the foreground and then clean off the old workbench. The last time it was out from under a quarter inch of dust you needed a t-square to produce PCB layouts (see it there). The old scope sm
Tracked: Sep 10, 00:59