Methodology for Distributed-ROM-Based Implementation of Finite State Machines

This brief explores the optimization of distributed-ROM-based finite state machine (FSM) implementations as an alternative to conventional implementations based on look-up tables (LUTs). In distributed-ROM implementations, LUTs with constant output value (called constant LUTs) and LUTs with the same content (called equivalent LUTs) can be saved. We propose a methodology to implement FSMs using distributed ROM that includes: 1) a greedy state encoding algorithm; 2) an algorithm to find the way of interconnecting the address signals to the ROM that maximize the number of constant or equivalent LUTs; and 3) a set of architectures to implement the columns of the ROM. The results obtained have been compared with conventional LUT-based implementations using standard benchmarks. The proposed technique reduces the number of LUTs in a 91% of cases and increases the speed in all cases.