Method and apparatus for generating numbers

• US 20020035586A1
• Filed: 12/12/2000
• Published: 03/21/2002
• Est. Priority Date: 12/20/1999
• Status: Active Grant

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Szajnowski, W. J.
• Granted Patent: US 6,751,639 B2
• Time in Patent Office: Days
• 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 using successive digits from a continuous sequence thereof to replace digits shifted out of a 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. A 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. A method as claimed in claim 2, wherein the shift register has N+X stages, wherein X is an integer of one or more.

4. A 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. A method as claimed in any preceding claim, 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. A method as claimed in any preceding claim, 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. A method as claimed in any preceding claim, 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. A method as claimed in any preceding claim, wherein the continuous sequence of digits is a non-repeating sequence.

9. A method as claimed in any preceding claim, wherein the continuous sequence of digits is derived from a non-deterministic source.

12. A method of generating a sequence of random numbers having a substantially uniform distribution, the method comprising generating a non-repeating sequence in accordance with a method as claimed in any preceding claim, and combining numbers of that sequence with substantially random numbers in order to randomise the non-repeating sequence.

15. A method as claimed in any one of claims 12 to 14, including a common source for producing both the continuous sequence of digits and the random numbers.

16. A method as claimed in any one of claims 12 to 15, 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.

18. Apparatus for generating a non-repeating sequence of numbers having a substantially uniform distribution, the apparatus being arranged to operate in accordance with a method as claimed in any one of claims 1 to 11.

19. Apparatus for generating random numbers, the apparatus being arranged to operate in accordance with a method as claimed in any one of claims 12 to 17.

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 the value of a group of said digits and replacing the result by its complement in dependence on said value, the group being successively replenished by digits from said sequence.

11. A method of generating a non-repeating sequence of numbers having a substantially uniform distribution, the method being substantially as herein described with reference to FIGS. 2 to 6, optionally in combination with FIG. 7 or FIG. 8, of the accompanying drawings.

13. A method as claimed in claim 12, wherein the random numbers are produced by a non-deterministic source.

14. A method as claimed in claim 13, wherein the non-deterministic source is a thermal noise source.

17. A method of generating random numbers, the method being substantially as herein described with reference to FIG. 10, optionally in combination with FIG. 13, of the accompanying drawings.

20. A method of digitally generating a non-repeating sequence of uniformly-distributed numbers, the method including the step of:

repeatedly changing a rational number according to a predetermined algorithm which, if applied to an irrational seed number, would produce an endless non-repeating sequence of uniformly-distributed irrational numbers;

each rational number change also involving adding to the number one or more randomly-generated bits.

21. A method of digitally generating a non-repeating sequence of uniformly-distributed numbers, the method comprising:

(a) producing a sequence of randomly-generated bits;

(b) applying an algorithm to a predetermined number of the bits, the algorithm involving shifting the bits;

(c) adding one or more bits from the randomly-generated sequence to replace the shifted bits; and

(d) repeating steps (b) and (c).