Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] The Digital Random Bit Generator

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Oct 31, 2011
    • 0 Attachment
      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.
      Initially when both transistors cause full voltage at both Nodes A and B. Intel had to use special inverters (NOT gates) that can withstand not being able to invert at this point. A clock signal slowly turns off the transistors and the inverters go to work reducing A and B to an equilibrium of half voltage each.

      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
    Your message has been successfully submitted and would be delivered to recipients shortly.