Method and apparatus for imbedded pattern recognition using dual alternating pointers
First Claim
1. A method for finding an occurrence of a reference pattern having K reference elements in an input pattern having M sequential input elements comprising the steps of:
- (a) loading a first reference address, corresponding to a first reference element in said reference pattern, into a first pointer register as a first pointer address and into a second pointer register as a second pointer address;
(b) comparing a first input element of said input pattern to a first pointer reference element from said reference pattern corresponding to said first pointer address and comparing said first input element to a second pointer reference element from said reference pattern corresponding to said second pointer address;
(c) incrementing said first pointer address if said first pointer reference element matches said first input element;
(d) incrementing said second pointer address if said second pointer reference element matches said first input element and said second pointer address does not match said first pointer address;
(e) incrementing said second pointer address if said second pointer reference element matches said first input element and said first pointer reference element does not match said first input element;
(f) resetting said first pointer address to said first reference address if said first pointer reference element does not match said first input element;
(g) resetting said second pointer address to said first reference address if said second pointer reference element does not match said first input element; and
(h) selecting a next sequential element from said M input elements as said first input element and repeating steps (a)-(g).
2 Assignments
0 Petitions
Accused Products
Abstract
A method and apparatus for finding a reference pattern (RP) with K elements imbedded in an input pattern IP with repeating substrings uses dual pointers to point to elements in the RP to compare with input elements sequentially clocked from the IP. The dual pointers are loaded with a pointer address corresponding to the first reference element in the RP and the pointer addresses are either incremented to the next position or are reset back to the address of the first reference element in response to results of comparing the reference element they access to the presently clocked input element and results of comparing their respective pointer addresses.
44 Citations
21 Claims
-
1. A method for finding an occurrence of a reference pattern having K reference elements in an input pattern having M sequential input elements comprising the steps of:
-
(a) loading a first reference address, corresponding to a first reference element in said reference pattern, into a first pointer register as a first pointer address and into a second pointer register as a second pointer address;
(b) comparing a first input element of said input pattern to a first pointer reference element from said reference pattern corresponding to said first pointer address and comparing said first input element to a second pointer reference element from said reference pattern corresponding to said second pointer address;
(c) incrementing said first pointer address if said first pointer reference element matches said first input element;
(d) incrementing said second pointer address if said second pointer reference element matches said first input element and said second pointer address does not match said first pointer address;
(e) incrementing said second pointer address if said second pointer reference element matches said first input element and said first pointer reference element does not match said first input element;
(f) resetting said first pointer address to said first reference address if said first pointer reference element does not match said first input element;
(g) resetting said second pointer address to said first reference address if said second pointer reference element does not match said first input element; and
(h) selecting a next sequential element from said M input elements as said first input element and repeating steps (a)-(g). - View Dependent Claims (2, 3, 4)
-
-
5. A system for finding a reference pattern with K elements imbedded in an input pattern comprising:
-
first and second pointer registers;
circuitry for loading a first reference address, corresponding to a first reference element in said reference pattern, into a first pointer register as a first pointer address and into a second pointer register as a second pointer address;
circuitry for comparing a first input element of said input pattern to a first pointer reference element from said reference pattern corresponding to said first pointer address and comparing said first input element to a second pointer reference element from said reference pattern corresponding to said second pointer address;
circuitry for incrementing said first pointer address if said first pointer reference element matches said first input element;
circuitry for incrementing said second pointer address if said second pointer reference element matches said first input element and said second pointer address does not match said first pointer address;
circuitry for incrementing said second pointer address if said second pointer reference element matches said first input element and said first pointer reference element does not match said first input element;
circuitry for resetting said first pointer address to said first reference address if said first pointer reference element does not match said first input element;
circuitry for resetting said second pointer address to said first reference address in said if said second pointer reference element does not match said first input element; and
circuitry for selecting a next sequential element from said M input elements as said first input element. - View Dependent Claims (6, 7, 8, 9)
-
-
10. A method for finding an occurrence of a reference pattern having K reference elements in an input pattern having M sequential input elements comprising the steps of:
-
(a) comparing a first input element of said input pattern to a first pointer reference element from said reference pattern stored at a first pointer address and comparing said first input element to a second pointer reference element from said reference pattern stored at a second pointer address;
(b) incrementing said first pointer address if said first pointer reference element matches said first input element;
(c) incrementing said second pointer address if said second pointer reference element matches said first input element and said second pointer address does not match said first pointer address; and
(d) incrementing said second pointer address if said second pointer reference element matches said first input element and said first pointer reference element does not match said first input element. - View Dependent Claims (11, 12, 13, 14, 15)
-
-
16. A system for finding a reference pattern with K elements imbedded in an input pattern comprising:
-
a first and second pointer register;
circuitry for loading a first reference address, corresponding to a first reference element in said reference pattern, into a first pointer register as a first pointer address and into a second pointer register as a second pointer address;
circuitry for comparing a first input element of said input pattern to a first pointer reference element from said reference pattern corresponding to said first pointer address and comparing said first input element to a second pointer reference element from said reference pattern corresponding to said second pointer address;
circuitry for incrementing said first pointer address if said first pointer reference element matches said first input element;
circuitry for incrementing said second pointer address if said second pointer reference element matches said first input element and said second pointer address does not compares to said first pointer address; and
circuitry for incrementing said second pointer address if said second pointer reference element matches said first input element and said first pointer reference element does not match said first input element. - View Dependent Claims (17, 18, 19, 20, 21)
-
Specification