Method and apparatus for imbedded pattern recognition using dual alternating pointers

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. The method of claim 1 , further comprising the steps of:

incrementing a first index value each time there is a match of said first pointer reference element to an input element and resetting said first index value to zero each time said first pointer reference element does not match an input element;

incrementing a second index value each time there is a match of said second pointer reference element to an input element and resetting said second index value to zero each time said second pointer reference element does not match an input element; and

repeating steps (a)–(h).

3. The method of claim 2 , further comprising the steps of:

outputting an indication of where in said input pattern said reference pattern matches a sequence of said input pattern when either said first sequence value or said second sequence value has a value of K; and

resetting said first and second index values to zero.

4. The method of claim 2 , further comprising the step of:

processing a second input pattern or stopping if said number M of said input elements of said first input pattern have been processed before either said first sequence or said second sequence has a value of K.

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.

6. The system of claim 5 , further comprising:

circuitry for incrementing a first index value each time there is a compare of said first pointer reference element to an input element;

circuitry for resetting said first index value to zero each time said first pointer reference element does not match an input element;

circuitry for incrementing a second index value each time there is a compare of said second pointer reference element to an input element; and

circuitry for resetting said second index value to zero each time said second pointer reference element does not match an input element.

7. The system of claim 6 , further comprising:

circuitry for outputting an indication of where in said input pattern said reference pattern matches a sequence of said input pattern when either said first index value or said second index value is equal to K; and

circuitry for resetting said first and second index values to zero.

8. The system of claim 7 , further comprising circuitry for processing a second input pattern if all elements of said first input pattern have been processed.

9. The system of claim 7 , further comprising circuitry for processing a second input pattern if either said first index value or said second index value is equal to K before all elements of said first input pattern have been processed.

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.

11. The method of claim 10 , further comprising the steps of:

resetting said first pointer address to a first reference address corresponding to a first reference element in said reference pattern if said first pointer reference element does not match said first input element; and

resetting said second pointer address to said first reference address if said second pointer reference element does not match said first input element.

12. The method of claim 11 , further comprising the steps of:

selecting a next sequential element from said M input elements as said first input element and repeating steps (a)–(d).

13. The method of claim 12 , further comprising the steps of:

incrementing a first index value each time there is a compare of said first pointer reference element to an input element and resetting said first index value to zero each time said first pointer reference element does not match an input element; and

incrementing a second index value each time there is a compare of said second pointer reference element to an input element and resetting said second index value to zero each time said second pointer reference element does not match an input element.

14. The method of claim 13 , further comprising the steps of:

outputting a location in said input pattern where said reference pattern matches a sequence of said input pattern when either said first index value or said second index value is equal to K; and

resetting said first and second index values to zero.

15. The method of claim 13 , further comprising the step of: processing a second input pattern or stopping if said number M of said input elements of said first input pattern have been processed before either said first index value or said second index value is equal to K.

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.

17. The system of claim 16 , further comprising:

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.

18. The system of claim 17 , further comprising:

circuitry for incrementing a first index value each time there is a compare of said first pointer reference element to an input element;

circuitry for resetting said first index value to zero each time said first pointer reference element does not match an input element;

circuitry for incrementing a second index value each time there is a compare of said second pointer reference element to an input element; and

circuitry for resetting said second index value to zero each time said second pointer reference element does not match an input element.

19. The system of claim 18 , further comprising:

circuitry for outputting an indication of where in said input pattern said reference pattern matches a sequence of said input pattern when either said first index value or said second index value is equal to K; and

circuitry for resetting said first and second index values to zero.

20. The system of claim 19 , further comprising circuitry for processing a second input pattern if all elements of said first input pattern have been processed.

21. The system of claim 19 , further comprising circuitry for processing a second input pattern if either said first index value or said second index value is equal to K before all elements of said first input pattern have been processed.