Serial decomposition of finite state machines for FPGA-based implementation

This paper presents a new method of the finite state machine logic synthesis intended for the modern FPGAs with embedded memory blocks. Although the functional decomposition is recognized as the most efficient method of digital circuits synthesis for implementation with FPGAs, none of the known state encoding algorithms is effective. This is caused by the fact that traditional methods comprise two steps: internal states encoding and, then, mapping of the encoded state transition table into target architecture. In this paper a new method of FSM state encoding is presented. It is an inherent part of the serial decomposition process and therefore no separate encoding step is required. It is shown that such state encoding guarantees the best solution. The paper presents examples from standard benchmark set, which confirm that the proposed method allows for a reduction of utilization of logic cells and embedded memory blocks.