Apparatus and method for generating random numbers

• US 5,966,313 A
• Filed: 07/10/1997
• Issued: 10/12/1999
• Est. Priority Date: 07/11/1996
• Status: Expired due to Fees

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Sakamoto, Hideki
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Nguyen, Nguyen X.
• Application Number:
  US08/890,985
• Time in Patent Office: 824 Days
• Field of Search: 307/201, 364/717, 364/602, 365/244, 380/46, 380/4, 380/30, 358/455, 331/78, 235/152, 340/172.5, 340/146.2
• US Class Current: 708/250
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators

Abstract

If a random number generated by a random-number generator is equal to or greater than a random number having a predetermined amplitude, a high-level comparison result signal is produced to cause an AND gate and an OR gate to apply clock pulses to the random-number generator, which updates the random number. Only random numbers whose amplitude is smaller than the predetermined amplitude are stored in a D-type flip-flop and outputted as generated random numbers. Since random numbers whose amplitude is smaller than the predetermined amplitude are selected from the random numbers that are outputted from the random-number generator, a random-number generating apparatus does not require a processing circuit, and may be of a relatively small circuit scale and can generate random numbers having a desired amplitude at all times and with no amplitude errors.

Claims

1. An apparatus operable in synchronization with clock pulses for generating random numbers of a predetermined length that are less than a predetermined number in response to a request signal, comprising:

a random-number generating circuit for generating a random number of the predetermined length in response to an operation pulse;

a comparator circuit for determining whether or not the generated random number is smaller than the predetermined number and outputting a comparison result signal; and

a logic circuit responsive to said request signal, said comparison result signal, and said clock pulses, for generating said operation pulse in response to said request signal and in response to said clock pulses if said generated random number is not smaller than said predetermined number.

2. An apparatus according to claim 1, wherein said random-number generating circuit comprises a polynomial counter comprising as many cascaded storage elements as bits in said random numbers of the predetermined length, for feeding a logic combination of outputs of said cascaded storage elements back to a first one of said cascaded storage elements.

3. An apparatus according to claim 2, wherein said logic circuit comprises:

an AND gate for outputting a logical AND result of an inverted logic level of said comparison result signal and said clock pulses; and

an OR gate for outputting a logical OR result of an output from said AND gate and said request signal.

4. An apparatus according to claim 1, wherein said logic circuit comprises:

an AND gate for outputting a logical AND result of an inverted logic level of said comparison result signal and said clock pulses; and

an OR gate for outputting a logical OR result of an output from said AND gate and said request signal.

5. An apparatus according to claim 1, further comprising a flip-flop connected to the random-number generating circuit and responsive to the request signal to store and output the random number generated by the random-number generating circuit.

6. An apparatus according to claim 5, wherein the random-number generating circuit is further responsive to a reset signal for initializing the random-number generating circuit.

7. An apparatus according to claim 6, wherein the logic circuit includes:

a first OR gate for outputting a logical OR result of an inverted logic level of the comparison result signal and the reset signal;

an AND gate for outputting a logical AND result of an output signal of the first OR gate and the clock pulses; and

a second OR gate for outputting a logical OR result of an output signal of the AND gate and the request signal,

wherein the operation pulse comprises an output signal of the second OR gate.

8. An apparatus for generating random numbers, comprising:

random-number generating means for generating a random number of a predetermined length in response to an operation pulse; and

means for determining whether or not the generated random number is smaller than a predetermined number and supplying said operation pulse to said random-number generating means depending on whether or not the generated random number is smaller than the predetermined number.

9. An apparatus according to claim 8, wherein said means for determining and supplying includes a comparator circuit, said comparator circuit comparing the generated random number with the predetermined number and outputting a low signal when the generated random number is smaller than the predetermined number and a high signal when the generated random number is equal to or greater than the predetermined number.

10. An apparatus according to claim 9, wherein said means for determining and supplying includes a logical circuit, said logical circuit receiving the low and high signals from the comparison circuit and outputting the operation pulse synchronously with clock pulses when a high signal is received from the comparison circuit.

11. An apparatus according to claim 10, wherein the random-number generating means is further responsive to a reset signal to produce an initial random number.

12. An apparatus according to claim 11, further comprising a flip-flop connected to the random-number generating means and responsive to a request signal to store and output the random number generated by the random-number generating circuit.

13. An apparatus according to claim 12, wherein the logical circuit includes:

a first OR gate for outputting a logical OR result of the low and high signals from the comparator circuit and the reset signal;

an AND gate for outputting a logical AND result of an output signal of the first OR gate and the clock pulses; and

a second OR gate for outputting a logical OR result of an output signal of the AND gate and the request signal,

wherein the operation pulse comprises an output signal of the second OR gate.

14. A method of generating random numbers, comprising the steps of:

generating a random number of a predetermined length;

determining whether or not the generated random number is smaller than a predetermined number; and

repeating said step of generating and said step of determining if said generated random number is not smaller than said predetermined number.

15. A method according to claim 14, further comprising the step of generating an operation pulse if said generated random number is not smaller than said predetermined number, wherein the step of generating the random number is initiated in response to the operation pulse.

16. A method according to claim 15, wherein the step of generating the random number includes the step of generating an initial random number in response to a reset signal.

17. A method according to claim 16, further comprising the step of generating the operation pulse in response to a request signal.

18. A method according to claim 17, further comprising the step of outputting the generated random number in response to the request signal.