Symbolic Functional Decomposition Algorithm for FSM Implementation

Abstract

This paper presents an algorithm of symbolic functional decomposition for the implementation of finite state machines in field programmable gate array (FPGA) circuits. Unlike previous approaches to this problem, which consist of separate encoding and mapping steps, this algorithm does not pre-encode the machine's states; instead, the states are encoded gradually during every step of the functional decomposition process (used for mapping the FSM to the FPGA circuit's LUT cells). This approach guarantees high quality of the final decomposition, with better results than the ones obtained by pre-encoding the FSM's states.