Pseudo random number generator apparatus

• US 4,161,041 A
• Filed: 10/06/1978
• Issued: 07/10/1979
• Est. Priority Date: 10/06/1978
• Status: Expired due to Term

• Current Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Original Assignee: United States Of America As Represented By The Secretary Of The Air Force
• Inventors: Moulds, Clinton W. III, Butler, Eric W.
• Primary Examiner(s): Fears, Terrell W.
• Application Number:
  US05/949,190
• Time in Patent Office: 277 Days
• Field of Search: 365/244, 365/78, 365/73, 365/76, 365/77
• US Class Current: 365/244
• CPC Class Codes: G06F 2207/581 Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
• CPC Class Codes: G06F 2207/583 Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register

Abstract

An improved pseudo random number generator apparatus utilizing a programmable read only memory to reduce autocorrelation magnitudes by mapping the maximal length shift register states into the final output states.

Claims

1. A pseudo random number generator apparatus comprising in combination:

a shift register having a predetermined bit length, said shift register having a clock input and a data input, said shift register having a plurality of output states, said shift register receiving a clock signal and a data signal, said shift register shifting said data signals to said plurality of output states,

an exclusive or gate having a predetermined number of input lines and an output line, said output line being connected to said data input of said shift register, each line of said predetermined number of input lines being randomly connected to a single line of said plurality of output states of said shift register, and,

a programmable read only memory connected to (n-1) of said plurality of output states of said shift register wherein n is equal to number of said predetermined bit length, said programmable read only memory have a plurality of output lines, said programmable read only memory assigning addresses to each integer appearing on said plurality of output lines, said programmable read only memory providing a random number on said plurality of output lines.

2. An apparatus as described in claim 1 wherein metatreptic mapping by said programmable read only memory of said plurality of output states is utilized, said programmable read only memory assigning addresses in the following sequence:

addresses 0 to N-1 are assigned to states N to 1, addresses N to 2N-1 are assigned to states 1 to N, addresses 2N to 3N-1 to states N to 1, addresses 3N to 4N-1 to states 1 to N et sequens.

3. An apparatus as described in claim 1 wherein random mapping is utilized by said programmable read only memory to provide a pseudo random sequence of M=2^m where m equals the number of bits from said shift register and M equals the number of members in the random sequence.

4. An apparatus as described in claim 1 wherein said plurality of output states are equal to the number of said predetermined bit length.

5. An apparatus as described in claim 1 wherein said predetermined bit length equals seven.

6. An apparatus as described in claim 1 wherein said predetermined number of input lines equal two.

7. An apparatus as described in claim 1 wherein said plurality of output lines from said programmable read only memory equal three.