Method and device for performing data pattern matching
AssigneeSarnoff Corporation
InventorsWee Mon Wong, Maurice David Caldwell
Life of this patent
Estimating the term…
Abstract
A method and system for identifying a bit pattern in a data stream including a plurality of bits each having a first or second state, the method includes identifying a number of mismatching bits, within a subset of the plurality of bits, having the first state and corresponding to a bit having the second state within the pattern; identifying a number of bits in the subset having the first state; and, identifying a number of bits in the pattern having the second state. A number of matches of between the subset and the pattern is dependent on the identified number of mismatching bits, the identified number of bits in the subset having the first state and the identified number of bits in the pattern having the second state.
Claims22
A method for identifying a bit pattern in a data stream comprising a plurality of bits each having a first or second state, said method comprising:
- identifying a number of mismatching bits, within a subset of said plurality of bits, having said first state and a bit correspondence with said second state within said pattern;
- identifying a number of bits in said subset having said first state;
- and,
- identifying a number of bits in said pattern having said second state;
- wherein, a number of matches of between said subset and said pattern is dependent on said identified number of mismatching bits, said identified number of bits in said subset having said first state and said identified number of bits in said pattern having said second state.
A device for identifying a bit pattern in a data stream, said device comprising:
- a memory device for storing a plurality of bits indicative of at least a portion of said data stream, each of said bits having a first state or a second state;
- an adder communicatively coupled to memory device so as to sum select ones of said bits corresponding to select bit locations in said bit pattern;
- a controller communicatively coupled to said memory device so as to receive at least a portion of said bits and for determining which of a plurality of predetermined conditions is present based upon said received portion of said bits;
- and,
- an adder/subtractor communicatively coupled and responsive to said controller to selectively increment and decrement a given value if a select one of said bits corresponds to a mismatching condition with said bit pattern.
A computer program product embodied on a computer-readable storage medium and for identifying a bit pattern in a data stream comprising a plurality of bits each having a first or second state, said computer program product comprising:
- code for identifying a number of mismatching bits, within a subset of said plurality of bits, having said first state and a bit correspondence with said second state within said pattern;
- code for identifying a number of bits in said subset having said first state;
- and,
- code for identifying a number of bits in said pattern having said second state;
- wherein, a number of matches of between said subset and said pattern is dependent on said identified number of mismatching bits, said identified number of bits in said subset having said first state and said identified number of bits in said pattern having said second state.
Dependencies are inferred from the claim text.