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

Abstract

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.