US5383142A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Fast circuit and method for detecting predetermined bit patterns
Assignee: Hewlett Packard Development Co LP
•
Filing: 1993-10-01
•
Granted: 1995-01-17
•
Expires: 2013-10-01
Abstract
Abstract A method and processor design for detecting a specified bit pattern based on the contents of one or more registers, each register having a plurality of bits. The invention is well suited for parallel processing. The method begins by combining successive sets of contiguous bits to generate a state value and output value representative of the values in each set of contiguous bits. The state values and output values so generated become the values for level 1 of a hierarchy of state and output values. The manner in which the states are assigned and the number of states will, in general, depend on the specific bit pattern being sought. At each successive level in the hierarchy, sets of continuous output values and state values from the previous level are combined to generate the output values and state values for the level in question. The number of output and state values is reduced by at least a factor of two at each level of the hierarchy. The process is terminated when only one output value and state value remains. The final output value specifies the location of the first bit of the bit pattern sought in the original bit string when the final state indicates that the bit pattern has been found. The method may be implement by a processor that includes a hierarchical array of processing elements arranged as a plurality of ordered levels of processors. Each level of processors has one or more processing modules. Each processing module receives a plurality of state inputs and generates therefrom a state output. The processing modules in level 1 have their state inputs connected to selected bits in the registers and the processing modules in the k th level of the hierarchy have their state inputs connected to state outputs of processing modules in level (k-1).
Inventors
- 👤 Shine Chung
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 03:33
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/74
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
243 words
A processor for detecting a specified bit pattern in the contents of one or more registers, each register having a plurality of bits, said processor comprising a hierarchical array comprising a plurality of ordered levels of processors labeled 1, 2, . . . M, each level of processors having one or more processing modules, each processing module receiving a plurality of state inputs and generating therefrom a state output, said processing modules in level 1 of said processors having said state inputs connected to selected bits in said registers and said processing modules in the k th level of said hierarchy having said state inputs connected to state outputs of processing modules in level (k-1) of said hierarchy for k=2 to M, wherein each of said processing modules in said levels labeled with 2, 3, . . . , M further comprise means for receiving a plurality of input values and means for generating an output value based on said state inputs and said input values, said receiving means of said processing modules in the k th level of said hierarchy having said receiving means connected to said output generating means of processing modules in level (k-1) of said hierarchy for k=2 to M, said output value providing information on the potential location of said specified bit pattern, and wherein each said processing module in said level labeled 1 includes means for generating an output signal based on said selected bits connected thereto.
Claim 2
Dependent Claim
243 words
A processor for detecting a specified bit pattern in the contents of one or more registers, each register having a plurality of bits, said processor comprising a hierarchical array comprising a plurality of ordered levels of processors labeled 1, 2, . . . M, each level of processors having one or more processing modules, each processing module receiving a plurality of state inputs and generating therefrom a state output, said processing modules in level 1 of said processors having said state inputs connected to selected bits in said registers and said processing modules in the k th level of said hierarchy having said state inputs connected to state outputs of processing modules in level (k-1) of said hierarchy for k=2 to M, wherein each of said processing modules in said levels labeled with 2, 3, . . . , M further comprise means for receiving a plurality of input values and means for generating an output value based on said state inputs and said input values, said receiving means of said processing modules in the k th level of said hierarchy having said receiving means connected to said output generating means of processing modules in level (k-1) of said hierarchy for k=2 to M, said output value providing information on the potential location of said specified bit pattern, and wherein each said processing module in said level labeled 1 includes means for generating an output signal based on said selected bits connected thereto.
Claim 3
Dependent Claim
37 words
The processor of claim 1 wherein each of said processing modules in the p th level of said hierarchy, for p>1, has said state inputs connected to said state outputs of two processing modules in level (p-1).
Claim 4
Dependent Claim
104 words
The processor of claim 2 wherein said processing modules in levels 2, . . . M comprise means for receiving first and second state input, each said state input having one of two predetermined values, means for receiving first and second partial addresses, means responsive to said first and second state inputs for generating a state output having one of said two predetermined values, means responsive to said first and second state inputs for selecting one of said partial addresses and for generating an address bit to be appended to one of said partial addresses to form the output information of said processing module.
Claim 5
Dependent Claim
64 words
The processor of claim 1 wherein said state output from one of said processing module in said level labeled M in said hierarchical array indicates whether the specified bit pattern has been found, and said output value output from one of said processing module in said level labeled M in said hierarchical array indicates the location of the specified bit pattern in said register.
Claim 6
Dependent Claim
58 words
The processor of claim 1 wherein said output value output from each of said processing modules in the k th level comprises an enlarged partial address, and wherein said means for generating said output value comprises means for producing said enlarged partial address by selecting one of said output values input thereto based on said state inputs thereto.
Claim 7
Dependent Claim
31 words
The processor of claim 5 wherein said means for generating said output value further comprises means for appending an additional bit to the selected one of said output values input thereto.
Claim 8
Independent Claim
214 words
A method for operating a data processing system to determine the position of a predetermined bit pattern in a string of bits, said method comprising the steps of: (a) combining successive sets of contiguous bits in said bit string to generate a state value and output value representative of the values in each said set of contiguous bits, said state values and output values comprising level 1 of a hierarchy of state and output values, each bit in said bit string being in precisely one of said successive sets; (b) combining successive sets of continuous output values and state values from level k to generate output values and state values in level (k+1) for k>1, said output values and state values being determined by the output values and state values in level k, each output value and state value in level k being in precisely one of said successive sets, the number of said output values and said state values at level k being less than the number of said output values and state values at level (k-1); and (c) repeating (b) until only one output value and one state value are generated, said output value arid said state value being referred to as the final output value and the final state value, respectively.
Claim 9
Independent Claim
214 words
A method for operating a data processing system to determine the position of a predetermined bit pattern in a string of bits, said method comprising the steps of: (a) combining successive sets of contiguous bits in said bit string to generate a state value and output value representative of the values in each said set of contiguous bits, said state values and output values comprising level 1 of a hierarchy of state and output values, each bit in said bit string being in precisely one of said successive sets; (b) combining successive sets of continuous output values and state values from level k to generate output values and state values in level (k+1) for k>1, said output values and state values being determined by the output values and state values in level k, each output value and state value in level k being in precisely one of said successive sets, the number of said output values and said state values at level k being less than the number of said output values and state values at level (k-1); and (c) repeating (b) until only one output value and one state value are generated, said output value arid said state value being referred to as the final output value and the final state value, respectively.
Claim 10
Dependent Claim
18 words
The method of claim 7 wherein said final output value specifies the position of said predetermined bit pattern.
Claim 11
Dependent Claim
25 words
The method of claim 8 wherein each output value generated at level k includes at least one of the output values generated at level (k-1).
Claim 12
Dependent Claim
29 words
The method of claim 7 in which the number of output and state values generated at any given level is one half the number generated at the previous level.
Claim 13
Dependent Claim
42 words
The method of claim 7 wherein said final state output generated in the last level indicates whether the specified bit pattern has been found, and said final output value generated in the last level indicates the location of said predetermined bit pattern.
Claim 14
Dependent Claim
48 words
The method of claim 7 wherein said output values generated comprise an enlarged partial address, and wherein said combining step (b) comprises the step of producing said enlarged partial address for level k+1 by selecting one of said output values for level k based on said state inputs.
Claim 15
Dependent Claim
27 words
The method of claim 12 wherein said combining step (b) further comprises the step of appending an additional bit to the selected one of said output values.
References Cited (Backward Citations)
US4785421A
Cited
US5073864A
Cited
US4864527A
Cited
US4939683A
Cited
US5111415A
Cited
US5212699A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1998-01-16 | 1998-07-18 | 1999-01-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-01-16 | 2002-07-18 | 2003-01-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-01-16 | 2006-07-18 | 2007-01-17 | $7700.00 | Window Closed / Lapsed |