Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1998-12-28
2001-05-29
Ngo, Chuong Dinh (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06240432
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
This invention relates to integrated circuits and in particular random number generators.
2. Description of Related Art
Random number generating circuits are well known. The most common of these circuits are based on the noise property of a biased semiconductor device. Some circuits use oscillators and rely on the natural variation in the frequency of slow oscillators to control the sampling of faster oscillators.
In U.S. Pat. No. 5,706,218 (Hoffman) a single, slow voltage controlled oscillator receives a noise input and controls the sampling of a set of ring oscillators. A circuit is used at the output of each ring oscillator to ensure that there is a near even distribution of logical ones and zeros in the random numbers. In U.S. Pat. No. 5,596,617 (Wolfe et al.) a feed back shift register of N stages has exclusive OR (XOR) circuits in the feedback logic and a gated clock which produces one blocked clock pulse in 2
n
clock pulses. In U.S. Pat. No. 5,327,365 (Fujisaki et al.) a parent processor in a parallel processor generates random number initial values and distributed the initial values to child processor elements which conduct processing to generate random numbers. In U.S. Pat. No. 4,905,176 (Schultz) a random number generator is disclosed which is based upon low frequency sampling of the output of a pseudo-random number generator that operates at a varying frequency from a free running ring oscillator. In U.S. Pat. No. 4,799,259 (Ogrodski) an array of oscillators operating at different frequencies is used as an input to an XOR network. The XOR network provides an output signal to a clocked D-type flip flop which samples the state of the random output signal from the XOR network. In U.S. Pat. No. 4,641,102 (Coulthart et al.) a five state ring counter is gated to a set of XOR circuits interposed between stages of a five stage shift register connected as a feedback shift register. A D-type flip flop with a low frequency clock and a high frequency data square wave controls the gating of the five stage ring counter to the set of XOR circuits.
Random number generators are useful in applications such as Smart Cards. It is therefore a requirement that random number generators be able to put into integrated circuits and utilize a relatively few components. It is also necessary that the output of the random number generator not be deterministic with a relatively short period as is the case with a simple linear feedback shift register where the feedback is XORed with certain bits in the shift register.
SUMMARY OF THE INVENTION
One objective of this invention is to provide a random number generator circuit that creates a clocked output in response to a clock signal and using relatively few components. Another objective of this invention is to provide a random number generator circuit for use in integrated circuit devices.
In this invention a circuit for generating a random bit sequence utilizes a linear feedback shift register (LFSR) and a set of ring oscillators. The LFSR has XOR circuites in the feedback to randomize the feedback signal and XOR circuits between each stage of the LFSR to randomize the signals between stages. The XOR circuits in the feedback circuit connect to outputs of selected stages of the LFSR, and the XOR circuits between stages are each connected to a different ring oscillator. The frequencies of the ring oscillators are set to be at a higher frequency than the frequency of the clock used to drive the LFSR and at a frequency different than each other.
The frequency of each ring oscillator connected to the XOR circuits between stages of the LFSR is set by adjusting capacitors in the circuit and by changing the size of the transistors. The period of the frequency oscillation is set to be an irrational number that is not repeated among the ring oscillators to avoid cyclic repetition and maximize the randomness of the random number generator. An alternative to using an irrational number for the period of oscillation is to set the frequency of each oscillator to be relatively primal with each other. In that way the period of oscillation will not be a multiple of any other frequency and will not have a common divider other than one.
REFERENCES:
patent: 4641102 (1987-02-01), Coulthart et al.
patent: 4785410 (1988-11-01), Hamatsu et al.
patent: 4799259 (1989-01-01), Ogrodski
patent: 4855690 (1989-08-01), Dias
patent: 4905176 (1990-02-01), Schutz
patent: 5327365 (1994-07-01), Fujisaki et al.
patent: 5596617 (1997-01-01), Wolf et al.
patent: 5706218 (1998-01-01), Hoffman
patent: 5867409 (1999-02-01), Nozuyama
Chuang Wei-Tong
Hsu Sandy C.
Ackerman Stephen B.
Ngo Chuong Dinh
Saile George O.
Vanguard International Semiconductor Corporation
LandOfFree
Enhanced random number generator does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced random number generator, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced random number generator will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2445742