Mixed radix number generator with chosen statistical artifacts

• US 7,962,540 B2
• Filed: 06/07/2007
• Issued: 06/14/2011
• Est. Priority Date: 06/07/2007
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Michaels, Alan J., Chester, David B.
• Primary Examiner(s): Malzahn; David H
• Application Number:
  US11/759,276
• Publication Number:
  US 20080307024A1
• Time in Patent Office: 1,468 Days
• Field of Search: None
• US Class Current: 708/250
• CPC Class Codes: G06F 7/58 Random or pseudo-random number generators
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A method is provided for masking a process used in generating a number sequence. The method includes generating a first sequence of numbers contained within a Galois field GF[M]. The method also includes performing a first modification to a first number in the first sequence of numbers. The first modification includes summing the first number with a result of a modulo P operation performed on a second number of the first sequence that proceeds the first number. M is relatively prime with respect to P. The method further includes performing a second modification to the first random number. The second modification is comprised of a modulo P operation. This second modification is performed subsequent to the first modification. The method includes repeating the first and second modification for a plurality of numbers comprising the first sequence of numbers to generate a second sequence of numbers.

Claims

1. A method for masking a process used in generating a number sequence, comprising;

generating, by at least one electronic circuit, a first sequence of numbers contained within a Galois field GF[M];

performing, by said electronic circuit, a first modification to a first number in said first sequence of numbers to obtain a modified first number, said first modification comprising summing said first number with a result of a modulo P operation performed on a second number of said first sequence that precedes said first number, where M is relatively prime with respect to P;

subsequent to said first modification, performing, by said electronic circuit, a second modification to said modified first number comprising a modulo P operation;

repeating, by said electronic circuit, said first and second modifications for a plurality of numbers comprising said first sequence of numbers to generate a second sequence of numbers; and

combining, by said electronic circuit, at least a portion of said second sequence of numbers with a sequence of symbols defining information to be stored in a storage device or transmitted over a communications link.

2. The method according to claim 1, wherein said generating step further comprises generating a pseudo-random sequence of numbers containing chosen statistical artifacts relating to said generating step, and wherein said statistical artifacts are chosen to create a uniformly distributed sequence of random numbers on GF[P] by said first and second modification steps.

3. The method according to claim 1, wherein said generating step further comprises exhaustively producing said first sequence of numbers by using a mapping which is periodically repeated.

4. The method according to claim 3, wherein said mapping includes a combination of an additive mapping and a multiplicative mapping.

5. The method according to claim 4, wherein said additive mapping and said multiplicative mapping in combination are selected to include repeated computations of an irreducible polynomial over a Galois field GF[M].

6. The method according to claim 1, wherein M is a value that is larger than P.

7. The method according to claim 1, wherein M is a value that is mutually prime with P and all of a plurality of prime factors of P include including p₁, p₂, p₃, . . . p_k.

8. The method according to claim 7, further comprising performing, by said electronic circuit, a third modification step on said second sequence of numbers, said third modification step comprising generating a plurality of output number sequences from said second sequence of numbers.

9. The method according to claim 8, wherein said third modification step comprises a modulo p operation performed upon each number in said second sequence of numbers to generate said plurality of output number sequences, where p includes a plurality of values selected from the group comprising p₁, p₂, p₃. . . p_k.

10. The method according to claim 1, wherein said second number is immediately preceding said first number.

11. The method according to claim 1, wherein said second number precedes said first number by N positions, where N is greater than 1.

12. The method according to claim 1, wherein said second sequence of numbers has statistical artifacts that are evenly distributed over a plurality of equivalence classes of said Galois field GF[P], and said plurality of equivalence classes include an equivalence class for each integer 0, 1, . . . , P-1.

13. A mixed radix number generator, comprising:

a number generator configured for generating a first sequence of numbers contained within a Galois field GF[M];

a mixed radix accumulator configured for

(1) performing a first modification to a first number in said first sequence of numbers to obtain a modified first number, said first modification comprising summing said first number with a result of a modulo P operation performed on a second number of said first sequence of numbers that precedes said first number, where M is relatively prime with respect to P,

(2) subsequent to said first modification, performing a second modification to said modified first number comprising a modulo P operation, and

(3) repeating said first and second modifications for a plurality of numbers comprising said first sequence of numbers to generate a second sequence of numbers.

14. The system according to claim 13, further comprising means configured for using said second sequence of numbers to modify a digital data stream.

15. The system according to claim 13, wherein said number generator comprises a pseudo-random number generator for generating a pseudo-random sequence of numbers containing statistical artifacts relating to said generation of said first sequence of numbers, and wherein said statistical artifact is eliminated by said mixed radix accumulator.

16. The system according to claim 13, wherein said number generator is configured for exhaustively producing said first sequence of numbers by using a mapping which is periodically repeated.

17. The system according to claim 16, wherein said mapping includes a combination of an additive mapping and a multiplicative mapping.

18. The system according to claim 17, wherein said additive mapping and said multiplicative mapping in combination include repeated computations of an irreducible polynomial over a Galois field GF[M].

19. The system according to claim 13, wherein M is larger than P.

20. The system according to claim 13, further wherein a value of M is mutually prime with respect to a value of P and all of a plurality of prime factors of P including p₁, p₂, p₃, . . . p_k.

21. The system according to claim 20, further comprising a plurality of arithmetic operator units each configured for performing a third modification on said second sequence of numbers, said plurality of arithmetic operator units generating a plurality of output number sequences from said second sequence of numbers.

22. The system according to claim 21, wherein said third modification comprises a modulo p operation performed upon each number in said second sequence of numbers to generate said plurality of output number sequences, where p includes a plurality of values selected from the group comprising p₁, p₂;

p₃, . . . p_k.

23. The system according to claim 13, wherein said second number precedes said first number by one position.

24. The system according to claim 13, wherein said second number precedes said first number by N positions, where N is greater than 1.

25. The system according to claim 13, wherein said first sequence of numbers is limited to a finite number of elements M defined by a Galois field GF[M], said second sequence of numbers has statistical artifacts that are evenly distributed over a plurality of equivalence classes of said Galois field GF[P], and wherein said plurality of equivalence classes include an equivalence class for each integer 0, 1, . . . , P-1.

26. The system according to claim 13, wherein said first sequence is operated upon by a filter structure configured to perform calculations inside a Galois of equal size to the second sequence.