Application of symbolic functional decomposition concept in FSM implementation targeting FPGA devices

This paper presents an FSM implementation method based on symbolic functional decomposition. This novel approach in multilevel logic synthesis of finite state machines targets FPGA architectures. Traditional methods are based on 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 implementing in FPGA logic cells. The symbolic decomposition does not require separate encoding step. It accepts FSM description with symbolic states and performs decomposition introducing such a state encoding that guarantees the best solution known.