Method and apparatus for generating numbers

• US 6,751,639 B2
• Filed: 12/12/2000
• Issued: 06/15/2004
• Est. Priority Date: 12/20/1999
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Szajnowski, Wieslaw Jerzy
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/734,181
• Publication Number:
  US 20020035586A1
• Time in Patent Office: 1,281 Days
• Field of Search: 708/250, 708/255
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/588 Random number generators, i.e. based on natural stochastic processes

Abstract

A non-repeating sequence of numbers having a substantially uniform distribution is obtained from a shift register whose contents are shifted, with the shifted digits being replaced by digits from a continuous sequence. The contents of the shift register are also replaced by their complement in dependence for the value of the most significant bit, so that the operations performed on the contents are represented by a tent map, thereby providing uniform distribution of the numbers. A randomising subsystem can be used to convert the output sequence into a random sequence.

Claims

1. A method of generating a non-repeating sequence of numbers having a substantially uniform distribution, the method comprising:

shifting digits out of a shift register;

using successive digits from a continuous sequence thereof to replace said digits shifted out of the shift register; and

using the contents of at least one stage of the shift register to control whether the contents of the shift register are replaced by their complement, so that the shift register has changing contents which can be used to derive said non-repeating sequence.

2. The method as claimed in claim 1, wherein each number of the non-repeating sequence is derived from N stages of the shift register, wherein N is an integer greater than 1.

3. The method as claimed in claim 2, wherein the shift register has N+X stages, wherein X is an integer of one or more.

4. The method as claimed in claim 3, wherein the N stages of the shift register from which each number is derived excludes at least the least significant stage of the shift register.

5. The method of claim 1, wherein the contents of the most significant stage of the shift register is used to control whether the contents of the shift register are replaced by their complement.

6. The method of claim 1, wherein the operations of shifting the contents of the shift register and selectively replacing the contents by their complement are such as to cause alternate stretching and folding of the contents.

7. The method of claim 1, wherein the operations of shifting the contents of the shift register and selectively replacing the contents by their complement are such that the shift register contents are altered in accordance with a tent map.

8. The method of claim 1, wherein the continuous sequence of digits is a non-repeating sequence.

9. The method of claim 1, wherein the continuous sequence of digits is derived from a non-deterministic source.

11. The method of claims 1-10, further comprising:

combining the digits shifted out of the shift register with substantially random numbers.

12. The method as claimed in claim 11, further comprising:

producing the random numbers with a non-deterministic source.

13. The method as claimed in claim 12, wherein said step of producing the sequence of random numbers with a non-deterministic source comprises:

producing the sequence of random numbers with a thermal noise source.

14. The method of claim 11, further comprising:

producing both the continuous sequence of digits and the random numbers with a common source.

15. The method of claim 14, wherein the combination of numbers from the non-repeating sequence with the random numbers is performed by exclusive OR-ing each bit of the random number with a respective bit of a number from the non-repeating sequence.

10. A method of generating a non-repeating sequence of numbers having a substantially uniform distribution within a predetermined interval, the method comprising:

providing a sequence of digits and repeatedly doubling a value of a group of said sequence of digits to produce a result; and

replacing the result by its complement in dependence on said value, wherein

said step of providing includes successively replenishing the group with digits from said sequence.