Arbitrary repeating pattern detector

• US 5,528,526 A
• Filed: 09/19/1994
• Issued: 06/18/1996
• Est. Priority Date: 02/02/1993
• Status: Expired due to Fees

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Klug, Keith M., Tugenberg, Steven R.
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/308,473
• Time in Patent Office: 638 Days
• Field of Search: 364/717, 364/717.5, 364/715.11, 382/218, 340/146.2
• US Class Current: 708/212
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

An arbitrary repeating pattern detector (ARPD) detects short cycle patterns having a length of N or less, where N is an integer number. The ARPD obtains data symbols from a random number generator. ARPD may be implemented in a circuit or process which evaluates data symbols b₁ -b_2N. A mismatch detector compares symbols b_I+J-1 with symbols b_N+J for all combinations of I and J, where I and J are integer numbers in the range of 1-N, inclusive. For each value of I, an alternative detector determines whether at least one mismatch occurs at any value of J. If such a mismatch is detected, an alternative indication declares a mismatch at the corresponding value of I. A conjunction detector determines whether alternative indications for all values of I indicate mismatches. If a single match is found, a repeating pattern is declared.

Claims

1. An arbitrary repeating pattern detector comprising:

means for receiving a sequence of symbols;

means for storing said received symbols;

a mismatch detector coupled to said storage means to provide sets of comparison indications from determining whether a predetermined number of said received symbols match said predetermined number of said stored symbols;

an alternative detector coupled to said mismatch detector to provide alternative indications from determining whether, for each of said sets of said comparison indications, any one of said comparison indications within said set indicates a mismatch; and

a conjunction detector, coupled to said alternative detector, to determine whether all of said alternative indications indicate mismatches.

2. A repeating pattern detector as claimed in claim 1 further comprising supplying means for supplying bits of digital data.

3. A repeating pattern detector as claimed in claim 1 wherein:

said pattern detector detects a sequentially repeating pattern having ≦

N symbols, where N is an integer number less than or equal to one-half the number of symbols in said sequence;

said mismatch detector provides N² comparison indications arranged in N sets, wherein each of said N sets includes N comparison indications; and

said alternative detector provides N alternative indications.

4. A repeating pattern detector as claimed in claim 3 further comprising supplying means for supplying 2N symbols representable in sequence as symbols b₁ through b_2N ;

and wherein

said mismatch detector compares each symbol b_I+J-1 with each symbol b.sub. N+J for all values of I and J, where each of I and J is an integer variable representing values in the range of 1 through N.

5. A repeating pattern detector as claimed in claim 4 wherein said mismatch detector includes means for supplying one of said sets of comparison indications for each of said values of I.

6. A repeating pattern detector as claimed in claim 1 wherein said storing means is a shift register having a shift input coupled to said receiving means and a parallel output coupled to said mismatch detector.

7. A repeating pattern detector as claimed in claim 6 wherein:

said pattern detector detects a sequentially repeating pattern having ≦

Nsymbols, where N is an integer number less than or equal to one-half the total number of symbols in said sequence;

said shift register stores a sequence of N symbols;

said mismatch detector provides N² comparison indications arranged in N sets, wherein each of said N sets includes N comparison indications; and

said alternative detector provides N alternative indications.

8. A repeating pattern detector as claimed in claim 7 wherein:

said mismatch detector includes N comparison circuits each of which have first and second inputs and an output;

said N first inputs couple to said shift register to receive N corresponding ones of said symbols stored therein; and

said N second inputs couple to said supplying means to receive a common symbol not stored in said shift register.

9. A repeating pattern detector as claimed in claim 8 wherein:

said sequence of N symbols is representable in sequence as symbols b₁ through b_N ; and

said common symbol is representable in said sequence as symbol b_N+1.

10. A repeating pattern detector as claimed in claim 8 wherein said alternative detector comprises N memory elements each of which has an input coupled to a corresponding one of said N outputs of said comparison circuits.

11. A repeating pattern detector as claimed in claim 10 additionally comprising means, coupled to said N memory elements, for causing all of said N memory elements to indicate a matching condition.

12. A repeating pattern detector as claimed in claim 1 additionally comprising means, coupled to said conjunction detector, for detecting false repetitions.

13. A method executed by a computer as part of a computer program of detecting an arbitrary repeating pattern comprising the steps of:

a) receiving and storing a sequence of symbols;

b) determining whether a predetermined number of said received symbols match said predetermined number of said stored symbols;

c) providing sets of comparison indications in response to said step (b);

d) determining, whether, for each of said sets of said comparison indications, any one of said comparison indications within said set indicates a mismatch;

e) providing alternative indications in response to said step (d); and

f) determining whether all of said alternative indications indicate mismatches.

14. A method of detecting a repeating pattern as claimed in claim 13 wherein:

said method detects a sequentially repeating pattern having ≦

N symbols, where N is an integer number less than or equal to one-half the number of symbols in said sequence;

said step (b) makes N² determinations;

said step (c) arranges results from said N² determinations in N sets, wherein each of said N sets includes N comparison indications; and

said step (e) provides N alternative indications.

15. A method of detecting a repeating pattern as claimed in claim 14 wherein:

said step (a) obtains 2N symbols representable in sequence as symbols b₁ through b_2N ; and

said step (b) comprises the step of comparing each symbol b_I+J-1 with each symbol b_N+J for all values of I and J, where each of I and J is an integer variable representing values in the range of 1 through N.

16. A repeating pattern detector as claimed in claim 15 wherein said step (c) comprises the step of providing one of said sets of comparison indications for each of said values of I.

17. A method of detecting a repeating pattern as claimed in claim 14 wherein:

said step (a) obtains 2N symbols representable in sequence as symbols b₁ through b_2N ;

I and J are each integer variables representing values in the range of 1 through N; and

said step (b) comprises the steps of;

g) setting a value for I;

h) setting a value for J;

i) comparing a symbol b_I+J-1 with a symbol b_N+J ;

j) repeating said steps (h) and (i) for all remaining possible values for J; and

k) repeating said steps (g), (h), (i), and (j) for all possible values of I.

18. A method as claimed in claim 17 wherein said step (d) comprises the step of setting a variable for any repetition of said step (i) that indicates a mismatch.

19. A method as claimed in claim 18 wherein said step (f) comprises the step of examining said variable after said step (j) to determine whether said variable indicates a mismatch.

20. A method as claimed in claim 18 additionally comprising the step of initializing, prior to said step (g), said variable to indicate a match.

21. A method of detecting a repeating pattern as claimed in claim 13 additionally comprising the step of repeating said steps (a)-(f) when said step (f) determines that not all of said alternative indications indicate mismatches to test for a false repetition.