Security Enhanced Linux
What's New
Frequently Asked Questions
Background
Documents
License
Download
Participating
Mail List
Archives
Remaining Work
Contributors
Related Work
Press Releases
Information Assurance Research
NIARL In-house Research Areas
Mathematical Sciences Program
Sabbaticals
Computer & Information Sciences Research
Technology Transfer
Advanced Computing
Advanced Mathematics
Communications & Networking
Information Processing
Microelectronics
Other Technologies
Technology Fact Sheets
Publications
Related Links
|
Method of Generating Multiple Random Bit SequencesAliases:NoneTechnical Challenge:Stochastic neural networks and other statistical computing systems use thousands of random bit sequences. They are also massively parallel by their very nature, and thus benefit from being implemented using multiple parallel circuits, each with its own source of random bits. This usually requires a separate pseudo-random bit generator (PRBG) for each circuit. A single PRBG is often larger than the circuit it supplies, so a substantial amount of chip area is consumed by random bit production. Moreover, to ensure that their outputs are statistically uncorrelated, each PRBG must be designed using a different algorithm or a different starting value called a random seed. This adds complexity to the design and increases the size of hardware implementations.Description:This method uses only 2 pseudo-random bit generators for the entire system and each PRNG is smaller than the one used by other well-known methods Circuits are easily added or removed from the system without additional calculations, eliminating the need to keep track of random seeds, PRBG algorithms, tap combinations, or time shifts.Two pseudo-random bit generators produce bit sequences Rn and Rdn that repeat every S and T bits, respectively. The designer selects S and T such that they are relatively prime numbers and such that S > K and T > K, where K is equal to the total number of random bits used by the system during each clock cycle. To generate multiple random bit streams the m-the random bit sequence bm,n is created locally by the circuit that needs it according to the formula , where signifies modulo-2 addition. Rn and a delayed copy of Rdn are passed from circuit to circuit in a daisy-chain configuration. Demonstration Capability:A demonstration is available upon requestPotential Commercial Application(s):There are numerous applications that use random numbers and parallel processing, including Monte Carlo simulation, neural networks, and statistical optimization.Patent Status:Patent Application has been filed with USPTO.Reference Number: 1294If you are interested in exploring this technology further, please call 443-445-7159 or express your interest in writing to the: National Security Agency |
|
Date Posted: Jan 15, 2009 | Last Modified: Jan 15, 2009 | Last Reviewed: Jan 15 2009 |