Many electronic systems and computerized processes use random data for various reasons. Cryptography requires random data for generating encryption and decryption keys. In the field of communications, spread spectrum communication systems rely on random data. In the audio and video fields, random data are used to generate white noise.
Unfortunately, the generation of random data is a troublesome task. Truly random data is difficult to generate from automated processes. Accordingly, linear feedback shift register (LFSR) circuits, computerized processes, and other techniques have been devised to form pseudorandom number generators. When operating properly, pseudorandom number generators produce data symbols that are sufficiently random for many purposes. When practically realizable pseudorandom number generators fail to produce sufficiently random data for a particular application, random number generators may be constructed which are responsive to various randomly occurring physical phenomenon, such as transistor characteristics.
Designers that incorporate random and pseudorandom number generators in their designs conventionally achieve only a low degree of confidence that the symbols being generated by a random or pseudorandom number generator are in fact sufficiently random. Those skilled in the art will appreciate that testing for sufficient randomness is a difficult task because there can be no specific "correct" or "incorrect" set of symbols if the symbols are more or less random.
Traditionally, randomness has been determined by performing extensive statistical testing, such as chi-squared tests, delta tests, and the like, on a sequence of generated symbols. Such tests cannot be performed in real time because they require a great amount of computational processing power. Accordingly, they work adequately to verify a random or pseudorandom number generator's design but are entirely inadequate for real time use, such as determining whether a component failure has occurred in a valid design or whether an external influence is causing insufficiently random symbols to be generated from an otherwise valid random or pseudorandom number generator design.
Those skilled in the art can easily devise circuits and processes that detect stuck-at-zero and stuck-at-one failure modes for random and pseudorandom number generators. However, the stuck-at-zero and stuck-at-one failure modes represent only a fraction of the likely failures which may cause generated symbols to become insufficiently random. A vast number of likely failure modes, particularly in pseudorandom number generators, cause short cycle patterns in a sequence of symbols. Short cycle patterns are arbitrary patterns having a relatively few symbols that sequentially repeat throughout a sequence of many symbols. Stuck-at-one and stuck-at-zero failure modes are short cycle patterns, but a vast number of other potential short cycle patterns are missed by simple tests for stuck-at-one and stuck-at-zero conditions.
USPTO Backgrounds
USPTO Backgrounds