Improving the iteration bound of finite state machines
- 13 January 2003
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1328-1331
- https://doi.org/10.1109/iscas.1989.100601
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.Keywords
This publication has 4 references indexed in Scilit:
- Look-ahead computation: Improving iteration bound in linear recursionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Parallel Viterbi decoding by breaking the compare-select feedback bottleneckPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Digital CommunicationPublished by Springer Nature ,1988
- High Rate Realization of Finite-State MachinesIEEE Transactions on Computers, 1975