Apparatus and method for selecting finite success states by indexing

Claim 1

A finite state automaton (FSA) responsive to a stream of input code elements, each code element consisting of a predetermined plurality of code bits, for searching the stream simultaneously for a plurality of specified query patterns each of which comprises an ordered plurality of code element query values; the FSA making transition in response to each input code element from one to another of a plurality of alternative states which include at least one multiple exit decision state in which the FSA searches simultaneously for a plurality of specified alternative code element query values that are code element values of respective query patterns; each code element query value being associated with a distinct next state to which the FSA makes transition in response to detection of that code element query value in the input stream; said FSA comprising input means for receiving an input stream of digital code data and for successively accessing from the stream a current one of said code elements for parallel delivery, control memory means including a plurality of state words associated with respective alternative states of the FSA, the state word associated with each said decision state including a series of ordered indexing bits corresponding to the respective possible values of said input code elements, with set bits designating said plurality of specified code element query values, and a code representation of a base state number having a predetermined relation to the next success state associated with a selected one of those query values, state register means for storing an identification of the current state and for accessing the contents of the state word associated with that state, action means controlled successively by the currently accessed input code element and by the currently accessed contents of the state word and including, when under control of the state word contents associated with said multiple exit decision state, means for simultaneously comparing said accessed input code element value and the set indexing bits in said accessed state word contents and for developing a match signal in response to detection of a match, means for deriving an index that represents the position among the set indexing bits of the bit corresponding to the input code element value, means for developing from said index and from the base state number represented in said accessed state word contents an identification of the next success state associated with the current input code element value, and means responsive to said match signal for storing the so developed next success state identification in said state register means as an identification of the next current state of the FSA.