Analog-to-digital conversion method of random number generation

• US 6,369,727 B1
• Filed: 12/17/1999
• Issued: 04/09/2002
• Est. Priority Date: 12/17/1999
• Status: Expired due to Fees

• Current Assignee: RNG Research
• Original Assignee: RNG Research
• Inventors: Vincze, Andrew J.
• Primary Examiner(s): JeanPierre, Peguy
• Assistant Examiner(s): Lauture, Joseph J
• Application Number:
  US09/466,580
• Time in Patent Office: 844 Days
• Field of Search: 341/118, 341/120, 341/143, 341/155, 708/250, 708/256, 364/746, 364/746.1, 463/22
• US Class Current: 341/131
• CPC Class Codes: G06J 1/00 Hybrid computing arrangements digitally-programmed analogue computers G06G7/06

Abstract

A random number generator (RNG) using an analog-to-digital (A/D) converter to convert random noise into digital samples which are transformed by a reductive mapping into uniformly distributed random numbers for output. The synchronous RNG may be integrated and is intended for use in all computer systems. A noise source provides random noise from electronic events involving quantum-mechanical uncertainty. A compressor amplifies noise by a level-dependent gain to provide random noise, v (t), with a stabilized standard deviation and allows the output level of a noise source to vary without affecting the output of an RNG. An n-bit A/D converter converts v (t) into a digital random variable, Y. An expedient test of an RNG is to compute the mean and standard deviation of Y. Correlation is precluded by minimizing antialiasing. An interface circuit reduces Y modulo-M, where constant M<<2ⁿ, and generates random numbers, from 0 to M−1, at the A/D converter sampling frequency.

Claims

1. A random number generator (RNG) comprising:

random noise source means for producing a random noise output;

analog-to-digital (A/D) converter means, coupled to said random noise source means, for converting said random noise output to a digital signal; and

reduction function means, coupled to said A/D converter means, for subjecting said digital signal to a reductive mapping for generating uniformly distributed random numbers.

2. An RNG as in claim 1 wherein said digital signals represent numbers and said reduction function means reductively maps the numbers in said digital signal to the numbers generated as uniformly distributed random numbers.

3. An RNG as in claim 1 wherein said random noise source means comprises:

a semiconductor P-N junction; and

means for applying a reverse-bias to said P-N junction for producing electronic noise as an output.

4. An RNG as in claim 3 further comprising:

amplifier means, coupled to said P-N junction, for outputting said electronic noise.

5. An RNG as in claim 1 wherein said A/D converter means comprises a sigma-delta A/D converter.

6. An RNG as in claim 1 wherein said A/D converter means comprises a track-and-hold buffer and a successive approximation register.

7. An RNG as in claim 1 further comprising:

compressor means, coupled between said random noise source means and said A/D converter means, for receiving said random noise output as an input and producing an approximately constant-level random noise output for input to said A/D converter.

8. An RNG as in claim 7 wherein said compressor means comprises:

controlled amplifier means for receiving said random noise output as an input and amplifying said input by a gain that is dependent on a control signal for producing an amplified output;

comparing means, including an error amplifier, coupled to said controlled amplifier means, for comparing said amplified output with a DC reference and producing an error signal; and

means, coupled to said comparing means, for conditioning said error signal to produce said control signal for controlling the gain of said controlled amplifier means for rendering constant the level of said amplified output.

9. An RNG as in claim 7 wherein said compressor means comprises:

controlled attenuation means for receiving said random noise output as an input and attenuating said input by a factor that is dependent on a control signal for producing an attenuated output;

comparing means, including an error amplifier, coupled to said controlled attenuation means, for comparing said attenuated output with a DC reference and producing an error signal; and

means, coupled to said comparing means, for conditioning said error signal to produce said control signal for controlling the attenuation factor of said controlled attenuation means for rendering constant the level of said attenuated output.

10. An RNG as in claim 7 wherein said compressor means comprises:

voltage controlled amplifier means for receiving said random noise output as an input and producing an output dependent on a control signal;

comparing means, including an error amplifier, coupled to said voltage controlled amplifier means, for comparing said output with a DC reference and producing an error signal; and

means, coupled to said comparing means, for conditioning said error signal to produce said control signal for controlling the output of said voltage controlled amplifier means for rendering constant the level of said output.

11. A method for generating a uniformly distributed random variable comprising the steps of:

providing a random noise source for producing a first continuous random variable;

coupling said random noise source to an analog-to-digital (A/D) converter;

using said A/D converter to restrict said first continuous random variable to discrete values for producing a first discrete random variable Y;

selecting a reduction function that maps all N number of possible values of Y to a lesser M number of particular values; and

using said function to transform Y to a second discrete random variable X, which random variable X is a uniformly distributed random variable.

12. The method of claim 11 wherein N is a finite number;

and each value of Y is an integral multiple of the same quantity.

13. The method of claim 11 wherein N is an integer power of two.

14. The method of claim 11 wherein M is an integer power of two.

15. The method of claim 11 wherein M is a divisor of N.

16. The method of claim 11 wherein said reduction function includes at least one modular reduction.

17. A system for generating uniformly distributed random numbers comprising:

a source of random noise for producing a random noise output;

analog-to-digital (A/D) converter means, coupled to said source, for converting said random noise output to a digital signal;

interface means, coupled to said A/D converter means, for controlling the output of said digital signal; and

digital computer means, coupled to said interface means, for utilizing said digital signal to obtain uniformly distributed random numbers.

18. A system as in claim 17 further comprising at least one amplifier coupled between said source and said A/D converter means.

19. A system as in claim 17 further comprising at least one compressor coupled between said source and said A/D converter means.

20. A system as in claim 17 wherein said interface means includes a reduction function for outputting the result of a reductive mapping of numbers represented by said digital signals.

21. A system as in claim 17 wherein said digital computer means includes a reduction function for transforming said digital signals to uniformly distributed random numbers.