Improvements to Symbolic Functional Decomposition Algorithms for FSM Implementation in FPGA Devices

• Autorzy: Szotkowski P. , Rawski M.
• Konferencja: Digital Control Units Design ; 6.03.2009 ; Zielona Góra, Poland
• Języki publikacji: EN

Abstrakty

EN

The method of symbolic functional decomposition for FSM implementation in FPGA devices yields better results than the currently widespread, two-step approaches based on state encoding and mapping of the resulting binary function. This paper presents the method using an example FSM and briefly discusses the existing algorithms, along with results obtained for benchmark FSMs. The paper also proposes a heuristic algorithm for input selection as well as a new, clique-based algorithm for the construction of the crucial decomposition blankets.

Słowa kluczowe

EN

finite state machine; FPGA; FSM; symbolic functional decomposition

• Wydawca: Polish Academy of Sciences, Committee of Electronics and Telecommunication
• Czasopismo: Electronics and Telecommunications Quarterly
• Rocznik: 2009
• Tom: Vol. 55, No 2
• Strony: 335--354
• Opis fizyczny: Bibliogr. 13 poz., tab., wykr.

Twórcy

autor

Szotkowski P.

autor

Rawski M.

• Institute of Telecommunications Warsaw University of Technology, Poland,

Bibliografia

• 1. J. A. Brzozowski, T. Łuba: Decomposition of boolean functions specified by cubes. Journal of Multiple-Valued Logic and Soft Computing, 9: 277-417, 2003.
• 2. G. de Micheli, R. K. Brayton, A. Sangiovanni-Vincentelli: Optimal state assignment for finite state machines. IEEE Trans. on CAD, pp. 269-284.
• 3. L. Jóźwiak, A. Ślusarczyk: A new state assignment method targeting FPGA implementations. Proc. EUROMICRO Symposium on Digital System Design DSD 2000, pp. 50-59.
• 4. B. Lin, A. R. Newton: Synthesis of multiple level logic from symbolic high-level description languages. Proc. of IFIP Int. Conf. on VLSI, pp. 187-196.
• 5. M. Rawski: The novel approach to FSM synthesis targeted FPGA architectures. Proceedings of IFAC Workshop on Programmable Devices and Systems PDS 2004, pp. 169-174, 2004.
• 6. M. Rawski, L. Jóźwiak, T. Łuba: Functional decomposition with an efficient input support selection for sub-functions based on information relationship measures. Journal of Systems Architecture, (47): 137-155, 2001.
• 7. M. Rawski, H. Selvaraj, T. Łuba, P. Szotkowski: Multilevel synthesis of finite state machines based on symbolic functional decomposition. International Journal of Computational Intelligence and Applications, 6(2): 257-271, 2007.
• 8. C. Scholl: Functional Decomposition with Application to FPGA Synthesis. Kluwer Academic Publishers, 2001.
• 9. A. Ślusarczyk: Decomposition and Encoding of Finite State Machines for FPGA Implementation. Technische Universiteit Eindhoven, 2004.
• 10. P. Szotkowski, M. Rawski: Symbolic functional decomposition algorithm for FSM implementation. Proceedings of the International Conference on Computer as a Tool EUROCON 2007, pp. 484-488, 2007.
• 11. P. Szotkowski, M. Rawski: A graph-based symbolic functional decomposition algorithm for FSM implementation. To be published in proceedings of the Conference on Human System Interaction HSI 2008, 2008.
• 12. P. Szotkowski, M. Rawski, H. Selvaraj: A graph-based approach to symbolic functional decomposition of finite state machines. To be published in proceedings of the International Conference on Systems Engineering ICSEng 2008, 2008.
• 13. T. Villa, A. Sangiovanni-Vincentelli: Nova: state assignment of finite state machines for optimal two-level logic implementation. IEEE Trans. on CAD, pp. 905-924.