Extending a repetition period of a random sequence

• US 7,921,145 B2
• Filed: 05/22/2007
• Issued: 04/05/2011
• 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.
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/751,783
• Publication Number:
  US 20080294710A1
• Time in Patent Office: 1,414 Days
• Field of Search: 708/250, 708/252
• US Class Current: 708/250
• 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 communications system based on the availability of a random sequence, comprising:

performing, by a ring generator circuit, 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, by said ring generator circuit, 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;

generating, by said ring generator circuit, 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; and

combining, by said communication system, said plurality of output sequence numbers having said arbitrary permutation ordering with respective output sequence bits defining information to be transmitted from said communications system.

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

1.

3. The method according to claim 2, wherein each of said plurality of output sequence numbers is associated with a respective element of said n elements.

4. The method according to claim 1, further comprising calculating, by said ring generator circuit, 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, 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.

7. The method according to claim 1, further comprising using, at said ring generator circuit, 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, by said ring generator circuit, said digit having a different number base to select an available unselected element in said cyclic structure.

10. A ring generator, comprising:

at least one electronic circuit 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;

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;

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; and

combining said plurality of output sequence numbers in said arbitrary permutation ordering with a plurality of output sequence bits defining information to be transmitted from a communications system.

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 electronic circuit 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 electronic circuit 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 electronic circuit is further configured for using a value of said selected combination of digits to select an available unselected element in said cyclic structure.

17. The ring generator according to claim 10, wherein said electronic circuit 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 17, wherein said electronic circuit is further configured for using said digit having a different number base to select an available unselected element in said cyclic structure.

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

20. A device comprising a machine-readable storage medium having stored thereon instructions, which when executed by said device, cause the device 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;

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; and

combining said plurality of output sequence numbers in said arbitrary permutation ordering with a plurality of output sequence bits defining information to be communicated from said device.

21. The device 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 device according to claim 20, wherein said machine-readable storage medium further comprises instructions to cause said device to perform 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 device according to claim 20, wherein said machine-readable storage medium further comprises instructions to cause said device to perform the operation of converting each of said plurality of RNS residue values to a different relatively prime number system.

24. The device according to claim 20, wherein said machine-readable storage medium further comprises 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 device according to claim 20, wherein said machine-readable storage medium further comprises instructions to cause said device to perform the operation of using a value of said select combination of digits to select an available unselected element in said cyclic structure.

26. The device according to claim 20, wherein said machine-readable storage medium further comprises instructions to cause said device to perform 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 device according to claim 26, wherein said machine-readable storage medium further comprises instructions to cause said device to perform the operation of using said digit having a different number base to select an available unselected element in said cyclic structure.