NOVA: state assignment of finite state machines for optimal two-level logic implementation
- 1 January 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 9 (9) , 905-924
- https://doi.org/10.1109/43.59068
Abstract
The problem of encoding the states of a synchronous finite state machine (FSM) so that the area of a two-level implementation of the combinational logic is minimized is addressed. As in previous approaches, the problem is reduced to the solution of the combinatorial optimization problems defined by the translation of the cover obtained by a multiple-valued logic minimization or by a symbolic minimization into a compatible Boolean representation. The authors present algorithms for this solution, based on a novel theoretical framework that offers advantages over previous approaches to develop effective heuristics. The algorithms are part of NOVA, a program for optimal encoding of control logic. Final areas averaging 20% less than other state assignment programs and 30% less than the best random solution have been obtained. Literal counts averaging 30% less than the best random solutions have been obtainedKeywords
This publication has 12 references indexed in Scilit:
- PLA optimization using output encodingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Addendum to 'A kernel-finding state assignment algorithm for multi-level logic'IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1989
- ASYL: A Rule-Based System for Controller SynthesisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Symbolic Design of Combinational and Sequential Logic Circuits Implemented by Two-Level Logic MacrosIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986
- Logic Minimization Algorithms for VLSI SynthesisPublished by Springer Nature ,1984
- State Assignment of Asynchronous Sequential Machines Using Graph TechniquesIEEE Transactions on Computers, 1972
- The Coding of Internal States of Sequential CircuitsIEEE Transactions on Electronic Computers, 1964
- Some Techniques of State Assignment for Synchronous Sequential MachinesIEEE Transactions on Electronic Computers, 1964
- A Programmed Algorithm for Assigning Internal Codes to Sequential MachinesIEEE Transactions on Electronic Computers, 1962
- On the State Assignment Problem for Sequential Machines IIIEEE Transactions on Electronic Computers, 1961