Apparatus and method for generating state transition rules for memory efficient programmable pattern matching finite state machine hardware

• US 7,219,319 B2
• Filed: 06/06/2006
• Issued: 05/15/2007
• Est. Priority Date: 03/12/2004
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Sensory Networks, Inc. (Intel Corporation)
• Inventors: Gould, Stephen, Barrie, Robert Matthew, Williams, Darren, de Jong, Nicholas
• Primary Examiner(s): Dinh, Paul
• Application Number:
  US11/422,520
• Publication Number:
  US 20060253816A1
• Time in Patent Office: 343 Days
• Field of Search: 716 1- 2, 716 4- 5, 716 16- 18
• US Class Current: 326/46
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32

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.

Claims

1. A method of generating state transition rules, the method comprising:

forming a plurality of Boolean logic functions each associated with a different one of a plurality of next states to which transitions are configured to occur;

performing logic minimization operation on number of minterms associated with each of the formed plurality of Boolean logic functions;

identifying at least one of the plurality of Boolean logic functions having a smallest number of minimized minterms;

storing the minimized minterms of the identified at least one of the plurality of Boolean logic functions;

adding expanded minterms corresponding to minimized minterms of the identified at least one of the plurality of Boolean logic functions to the remaining ones of the plurality of Boolean logic functions;

performing a second logic minimization operation on number of minterms associated with each of the remaining ones of the plurality of Boolean logic functions;

identifying at least another one of the plurality of Boolean logic functions having a smallest number of minimized minterms following the second logic minimization operation; and

storing the minimized minterms of the identified at least another one of the plurality of Boolean logic functions;

wherein the stored minterms define the state transition rules and are in a ranking order of generality.

2. The method of claim 1 wherein the minimized terms are stored in a ternary content addressable memory.

3. The method of claim 1 wherein the ranking order of generality is an increasing order of generality.

4. The method of claim 1 wherein the ranking order of generality is a decreasing order of generality.

5. The method of claim 1 further comprising:

storing a corresponding entry for each of the plurality of next states.

6. The method of claim 5 wherein the corresponding entry for each of the plurality of next states is stored in a static random access memory.