FPGA Implementation of Reconfigurable Finite State Machine with Input Multiplexing Architecture Using Hungarian Method

الملخص EN

The mathematical model for designing a complex digital system is a finite state machine (FSM).

Applications such as digital signal processing (DSP) and built-in self-test (BIST) require specific operations to be performed only in the particular instances.

Hence, the optimal synthesis of such systems requires a reconfigurable FSM.

The objective of this paper is to create a framework for a reconfigurable FSM with input multiplexing and state-based input selection (Reconfigurable FSMIM-S) architecture.

The Reconfigurable FSMIM-S architecture is constructed by combining the conventional FSMIM-S architecture and an optimized multiplexer bank (which defines the mode of operation).

For this, the descriptions of a set of FSMs are taken for a particular application.

The problem of obtaining the required optimized multiplexer bank is transformed into a weighted bipartite graph matching problem where the objective is to iteratively match the description of FSMs in the set with minimal cost.

As a solution, an iterative greedy heuristic based Hungarian algorithm is proposed.

The experimental results from MCNC FSM benchmarks demonstrate a significant speed improvement by 30.43% as compared with variation-based reconfigurable multiplexer bank (VRMUX) and by 9.14% in comparison with combination-based reconfigurable multiplexer bank (CRMUX) during field programmable gate array (FPGA) implementation.