[Computational Complexity] The Digital Random Bit Generator
- I started this month asking about the nature of randomness and how we generate it for our computers. Let me end the month talking about Intel's clever new digital approach to creating random bits.
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.
Posted By Lance Fortnow to Computational Complexity at 10/31/2011 08:40:00 AM