STATE ASSIGNMENT FOR HARDWIRED VLSI CONTROL UNITS

Finding a binary encoding of symbolic control states, such that the im plementation area of a digital control unit is minimized is well known to be NP-complete. Many heuristic algorithms have been proposed for t his state assignment problem. The objective of this article is to pres ent a comprehensive survey and systematic categorization of the variou s techniques, in particular, for synchronous sequential circuits with nonmicroprogrammed implementations. The problem is partitioned into th e generation and the satisfaction of coding constraints. Three types o f 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. S pecial coding requirements and testability-related aspects of state as signment are considered in a separate section. Different implementatio ns of the algorithms presented are also compared.