US5528526A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Arbitrary repeating pattern detector
Assignee: General Dynamics Mission Systems Inc
•
Filing: 1994-09-19
•
Granted: 1996-06-18
•
Expires: 2014-09-19
Abstract
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 1 -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.
Inventors
- 👤 Keith M. Klug
- 👤 Steven R. Tugenberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 14:39
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/02
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
106 words
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.
Claim 2
Dependent Claim
106 words
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.
Claim 3
Dependent Claim
19 words
A repeating pattern detector as claimed in claim 1 further comprising supplying means for supplying bits of digital data.
Claim 4
Dependent Claim
71 words
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 2 comparison indications arranged in N sets, wherein each of said N sets includes N comparison indications; and said alternative detector provides N alternative indications.
Claim 5
Dependent Claim
69 words
A repeating pattern detector as claimed in claim 3 further comprising supplying means for supplying 2N symbols representable in sequence as symbols b 1 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.
Claim 6
Dependent Claim
31 words
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.
Claim 7
Dependent Claim
35 words
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.
Claim 8
Dependent Claim
79 words
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 2 comparison indications arranged in N sets, wherein each of said N sets includes N comparison indications; and said alternative detector provides N alternative indications.
Claim 9
Dependent Claim
68 words
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.
Claim 10
Dependent Claim
41 words
A repeating pattern detector as claimed in claim 8 wherein: said sequence of N symbols is representable in sequence as symbols b 1 through b N ; and said common symbol is representable in said sequence as symbol b N+1 .
Claim 11
Dependent Claim
36 words
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.
Claim 12
Dependent Claim
31 words
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.
Claim 13
Dependent Claim
21 words
A repeating pattern detector as claimed in claim 1 additionally comprising means, coupled to said conjunction detector, for detecting false repetitions.
Claim 14
Independent Claim
105 words
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.
Claim 15
Independent Claim
105 words
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.
Claim 16
Dependent Claim
80 words
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 2 determinations; said step (c) arranges results from said N 2 determinations in N sets, wherein each of said N sets includes N comparison indications; and said step (e) provides N alternative indications.
Claim 17
Dependent Claim
74 words
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 1 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.
Claim 18
Dependent Claim
32 words
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.
Claim 19
Dependent Claim
108 words
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 1 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.
Claim 20
Dependent Claim
29 words
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.
Claim 21
Dependent Claim
30 words
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.
Claim 22
Dependent Claim
24 words
A method as claimed in claim 18 additionally comprising the step of initializing, prior to said step (g), said variable to indicate a match.
Claim 23
Dependent Claim
41 words
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.
References Cited (Backward Citations)
US3855576A
Cited
JPS61173527A
Cited
US4736424A
Cited
US5014327A
Cited
US5020058A
Cited
US4977596A
Cited
US5208832A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-06-18 | 1999-12-18 | 2000-06-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-06-18 | 2003-12-18 | 2004-06-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-06-18 | 2007-12-18 | 2008-06-18 | $7700.00 | Window Closed / Lapsed |