Technique for concurrent detection of bit patterns
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
23 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11)
-
-
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. - View Dependent Claims (13, 14, 15, 16, 17)
-
-
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. - View Dependent Claims (19, 20, 21, 22, 23)
-
Specification