Thumbnail
Access Restriction
Subscribed

Author Eschermann, Bernhard
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1993
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword VLSI ♦ Built-in tests ♦ Coding constraints ♦ Computer-aided design ♦ Control design ♦ Finite-state machines ♦ Integrated circuits ♦ Logic design ♦ Sequential circuits ♦ State assignment ♦ Synthesis ♦ Testability
Abstract Finding a binary encoding of symbolic control states, such that the implementation area of a digital control unit is minimized is well known to be NP-complete. Many heuristic algorithms have been proposed for this state assignment problem. The objective of this article is to present a comprehensive survey and systematic categorization of the various techniques, in particular, for synchronous sequential circuits with nonmicroprogrammed implementations. The problem is partitioned into the generation and the satisfaction of coding constraints. Three types of coding constraints—adjacency, covering, and disjunctive constraints—are widely used. The constraint satisfaction algorithms are classified into column-based, row-based, tree-based, dichotomy-based, and global minimization approaches. All of them are illustrated with examples. Special coding requirements and testability-related aspects of state assignment are considered in a separate section. Different implementations of the algorithms presented are also compared.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1993-12-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 25
Issue Number 4
Page Count 22
Starting Page 415
Ending Page 436


Open content in new tab

   Open content in new tab
Source: ACM Digital Library