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.