Method and apparatus for generating pseudo-random numbers

• US 5,258,936 A
• Filed: 05/10/1993
• Issued: 11/02/1993
• Est. Priority Date: 08/05/1992
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Gallup, Michael G., Goke, L. Rodney
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/058,836
• Time in Patent Office: 176 Days
• Field of Search: 364/717, 364/715.09, 380/46
• US Class Current: 708/254
• 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/584 using finite field arithmetic, e.g. using a linear feedback shift register

Abstract

A method and apparatus for generating pseudo-random numbers. A programmably selectable MASK value determines the polynomial to be used to generate the pseudo-random numbers. The MASK value can be changed while pseudo-random numbers are being generated in order to increase the run rate and improve the randomness of the sequence of pseudo-random numbers being generated. A programmably selectable SEED value is also used. The initial SEED value is used to generate the first pseudo-random number. The first pseudo-random number is then used as the NEW SEED value to generate the second pseudo-random number, and so on.

Claims

1. An apparatus for generating pseudo-random numbers, comprising:

a first circuit which logically combines a first binary value and a second binary value to produce an intermediate binary value; and

a second circuit which is coupled to said first circuit, which receives the intermediate binary value from said first circuit, and which produces a binary bit which has a first logic state if the intermediate binary value contains an odd number of ones and which has a second logic state if the intermediate binary value contains an even number of ones, said second circuit using the binary bit to determine a bit of a pseudo-random number.

2. An apparatus as in claim 1, wherein said first circuit performs a logical AND operation using the first binary value and the second binary value as operands.

3. An apparatus as in claim 1, wherein the binary bit is a most significant bit of the pseudo-random number.

4. An apparatus as in claim 1, wherein said second circuit comprises:

a ones-tally circuit.

5. An apparatus as in claim 1, wherein said second circuit comprises:

a shifting circuit for shifting the first binary value.

6. An apparatus as in claim 5, further comprising:

control circuitry, coupled to said shifting circuit, for selecting between a shift operation and a no-shift operation.

7. An apparatus as in claim 6, further comprising:

a first storage circuit for storing the first binary value, said first storage circuit being coupled to said first circuit.

8. An apparatus as in claim 7, further comprising:

a second storage circuit for storing the second binary value, said second storage circuit being coupled to said first circuit.

9. An apparatus as in claim 8, wherein said control circuitry also controls read accesses and write accesses to said first storage circuit and to said second storage circuit.

10. An apparatus as in claim 9, wherein said second circuit produces the pseudo-random number by shifting each bit of the first binary value by one bit and by shifting in the binary bit as the most significant bit of the pseudo-random number.

11. An apparatus as in claim 10, wherein the pseudo-random number is also used as a next first binary value which is logically combined with the second binary value.

12. A method for generating a pseudo-random number value in a data processing system, the data processing system having a plurality of registers and having a circuit for performing a logical combination function coupled to a circuit for producing a control signal, the method comprising the steps of:

transferring, from a first one of the plurality of registers to a first bus, a first plurality of electrical signals which represent a first value;

transferring, from a second one of the plurality of registers to a second bus, a second plurality of electrical signals which represent a second value;

logically combining the first plurality of electrical signals which represent the first value and the second plurality of electrical signals which represent a second value to produce an intermediate value;

placing the control signal in a first logic state if a number of ones in a binary representation of the intermediate value is odd; and

generating a pseudo-random number value based upon the first value and the control signal.

13. The method according to claim 12, wherein said step of logically combining further comprises the step of:

performing a logical AND operation.

14. The method according to claim 12, further comprising the step of:

placing the control signal in a second logic state if the number of ones in a binary representation of the intermediate value is even.

15. The method according to claim 12, wherein said step of generating a pseudo-random number value further comprises the step of:

using the control signal to determine a logic state of a bit of the pseudo-random number value.

16. The method according to claim 15, wherein the bit of the pseudo-random number value is a most significant bit.

17. The method according to claim 15, wherein said step of generating a pseudo-random number value further comprises the step of:

shifting the first value by one bit place.

18. The method according to claim 12, further comprising the steps of:

storing an initial first value in the first one of the plurality of registers; and

storing an initial second value in the second one of the plurality of registers.

19. The method according to claim 12, further comprising the step of:

repeating said step of logically combining, said step of placing the control signal in the first logic state, and said step of generating a pseudo-random number value using a previous pseudo-random number value as the first value.

20. The method according to claim 12, wherein the method is initiated by decoding a single instruction.

21. The method according to claim 12, wherein the first value is a pseudo-random number.

22. A method for operating a digital data processor comprising the steps of:

decoding an instruction; and

performing, in response to said decoding of the instruction, the steps of;

1) retrieving a first value from a first storage circuit;

2) retrieving a second value from a second storage circuit;

3) logically combining the first value and the second value to produce an intermediate value;

4) placing a binary bit in a first logic state if a number of ones in a binary representation of the intermediate value is odd; and

5) generating a pseudo-random number based upon the first value and the binary bit.

23. The method according to claim 22, wherein said step of logically combining comprises the step of:

performing a logical AND operation.

24. The method according to claim 22, wherein said step of generating a pseudo-random number comprises the step of:

using the binary bit as one bit of the pseudo-random number.

25. The method according to claim 24, wherein a most significant bit of the pseudo-random number is the binary bit.

26. An apparatus for generating pseudo-random numbers, comprising:

first storage circuit for storing a first binary value;

second storage circuit for storing a second binary value;

ANDing circuit for logically ANDing the first binary value and the second binary value to produce an intermediate binary value, said ANDing circuit being coupled to said first storage circuit and said second storage circuit; and

logic circuit for receiving the intermediate binary value from said ANDing circuit and for placing a binary bit in a first logic state if the intermediate binary value contains an odd number of ones, said logic circuit using the first binary value and the binary bit to generate a pseudo-random number.

27. An apparatus for generating a pseudo-random number, comprising:

a storage circuit for storing a previously generated pseudo-random number;

a programmable register circuit for storing a mask value; and

circuitry, coupled to said storage circuit for receiving the previously generated pseudo-random number and coupled to said programmable register circuit for receiving the mask value, said circuitry using the mask value to select which bits of the previously generated pseudo-random number are masked, said circuitry generating the pseudo-random number based upon the previously generated pseudo-random number and the mask value.

28. An apparatus as in claim 27, wherein said circuitry comprises:

an arithmetic logic unit.

29. An apparatus as in claim 27, wherein the pseudo-random number is generated during execution of an instruction.

30. An apparatus as in claim 27, wherein said storage circuit is user programmable.