Circuitry for minimizing auto-correlation and bias in a random number generator

• US 4,355,366 A
• Filed: 11/28/1980
• Issued: 10/19/1982
• Est. Priority Date: 11/28/1980
• Status: Expired due to Term

• Current Assignee: NCR Corporation
• Original Assignee: NCR Corporation
• Inventors: Porter, Sigmund N.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US06/210,989
• Time in Patent Office: 690 Days
• Field of Search: 364/717, 331/78, 178/22.15
• US Class Current: 708/255
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes
• CPC Class Codes: H03K 3/84 Generating pulses having a predetermined statistical distribution of a parameter, e.g. random pulse generators

Abstract

A random number generator that provides bits at its output that are neither biased nor periodic. The generator includes a noise generator and sampling register that provide serial, randomly varying bits. A circuit within the generator for reducing auto-correlation or periodicity discards certain ones of the randomly varying bits, and includes a first shift register for receiving and storing the randomly varying bits and a second register for receiving in parallel and storing only a portion of the randomly varying bits from the first register. In order to eliminate bias, EXCLUSIVE OR gates are connected between the first and second registers in order to logically combine the randomly varying bits received by the second register with previous bits stored in the second register.

Claims

1. A random number generator having an output for providing random numbers, comprising:

means for providing successive and randomly varying bits; and

means for receiving the randomly varying bits and minimizing auto-correlation in the randomly varying bits, including means for discarding certain ones of the randomly varying bits so that random numbers provided at the output of said random number generator do not include the discarded bits, said means for discarding comprising;

a first shift register clocked by a first clock signal in order to serially receive and store the randomly varying bits; and

a second register connected to said first shift register in order to receive in parallel the bits stored by said first register, said second register clocked by a signal other than the first clock signal so that said second register receives and stores only a portion of the bits received by said first register, with said second register providing the portion of the bits to the output of said random number generator.

2. The random number generator of claim 1, further comprising circuit means for minimizing bias in the randomly varying bits, including logic gate means having first input means connected for receiving the bits stored in said first register, second input means connected for receiving the bits stored in said second register, and output means connected for providing bits to said second register, said logic gate means logically combining the bits at said first input means and said second input means and providing the logically combined bits at said output means, so that the portion of the bits received by said second register from said first register are logically combined with the portion of the bis previously received by said second register before being received and stored in said second register.

3. In a random number generator, a circuit for minimizing auto-correlation in successive random bits, comprising:

first storage means for being clocked to serially receive the bits and to store a predetermined number of the bits, said first storage means having a plurality of stages, including a first stage and a last stage, each stage for storing one of the bits, with said first storage means discarding the one of the bits in the last stage when one of the bits is received in the first stage;

second storage means for storing the same predetermined number of bits and connected for receiving in parallel the bits stored in said first storage means; and

means connected to said second storage means for clocking said second storage means to receive the bits from said first storage means only after a number in excess of the predetermined number of bits have been serially received in said first storage means and at least one of the bits has been discarded in said first storage means.

4. The circuit of claim 3, wherein said first storage means comprises a first shift register and said second storage means comprises a second register, said first and second registers both having a plurality of stages.

5. The circuit of claim 4, wherein said means for clocking said second storage means comprises a first binary counter having an input connected for receiving the successive random bits, said first counter incremented by bits having one predetermined binary value, said first counter having an output connected for providing an enabling clock signal to said second register.

6. The circuit of claim 5, further comprising logic gate means connecting each stage of said first register to an associated stage in said second register, said logic gate means having one input connected to the output of one of the stages of said first register, having its output connected to the data input of the associated stage of said second register, and having its second input connected to the output of said second register, so that each bit received by said second register from said first register is logically combined with a previous bit stored in said second register.

7. The circuit of claim 6, further comprising a third register having a plurality of stages, each stage connected for receiving the bit stored in an associated one of the stages in said second register, and clocking circuitry for providing an enabling clocking signal to said third register so that the stages of said third register receive bits from said second register, with the bits stored in said second register repeatedly provided to and logically combined at said logic gate means prior to being received by said third register.

8. The circuit of claim 7, wherein said clocking circuitry includes a second counter having its input connected to the output of said first counter.

9. In a random number generator, a circuit for receiving randomly varying bits of a random number and reducing the bias of the randomly varying bits, the circuit comprising:

a plurality of EXCLUSIVE OR gates, each of said EXCLUSIVE OR gates having first and second inputs, and an output, with the first input for receiving one of the randomly varying bits; and

a register for storing the randomly varying bits from said EXCLUSIVE OR gates and having a plurality of stages, each stage associated with one of said EXCLUSIVE OR gates and having an input connected to the output of its associated EXCLUSIVE OR gate and an output connected to the second input of its associated EXCLUSIVE OR gate, so that the randomly varying bits are logically combined at said EXCLUSIVE OR gates with previous randomly varying bits stored in said register.