Implementation of Finite State Machines on a Reconfigurable Device

We present a novel method for the implementation of finite state machines (FSM) using a reconfigurable architecture. The proposed method utilises run-time reconfiguration to reduce the hardware required to implement FSMs. This is achieved through the use of a unique representation of the FSM which allows the next state of the state machine to be calculated solely from the primary inputs rather than the primary inputs and the current state as would be traditionally required. This reduction in parameters significantly reduces the size of the hardware block required to calculate the next state. The paper presents results obtained for the MCNC benchmark suite that demonstrate hardware savings of around 90% for the majority of the FSMs investigated.