Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-03-06
2003-10-07
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S251000
Reexamination Certificate
active
06631390
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to random number generation, and more particularly, to a method and apparatus for generating random numbers using flip-flop meta-stability.
BACKGROUND OF THE INVENTION
Flip-flops and latches are widely used in computers and other electronic devices, for example, as sampling, counting and storage elements. A number of flip-flop types have been developed, such as D-type flip-flops (“data”), R-S latches (“reset and set”), J-K flip-flops (having J and K inputs) and T flip-flops (having only one input). A D-type flip-flop, for example, is a clocked flip-flop whose output is delayed by one clock pulse.
A conventional R-S latch
100
is shown in FIG.
1
A. As in
FIG. 1A
, the R-S latch
100
is comprised of two NOR gates
110
and
120
. The outputs of the two NOR gates
110
,
120
are cross-connected to a respective input of the opposite NOR gate. Thus, NOR gate
110
receives the output of NOR gate
120
and a reset signal, R, as inputs. Likewise, NOR gate
120
receives the output of NOR gate
110
and the set signal, S, as inputs.
More recently, the simple latches shown in
FIG. 1A
have been replaced by edge-triggered flip-flops, such as the D-type flip-flop
150
is shown in FIG.
1
B. Edge-triggered flip-flops change state based on a rising or falling clock edge and a data input. A conventional D-type flip-flop
150
is shown in FIG.
1
B. Such D-type flip-flops are often used to detect the logic state of an asynchronous digital signal having an unpredictable timing relative to the clock signal. A synchronous signal is applied to the clock input, CLK, of the flip-flop
150
, while a digital logic level of the asynchronous signal to be detected is directed to the D input. The detected signal is then produced on the Q output line. Thereafter, the flip-flop
150
simply changes state whenever the input signal at the D input is changed (so long as the reset signal is tied permanently to ground).
It is well-known that the latches
100
shown in
FIG. 1A
are susceptible to meta-stability. For a detailed discussion of meta-stability, see, for example, Application Note, A Meta-Stability Primer, AN219, Philips Semiconductors (Nov. 15, 1989), incorporated by reference herein. Generally, meta-stability can occur when both inputs to a latch
100
are set at a high logic value (“11”), and are then reset to a low logic value (“00”). Under these conditions, the latch outputs can oscillate unpredictably in a statistically known manner. In theory, the latch
100
can oscillate indefinitely. In practice, however, the latch
100
will randomly shift and arrive at a random output value of either logic low or high. Typically, these meta-stable values are subsequently detected by other circuitry in a given application and can be interpreted as different logic level states.
In addition, the edge-triggered flip-flop
150
shown in
FIG. 1B
can become meta-stable when the setup or hold times of the flip-flop are violated. Edge-triggered flip-flops
150
are susceptible to meta-stability because inside every edge-triggered flip-flop
150
there is a latch
100
being fed by the edge detection circuitry. If the setup or hold times are violated then the internal latch
100
will observe inputs that can trigger the meta-stable state.
For most applications, especially those requiring reliable detection of the logic level state of an asynchronous signal, such meta-stable behavior is undesirable. Thus, a number of techniques have been proposed or suggested to provide flip-flops that are not susceptible to meta-stability. Philips Semiconductors of Sunnyvale, Calif., for example, provides a family of integrated circuits that exhibit meta-stable immune characteristics. See, for example, Application Note, Synchronizing and Clock Driving Solutions—Using the 74F50XXX Family, AN220, Philips Semiconductors (Sep., 1989), incorporated by reference herein. In addition, U.S. Pat. No. 5,365,122, issued to Rackley, discloses a meta-stable resistant R-S latch.
Many applications and electronic devices require random numbers, including games of chance, such as poker, roulette, and slot machines. In particular, numerous cryptographic algorithms and protocols depend on a non-predictable source of random numbers to implement secure electronic communications and the like. There are numerous devices available for generating a random number. A number of factors are important in evaluating a random number generator. For example, it is desirable that the random number generator can generate every possible permutation in the designated range of numbers. In addition, the random number generator should not be biased and should generate any given number with the same probability as any other number. Moreover, the random number generator should generate random numbers that cannot be predicted, irrespective of the size of the collection of previous results. Thus, the random numbers should be completely unpredictable and non-susceptible to outside influences. Therefore, ideal random number generators have used forces in nature, such as radioactive decay or analog noise in zener diodes, as the source of randomness. These devices are essentially perfect in that natural forces can neither be predicted nor influenced.
Many computer-generated random numbers are easily predictable, thus leading to the failure of secure systems or games of chance. Hardware-based random number generators have typically been constructed using analog devices that make integration on digital integrated circuits difficult. In addition, they have often been temperamental in terms of reacting to noise in power supplies and local electronic noise in computer systems. Thus, such generators have not been cost effective for implementation in many systems, such as smart cards or typical personal computers.
A need therefore exists for a method and apparatus for generating random numbers that can utilize only digital technology and consists of very few gates. This will allow easy integration of the random number generator into any product that could benefit from it.
SUMMARY OF THE INVENTION
Generally, a method and apparatus are disclosed for generating random numbers using the meta-stable behavior of flip-FLOPS. According to a first embodiment of the invention, a flip-flop is clocked with an input that deliberately violates the setup or hold times (or both) of the flip-flop to ensure meta-stable behavior. The meta-stable operation of the flip-flop provides a mechanism for generating random numbers.
The input to the flip-flop causes the meta-stable output of the flip-flop to be asynchronous with respect to the clock source. Thus, according to another aspect of the invention, a well-known synchronizing circuit is disclosed to synchronize the meta-stable output of the flip-flop with the clock source.
The synchronized output of the flip-flop is compared to an input waveform to determine if the output signal does not match the input signal, indicating a meta-stable state. When a meta-stable event is detected, an output bit is provided as a random bit.
According to a second embodiment of the invention, the time delay between meta-stable events can be used for the generation of a random number. While the first embodiment assumed that the meta-stable state will produce mistakes of ones or zeroes with an even distribution, a third embodiment assumes that meta-stability occurs more frequently with one binary value (either zero or one) for a given class of flip-flops. The third embodiment obtains an even random number distribution by “marking” half of the zeroes as “ones” and the other half of the zeroes as “zeroes.” In addition, half of the ones are marked as “ones” and the other half are marked as “zeroes”. Thus, irrespective of the ratio of mistakes made in the zero state or the one state, the distribution of random output bits will remain even.
A fourth and fifth embodiment of the invention account for process variations, such as voltage or temperature, that affect the ability of a flip-flop to become meta-stable on a regular
Do Chat C.
Goodman Edward W.
Ngo Chuong Dinh
LandOfFree
Method and apparatus for generating random numbers using... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating random numbers using..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating random numbers using... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3173118