NOVA: state assignment of finite state machines for optimal two-level logic implementations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

NOVA: state assignment of finite state machines for optimal two-level logic implementations

Full text

Pdf (865 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 26th ACM/IEEE Design Automation Conference table of contents

Las Vegas, Nevada, United States

Pages: 327 - 332

Year of Publication: 1989

ISBN:0-89791-310-8

Authors

T. Villa	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California,
A. Sangiovanni-Vincentelli	Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, California,

Sponsors

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CS\TCDA : TC Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 27, Citation Count: 18

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/74382.74437 What is a DOI?

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. In this paper we present algorithms for their solution, based on a new 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 solutions have been obtained. Literal counts averaging 30% less than the best random solutions have been obtained.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	GaJ79	R. Garey, D.S. Johnson, "Computers and intractability", Freem an, 1979
	MSV83	G. De Michel.i, A. Sangiovanni-Vineentelli and T.Villa, "Computer-aided synthesis of PLA-based Finite State Machines", ICCAD, September 1983, S.Clara
	DeM83	Giovanni De Micheli, Computer-aided synthesis of pla-based systems, 1983
	BHM84	Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
	DBS85	G. De Michdi, R.K. Brayton and A. Sangiovanni- Vincentelli, "Optimal State Assignment for Finite State Machines", IEEE Trans. on CAD, CAD-4(3), pp. 269- 284, July 1985
	DeM86	G. De Micheli, "Symbolic Design of Combinational and Sequential Logic Circuits Implemented by Two-level Logic Macros", II~E Trans. on CAD, CAD-5(4), pp. 597-616, October 198 6,
	Vil87	T. Villa, "Constrained Encoding in Hypercubes: Algorithms and AppLications to Logical Synthesis". Mem. UCB/ERL M87/37, U.C. Berkeley, May 1987
	DMa87	S. Devadas, H.T. Ma, A.R. Newton and Sangiovanni- Vincentelli, "MUSTANG: State Assignment of Finite State Machines for Optimal Multi-Level Logic Implememations", ICCAD, November 1987, S.Clara
	Sal88	A. Saldanha, "Pla Optimization Using Output Encoding", U.C. Berkeley Master's Report, August 1988
	SaV88	A. Saldanha, T.ViUa, "Symbolic Minimization Revisited", UCB/ERL Memo in preparation, September 1988
	Vil88	T. Villa, "NOVA", User's manual, U.C. Berkeley, October 1988 ar~a : l

CITED BY 18

	R. Leveugle, Optimized state assignment of single fault tolerant FSMs based on SEC codes, Proceedings of the 30th international conference on Design automation, p.14-18, June 14-18, 1993, Dallas, Texas, United States
	Mark Beardslee , Alberto Sangiovanni-Vincentelli, An algorithm for improving partitions of pin-limited multi-chip systems, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.378-385, November 07-11, 1993, Santa Clara, California, United States
	Mark Beardslee , Bill Lin , Alberto Sangiovanni-Vincentelli, Communication based logic partitioning, Proceedings of the conference on European design automation, p.32-37, November 1992, Congress Centrum Hamburg, Hamburg, Germany
	G. Cabodi , P. Camurati , L. Lavagno , S. Quer , R. Brayton , E. Sentovich, Incremental re-encoding for symbolic traversal of product machines, Proceedings of the conference on European design automation, p.158-163, September 1996, Geneva, Switzerland
	Sybille Hellebrand , Hans-Joachim Wunderlich, An efficient procedure for the synthesis of fast self-testable controller structures, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.110-116, November 06-10, 1994, San Jose, California, United States
	A. Both , B. Biermann , R. Lerch , Y. Manoli , K. Sievert, Hardware-software-codesign of application specific microcontrollers with the ASM environment, Proceedings of the conference on European design automation, p.72-76, September 19-23, 1994, Grenoble, France
	Bernhard Eschermann, State assignment for hardwired VLSI control units, ACM Computing Surveys (CSUR), v.25 n.4, p.415-436, Dec. 1993
	David Binger , David W. Knapp, Automatic synthesis of a dual-PLA controller with a counter, Proceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture, p.149-157, November 27-29, 1990, Orlando, Florida, United States
	Gabriele Saucier , Christopher Duff , Franck Poirot, State assignment of controllers for optimal area implementation, Proceedings of the conference on European design automation, March 12-15, 1990, Glasgow, Scotland
	L. N. Kannan , D. Sarma, Fast heuristic algorithms for finite state machine minimization, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Andre DeHon , Michael J. Wilson, Nanowire-based sublithographic programmable logic arrays, Proceedings of the 2004 ACM/SIGDA 12th international symposium on Field programmable gate arrays, February 22-24, 2004, Monterey, California, USA
	Bapiraju Vinnakota , Niraj K. Jha, MACHETE: synthesis of sequential machines for easy testability, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	S. T. Chakradhar , S. Kanjilal , V. D. Agrawal, Finite state machine synthesis with fault tolerant test function, Proceedings of the 29th ACM/IEEE conference on Design automation, p.562-567, June 08-12, 1992, Anaheim, California, United States
	Pranav Ashar , Srinivas Devadas , A. Richard Newton, A unified approach to the decomposition and re-decomposition of sequential machines, Proceedings of the 27th ACM/IEEE conference on Design automation, p.601-606, June 24-27, 1990, Orlando, Florida, United States
	I. Pomeranz , K.-T. Cheng, State assignment using input/output functions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.573-577, June 08-12, 1992, Anaheim, California, United States
	G. Tarroux , B. Rouzeyre , G. Sagnes, Optimization of micro-controllers by partitioning, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	Kwang-Ting Cheng , Vishwani D. Agrawal, Initializability Consideration in Sequential Machine Synthesis, IEEE Transactions on Computers, v.41 n.3, p.374-379, March 1992
	Stefano Quer , Gianpiero Cabodi , Paolo Camurati , Luciano Lavagno , Ellen M. Sentovich , Robert K. Brayton, Verification of Similar FSMs by Mixing Incremental Re-encoding, Reachability Analysis, and Combinational Checks, Formal Methods in System Design, v.17 n.2, p.107-134, Oct. 2000