Skip to main content
Article
Multilevel Synthesis of Finite State Machines Based on Symbolic Functional Decomposition Concept
International Journal of Computational Intelligence and Applications
  • Mariusz Rawski, Warsaw University of Technology
  • Henry Selvaraj, University of Nevada, Las Vegas
  • Tadeusz Luba, Institute of Telecommunications Warsaw
  • Piotr Szotkowski, Warsaw University of Technology
Document Type
Article
Publication Date
6-1-2006
Abstract
This paper presents a Finite State Machine (FSM) implementation method based on symbolic functional decomposition. This novel approach to multilevel logic synthesis of FSMs targets Field Programmable Gate Array (FPGA) architectures. Traditional methods consist of two steps: internal state encoding and then mapping the encoded state transition table into target architecture. In the case of FPGAs, functional decomposition is recognized as the most efficient method of implementing digital circuits. However, none of the known state encoding algorithms can be considered as a good method to be used with functional decomposition. In this paper, the concept of symbolic functional decomposition is applied to obtain a multilevel structure that is suitable for implementation in FPGA architectures. The symbolic functional decomposition does not require a separate encoding step. It accepts FSM description with symbolic states and performs decomposition, producing such a state encoding that guarantees the optimal or near-optimal solution.
Keywords
  • Computer algorithms,
  • Decomposition method,
  • Field programmable gate arrays,
  • Gate array circuits,
  • Sequential machine theory
Language
English
Permissions
Use Find in Your Library, contact the author, or use interlibrary loan to garner a copy of the article. Publisher copyright policy allows author to archive post-print (author’s final manuscript). When post-print is available or publisher policy changes, the article will be deposited
Identifier
DOI: 10.1142/S1469026806001988
Citation Information
Mariusz Rawski, Henry Selvaraj, Tadeusz Luba and Piotr Szotkowski. "Multilevel Synthesis of Finite State Machines Based on Symbolic Functional Decomposition Concept" International Journal of Computational Intelligence and Applications Vol. 6 Iss. 2 (2006) p. 257
Available at: http://works.bepress.com/henry_selvaraj/18/