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

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.