Intel chips used to have an analog random bit generator based on noise in the circuits. But improved circuits reduced the noise limiting the effectiveness of these generators.
In the September IEEE Spectrum, Intel Architects Greg Taylor and George Cox give an overview of a digital random bit generator will sit in future Intel chips. The article is a short and fun read.
The heart of the article describe a simple digital circuit.
The magic now happens. This isn't a stable equilibrium so even the slightest noise quickly drives one of the nodes to full voltage and the other to no voltage. Which node goes to one depends on the direction of the noise and that's how you get your random bit.
Taylor and Cox find an idea that they might have sketched on a napkin and yet gives an incredible simple and elegant solution to an important problem. This is why I love computer science.
Just to play Devil's Advocate.
ReplyDeleteThe circuit is NOT a digital circuit, or at least not a well-defined one. A digital circuit would have "undefined" output.
It is exactly because digital circuits are implemented by "analog" devices that the circuit works. In fact, as the paper points out, the actual circuit contains an analog amplifier that balances out the slight differences in the two inverters -- without this extra device, the circuit would produce biased bits.
Of course, the generator is a great idea.
All of this reinforces Lance's statement that CS is wonderful. In part it is wonderful because once you look at a beautiful simple idea, it turns out that it is not quite that simple. In fact, you have to look at your basic abstractions, and, in this case, the idea comes from looking at the implementation of those abstractions. An inverter is actually a kind of analog amplifier. I'm willing to bet that it was the insight from the behavior of this "physical layer" underneath the digital circuit (plus the knowledge of astable multivibrators, a trick from the 1910s, standard EE fare) that inspired the engineers.
So I would add to the charms of CS the possibility (need?) to reason at several levels of abstraction simultaneously, and the use of techniques and insights from many different disciplines.
A wonderful article on this topic is Harold Stephen Black's "Inventing the negative feedback amplifier," IEEE Spectrum (Dec. 1977): 54-60 (this article regrettably is paywall-restricted).
ReplyDeleteBlack's idea of using negative feedback as the basis for stable high-gain amplification is a sterling example of an idea that Dick Lipton calls "a burning arrow."
It is great that we will have true random numbers in our next PCs, but not even the use of metastability is new: we at Philips Research published and patented it 10 years ago. Different versions of the stabilizing negative feedback for unbiasing the circuit have also been patented at the same time.
ReplyDeleteRegardless of the IP issues, what appears to be noise for the circuit may not be random in real life systems, like PCs. Other on-chip components, the power supply, hard disk etc. produce predictable interference, which reduces or removes the randomness.