Apparatus and method for memory efficient, programmable, pattern matching finite state machine hardware
First Claim
1. A programmable finite state machine configured to transition to one of a plurality of next states from a current state in response to receipt of an input symbol, each of the current state and next states being represented by m bits and each input symbol being represented by k bits, the programmable finite state machine comprising:
- a first memory configured to store a plurality of transition rules, said first memory further configured to receive a (k+m)-bit word representative of the input symbol and the current state and to supply one or more matching transition rules in response, wherein the one ore more matching transition rules are stored in a ranking order of generality;
a logic block configured to select a most specific transition rule from among the one or more matching transition rules; and
a second memory configured to receive the selected transition rule and to supply one of the plurality of next states in response.
3 Assignments
0 Petitions
Accused Products
Abstract
A programmable finite state machine (FSM) includes, in part, first and second memories, and a selection circuit coupled to each of the memories. Upon receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state, the first memory supplies one ore more matching transition rules stored therein. The selection circuit selects the most specific of the supplied rules. The transition rules are stored in the first memory in a ranking order of generality. The second memory receives the selected transition rule and supplies the next state of the FSM. The first memory may be a ternary content addressable memory and the second memory may be a static random access memory. The contents of both the content addressable memory and the static random memory is determined by an algorithm which minimizes the number of terms required to represent the next-state transition functions.
-
Citations
25 Claims
-
1. A programmable finite state machine configured to transition to one of a plurality of next states from a current state in response to receipt of an input symbol, each of the current state and next states being represented by m bits and each input symbol being represented by k bits, the programmable finite state machine comprising:
-
a first memory configured to store a plurality of transition rules, said first memory further configured to receive a (k+m)-bit word representative of the input symbol and the current state and to supply one or more matching transition rules in response, wherein the one ore more matching transition rules are stored in a ranking order of generality; a logic block configured to select a most specific transition rule from among the one or more matching transition rules; and a second memory configured to receive the selected transition rule and to supply one of the plurality of next states in response. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. A method for transitioning to one of a plurality of next states from a current state in response to receipt of an input symbol, each of the current and next states being represented by m bits and each input symbol being represented by k bits, method comprising:
-
receiving a (k+m)-bit word representative of the k-bit input symbol and the m-bit current state; supplying one or more matching transition rules, wherein the one or more matching transition rules are stored in a ranking order of generality; selecting a most specific transition rule from among the one or more supplied matching transition rules; and supplying the one of the plurality of next states. - View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25)
-
Specification