A graph-based approach to symbolic functional decomposition of finite state machines

• Autorzy: Szotkowski P. , Rawski M. , Selvaraj H.
• Języki publikacji: EN

Abstrakty

EN

This paper discusses the symbolic functional decomposition method for implementing finite state machines in field-programmable gate array devices. This method is a viable alternative to the presently widespread two-step approaches to the problem, which consist of separate encoding and mapping stages; the proposed method does not have a separate decomposition step - instead, the state's final encoding is introduced gradually on every decomposition iteration. Along with general description of the functional symbolic decomposition method's steps, the paper discusses various algorithms implementing the method and presents an example realisation of the most interesting algorithm. In the end, the paper compares the results obtained using this method on standard benchmark FSMs and shows the advantages of this method over other state-of-the-art solutions.

Słowa kluczowe

EN

finite state machine; FSM; FPGA; functional decomposition

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2009
• Tom: Vol. 35, no 2
• Strony: 41--47
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Szotkowski P.

autor

Rawski M.

autor

Selvaraj H.

• Institute of Telecommunications, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warszawa, Poland,

Bibliografia

• [1] de Micheli G., Brayton R.K., Sangiovanni-Vincentelli A., Optimal state assignment for finite state machines, IEEE Trans, on CAD, pp. 269-284.
• [2] Jóźwiak L., Chojnacki A., Effective and efficient combinational circuit synthesis for the FPGA-based reconfigurable systems, Special Issue of Journal of Systems Architecture on Re-configurable Computing, 49(4-6), pp. 247-265.
• [3] Jóźwiak L., Ślusarczyk A., A new state assignment method targeting FPGA implementations, Proc. EUROMICRO Symposium on Digital System Design DSD 2000, pp. 50-59.
• [4] Lin B., Newton A.R., Synthesis of multiple level logic from symbolic high-level description languages, Proc. of IFIP Int. Conf. on VLSI, pp. 187-196.
• [5] Rafla N., Davis B., A study of finite state machine coding styles for implementation in FPGAs, 49th IEEE International Midwest Symposium on Circuits and Systems MWSCAS 2006, pp. 337-341.
• [6] Rawski M., The novel approach to FSM synthesis targeted FPGA architectures, Proceedings of IF AC Workshop on Programmable Devices and Systems PDS 2004, pp. 169-174.
• [7] Rawski M., Selvaraj H., Luba T., Szotkowski P., Application of symbolic functional decomposition concept in FSM implementation targeting FPGA devices, Sixth International Conference on Computational Intelligence and Multimedia Applications ICCIMA 2005, pp. 153-158.
• [8] Rawski M., Selvaraj H., Luba T., Szotkowski P., Multilevel synthesis of finite state machines based on symbolic functional decomposition, International Journal of Computational Intelligence and Applications, 6(2), 2007, pp. 257-271.
• [9] Ślusarczyk A., Decomposition and Encoding of Finite State Machines for FPGA Implementation, Technische Universiteit Eindhoven, 2004.
• [10] Szotkowski P., Rawski M., Symbolic functional decomposition algorithm for FSM implementation, Proceedings of the International Conference on Computer as a Tool EUROCON 2007, p. 484-488.
• [11] Szotkowski P., Rawski M., A graph-based symbolic functional decomposition algorithm for FSM implementation, to be published in proceedings of the Conference on Human System Interaction HSI 2008.
• [12] Titarienko L., Węgrzyn M., Optimization of Moore FSM on FPGA, CAD Systems in Microelectronics, 2007, CADSM’07, 9th International Conference - The Experience of Designing and Applications of, February 2007, pp. 246-250.
• [13] Villa T., Sangiovanni-Vincentelli A., Nova: state assignment of finite state machines for optimal two-level logic implementation, IEEE Trans, on CAD, pp. 905-924.
• [14] Welsh D.J.A., Powell M.B., An upper bound for the chromatic number of a graph and its application to timetabling problems, The Computer Journal, 10(1), 85-86.