Extending a Repetition Period of a Random Sequence

• US 20080294710A1
• Filed: 05/22/2007
• Published: 11/27/2008
• Est. Priority Date: 05/22/2007
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Michaels, Alan J.
• Granted Patent: US 7,921,145 B2
• Time in Patent Office: Days
• US Class Current: 708/491
• CPC Class Codes: G06F 7/582 Pseudo-random number generators
• CPC Class Codes: G06F 7/729 using representation by a residue number system
• CPC Class Codes: G06F 7/76 Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data

Abstract

A method is provided for extending a sequence repetition period of a random number generator in systems based on the availability of random sequences. The method includes performing RNS arithmetic operations to express a random number in a sequence as RNS residue values. Each generated random number has a value between zero and n!−1. The method also includes converting each of the RNS residue values to a relatively prime base number system so that each of the RNS residue values includes at least one digit. The method further includes generating an arbitrary permutation ordering of output sequence numbers using a select combination of digits associated with each of the RNS residue values. The arbitrary permutation ordering is applied to a cyclic structure having n elements. Each of the n elements has an associated output sequence number.

Claims

1. A method for extending a sequence repetition period of a random number generator in a system based on the availability of a random sequence, comprising:

performing a plurality of residue number system (RNS) arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values;

converting each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit; and

generating an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values, wherein said arbitrary permutation ordering is determined using a cyclic structure.

2. The method according to claim 1, further comprising selecting said cyclic structure to have n elements and selecting said random number to have a value which can range between zero and n!−

1.

3. The method according to claim 2, further comprising associating each of said plurality of output sequence numbers with a respective element of said n elements.

4. The method according to claim 1, further comprising calculating said plurality of RNS residue values using relatively prime numbers as moduli, wherein said moduli are determined by determining a decimal number defined by n! as a product of relatively prime numbers.

5. The method according to claim 1, wherein said converting step further comprises converting each of said plurality of RNS residue values to a different relatively prime number system.

6. The method according to claim 1, further comprising choosing said select combination of digits so that a range of values which can be determined by said digits is equal to a number of available unselected elements in said cyclic structure.

7. The method according to claim 1, further comprising using a value of said select combination of digits to select an available unselected element in said cyclic structure.

8. The method according to claim 1, wherein said generating step further comprises using a Chinese Remainder Theorem to combine at least two digits associated with at least two RNS residue values to obtain a digit having a different number base than said at least two digits.

9. The method according to claim 8, further comprising using said digit having a different number base to select an available unselected element in said cyclic structure.

10. A ring generator, comprising:

a computing means configured for performing a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values;

a converting means configured for converting each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit; and

a permutation means configured for generating an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values, wherein said arbitrary permutation ordering is determined using a cyclic structure.

11. The ring generator according to claim 10, wherein said random number has a value within a range of zero to n!−

1 and said cyclic structure has n elements.

12. The ring generator according to claim 11, wherein each of said plurality of output sequence numbers is associated with a respective element of said n elements.

13. The ring generator according to claim 10, wherein said computing means is further configured for calculating said plurality of RNS residue values using relatively prime numbers as moduli, wherein said relatively prime numbers are selected to have a product equal to a decimal number defined by n!.

14. The ring generator according to claim 10, wherein said converting means is further configured for converting each of said plurality of RNS residue values to a different relatively prime number system.

15. The ring generator according to claim 10, wherein said select combination of digits are chosen so that a range of values which can be determined by said digits is equal to a number of available unselected elements in said cyclic structure.

16. The ring generator according to claim 10, wherein said permutation means is further configured for using a value of said select combination of digits to select an available unselected element in said cyclic structure.

17. The ring generator according to claim 10, wherein said permutation means is further configured for using a Chinese Remainder Theorem to combine at least two digits associated with at least two RNS residue values to obtain a digit having a different number base than said at least two digits.

18. The ring generator according to claim 10, wherein said permutation means is further configured for using a Chinese Remainder Theorem to combine with one or more additional cyclic ring generators.

19. The ring generator according to claim 17, wherein said permutation means is further configured for using said digit having a different number base to select an available unselected element in said cyclic structure.

20. A machine-readable medium having stored thereon instructions, which when executed by a machine, cause the machine to perform the following operations comprising:

performing a plurality of RNS arithmetic operations to express a random number in a random number sequence as a plurality of RNS residue values;

converting each of said plurality of RNS residue values to a relatively prime number system so that each of said plurality of RNS residue values includes at least one digit; and

generating an arbitrary permutation ordering of a plurality of output sequence numbers using a select combination of digits associated with each of said plurality of RNS residue values, wherein said arbitrary permutation ordering is determined using a cyclic structure.

21. The machine-readable medium according to claim 20, wherein said random number has a value between zero and n!−

1, said cyclic structure has n elements, and each of said plurality of output sequence numbers is associated with a respective element of said n elements.

22. The machine-readable medium according to claim 20, further comprising instructions to cause the operation of calculating said plurality of RNS residue values using relatively prime numbers as moduli, wherein said relatively prime numbers are to have a product equal to a decimal number defined by n!.

23. The machine-readable medium according to claim 20, further comprising instructions to cause the operation of converting each of said plurality of RNS residue values to a different relatively prime number system.

24. The machine-readable medium according to claim 20, further comprising instructions to cause the operation of choosing said select combination of digits so that a range of values which can be determined by said digits is equal to a number of available unselected elements in said cyclic structure.

25. The machine-readable medium according to claim 20, further comprising instructions to cause the operation of using a value of said select combination of digits to select an available unselected element in said cyclic structure.

26. The machine-readable medium according to claim 20, further comprising instructions to cause the operation of using a Chinese Remainder Theorem to combine at least two digits associated with at least two RNS residue values to obtain a digit having a different number base than said at least two digits.

27. The machine-readable medium according to claim 28, further comprising instructions to cause the operation of using said digit having a different number base to select an available unselected element in said cyclic structure.