Apparatus and method for large hardware finite state machine with embedded equivalence classes
US7180328B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 21, 2004 |
| Grant date | Feb 20, 2007 |
| Priority date | — |
| Expiry date | Jun 27, 2025 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/4498
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A programmable finite state machine (FSM) includes, in part, a first address calculation logic block, a first lookup table, a second address calculation logic block, and a second lookup table. The first address calculation logic block generates an address for the first lookup table based on the received input symbol and the current state. The data stored in first look-up table at the generated address is used by the second address calculation logic block to compute an address for the second lookup table. Data stored in the second lookup table is the next state to which the FSM transitions. The programmable FSMs uses redundant information of the transition table to compress these transitions and thus requires a smaller memory while maintaining a high data throughput. The data in the first and second lookup tables are coded and supplied by a compiler. The FSM operation may optionally be pipelined.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.