Search device using finite automata for partial words

摘要

Disclosed is a device that searches an input stream having a sequence of N-bit wide data words using a plurality of small EAs for a pattern. The device includes a plurality of subword EAs and a combiner. Each subword EA has an input word size less than N bits. Each EA processes a corresponding segment of the N-bit word and generates a match output indicating a possible match with the pattern when one of the input words for the EA is received and the EA moves to a predetermined match state. The combiner receives match outputs from all of the subword EAs and generates a pattern match output when all subword EAs indicate a match to the pattern. The pattern is a variable pattern. In one embodiment, the EAs are single-bit EAs.