Improving the iteration bound of finite state machines

Abstract

A description is given of a general approach to improve beyond the given iteration bound the speed of an arbitrary synchronous finite-state machine (FSM) or a discrete-time finite-state Markov process. The methods proposed can be implemented with pipelined arrays of simple hardware modules, achieving a throughput rate on the order of the reciprocal of a single-gate delay or latch setup time, whichever is limiting, at the expense of latency. Combining the pipelined arrays and modules in parallel further increases the throughput, which is theoretically unbounded. The implemented concurrent FSM is fully efficient and has minimal overhead, where the complexity grows only linearly with the speedup. The approach is practical for FSMs with a small number of states, or other special structures Author(s) Horng-Dar Lin Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA Messerschmitt, D.G.