Apparatus and method for generating state transition rules for memory efficient programmable pattern matching finite state machine hardware
US7219319B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 6, 2006 |
| Grant date | May 15, 2007 |
| Priority date | — |
| Expiry date | Jun 6, 2026 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L63/12
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.