Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2001-03-01
2004-07-06
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06760739
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to a system and method for generating a random digital data string. More particularly, the present invention relates to a system and method for generating a random digital data string based on a sampling source, which varies in frequency and phase, sampling an entropy source that also varies in frequency and phase, and additionally based on the principles of permutation and substitution.
2. Description of Related Art
Historically, randomizer circuits have been analog-based designs. Generally, such analog-based randomizer circuits include, for example, either a noisy diode, an operational amplifier in a specific feedback configuration, or some thermal noise source to provide a random signal. Unfortunately, such devices cannot be manufactured with sufficient precision, and thus do not allow for consistent circuit production.
Digital randomizer circuits were developed, at least in part, in response to the weaknesses of analog-based randomizer circuit designs. One such circuit, disclosed in U.S. Pat. No. 5,570,307, and having the same inventor as the instant application, is based on the metastable operability of flip-flops. Specifically, the design consists of a plurality of flip-flops that are forced to operate in a metastable state. The random, unpredictable nature of flip-flops operated in the metastable state being the primary source of random data blocks. More specifically, each flip-flop is coupled to a dedicated free-running oscillator that operates at a prime-number-based frequency. Each flip-flop also receives a common jitter clock signal, and therefore operates in a metastable state by intentionally violating either the flip-flop set-up or hold time margins of incoming data relative to the jitter clock, thus generating a random noise sequence. To further increase the entropy of the system, the flip-flop outputs are exclusively-ORed (XORed).
The above-described digital randomizer suffers various weakness. Namely, the oscillator frequencies can drift toward, and actually lock on to, one another. Additionally, as the size of the circuitry that makes up the randomizer decreases, the likelihood of sustaining, or even reaching a metastable state, significantly decreases. Thus, this prior design is not sufficiently robust.
Hence, there is a need in the art for a digital randomizer circuit that does not rely on the metastable operability of flip-flops. And more particularly, a digital randomizer that does not utilize oscillators that can lock on to each other, and that is sufficiently robust as circuit size decreases.
SUMMARY OF THE INVENTION
The present invention relates to a system and method for generating a random digital data string based on a sampling source, which varies in frequency and phase, sampling an entropy source that also varies in frequency and phase, and additionally based on the principles of permutation and substitution.
In one aspect of the present invention, the system includes a random number generation circuit and a data substitution circuit coupled to receive random data output from the random number generation circuit. A data permutation circuit is coupled to receive substituted random data output from the data substitution circuit. A data compression circuit is coupled to receive permuted and substituted random data output from the permutation circuit and output at least a portion of the indeterminate random data string. A plurality of variable frequency clocks, each operating at different clock frequencies, are selectively coupled to various of the circuits within the system.
In another aspect of the present invention, the method includes the steps of generating a first random number of a first predetermined bit length, and substituting the first random number with different data based upon the first random number. The substituted random data is then permuted. Thereafter, the permuted and substituted random data is compressed to form at least a portion of the indeterminate random data string.
REFERENCES:
patent: 3364308 (1968-01-01), Vasseur
patent: 4810975 (1989-03-01), Dias
patent: 4905176 (1990-02-01), Schulz
patent: 5297207 (1994-03-01), Degele
patent: 5420928 (1995-05-01), Aiello et al.
patent: 5515307 (1996-05-01), Aiello et al.
patent: 5570307 (1996-10-01), Takahashi
patent: 5615263 (1997-03-01), Takahashi
patent: 5724277 (1998-03-01), Nakagawa
patent: 5737252 (1998-04-01), Hollmann et al.
patent: 5963104 (1999-10-01), Buer
patent: 0 782 069 (1997-07-01), None
patent: 2 796 477 (2001-01-01), None
Atkins Robert D.
Corrent Corporation
Malzahn David H.
Quarles & Brady Streich & Lang LLP
LandOfFree
Pipelined digital randomizer based on permutation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pipelined digital randomizer based on permutation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined digital randomizer based on permutation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3250653