Technique for concurrent detection of bit patterns

• US 5,894,427 A
• Filed: 11/12/1997
• Issued: 04/13/1999
• Est. Priority Date: 11/12/1997
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chung, Shine
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US08/968,565
• Time in Patent Office: 517 Days
• Field of Search: 364/715.11, 364/715.1, 364/715.04
• US Class Current: 708/212
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

A technique for concurrently detecting a repetitive occurrence of a bit pattern in a bit string. Successive bits of the bit string are separated into bit groupings and the combined bits are analyzed for the presence of the bit pattern. The logic for subsequent analysis to reduce the number of groupings is achieved by the use of a hierarchically decreasing logic array. At each level of the hierarchy, the bit analysis is reduced until a final output is reached. This final output provides state and address outputs for identifying the detection of the bit pattern occurrences and the address where the bit patterns occur.

Claims

1. An apparatus for concurrently detecting a first and subsequent occurrences of a bit pattern in a bit string comprising:

a plurality of first logic modules forming a first level of a logic hierarchy, wherein each of said first logic modules is coupled to receive successive bits of said bit string and for generating a state output and a plurality of partial address outputs, corresponding to bit values and bit locations for said successive bits received;

a plurality of second logic modules arranged in a decreasing array below said first level to form subsequent levels of said logic hierarchy, until a final second logic module resides at a final level of said logic hierarchy;

said second logic modules coupled to receive state and partial address outputs from more than one of said first or second logic modules of a previous level and for generating a subsequent state output and partial addresses to a respective subsequent level based on received states and partial addresses, until a final state and partial address outputs are generated to identify detection and locations of said bit pattern occurrences.

2. The apparatus of claim 1 wherein a partial address is generated by each module for detection of each occurrence of said bit pattern and generation of each partial address from a particular second logic module is achieved by propagating a partial address from a previous level of said hierarchy.

3. The apparatus of claim 2 wherein a bit is appended to each partial address generated by said second logic modules at levels subsequent to said first level.

4. The apparatus of claim 3 wherein said bit pattern being detected is a single bit.

5. The apparatus of claim 4 wherein two partial addresses are generated and propagated for detecting the occurrences of a first "1" bit and a second "1" bit.

6. The apparatus of claim 4 wherein said first logic modules process a sequence of two successive bits and each second logic module processes state and partial address outputs from a pair of logic modules of a previous level.

7. A state machine for concurrently detecting a first occurrence of a bit value and a second occurrence of the same bit value in a bit string comprising:

a plurality of first logic modules forming a first level of a logic hierarchy, wherein each of said first logic modules is coupled to receive two successive bits of said bit string and for generating a state output corresponding to a number of a particular bit value present in its respective two successive bits received and generating a first and second partial address outputs corresponding to values of its respective two bits;

a plurality of second logic modules arranged in a decreasing array below said first level to form subsequent levels of said logic hierarchy, until a final second logic module resides at a final level of said logic hierarchy;

said second logic modules coupled to receive state, first and second partial address outputs from more than one of said first or second logic modules of a previous level and for generating a subsequent state, first and second partial address outputs to a respective subsequent level based on received states and partial addresses, until a final state, first and second partial address outputs are generated to identify detection and locations of said first and second bit value occurrences.

8. The state machine of claim 7 wherein a generation of each partial address from a particular second logic module is achieved by propagating a partial address from a previous level of said hierarchy.

9. The state machine of claim 8 wherein a bit is appended to each partial address generated by said second logic modules at levels subsequent to said first level.

10. The state machine of claim 9 wherein said second logic modules are each arranged to process state, first and second partial address outputs from a pair of first or second logic modules of a previous level.

11. The state machine of claim 10 wherein said bit value being detected is a "1" bit.

12. A processor for concurrently detecting a first and subsequent occurrences of a bit pattern in a bit string comprising:

a register for holding said bit string;

a plurality of first logic modules coupled to said register and forming a first level of a logic hierarchy, wherein each of said first logic modules receives successive bits of said bit string and for generating a state output and a plurality of partial address outputs, corresponding to bit values and bit locations for said successive bits received;

a plurality of second logic modules arranged in a decreasing array below said first level to form subsequent levels of said logic hierarchy, until a final second logic module resides at a final level of said logic hierarchy;

said second logic modules coupled to receive state and partial address outputs from more than one of said first or second logic modules of a previous level and for generating a subsequent state output and partial addresses to a respective subsequent level based on received states and partial addresses, until a final state and partial address outputs are generated to identify detection and locations of said bit pattern occurrences.

13. The processor of claim 12 wherein a partial address is generated by each module for detection of each occurrence of said bit pattern and generation of each partial address from a particular second logic module is achieved by propagating a partial address from a previous level of said hierarchy.

14. The processor of claim 13 wherein a bit is appended to each partial address generated by said second logic modules at levels subsequent to said first level.

15. The processor of claim 14 wherein said bit pattern being detected is a single bit.

16. The processor of claim 15 wherein two partial addresses are generated and propagated for detecting the occurrences of a first "1" bit and a second "1" bit.

17. The processor of claim 15 wherein said first logic modules process a sequence of two successive bits and each second logic module processes state and partial address outputs from a pair of logic modules of a previous level.

18. A method for concurrently detecting a first and subsequent occurrences of a bit pattern in a bit string, comprising the steps of:

a) separating said bit string into a plurality of bit groupings;

b) generating a state output and a plurality of partial address outputs for each of said bit groupings, wherein each of said first state outputs corresponds to bit values of bits in its respective grouping and said partial address outputs correspond to ordering of said bit values, at least one partial address being generated for detection of each occurrence of said bit pattern;

c) combining a plurality of state and partial address outputs as inputs to a subsequent stage of a decreasing hierarchical logic array;

d) generating subsequent state and partial address outputs based on state and partial address outputs of a previous level of said array;

e) repeating steps c) and d) until one final state output remains with its associated partial addresses, said final state output identifying the occurrences of said bit pattern and each of its partial addresses identifying an address location of each bit pattern occurrence being detected.

19. The method of claim 18 further including the step of appending a bit to each partial address being generated to extend its address, said step being performed after step d) but prior to step e).

20. The method of claim 19 wherein said step of separating said bit string into a plurality of bit groupings further includes the step of separating said bit string into groupings of two bits.

21. The method of claim 20 wherein said steps are performed to detect multiple occurrences of a single bit.

22. The method of claim 20 wherein said steps are performed to detect the first and second occurrences of a bit.

23. The method of claim 20 wherein said steps are performed to detect the first and second occurrences of a "1" bit.