Title :
A theory of nondeterministic networks
Author :
Mishchenko, Alan ; Brayton, Robert K.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Univ. of California, Berkeley, CA
fDate :
6/1/2006 12:00:00 AM
Abstract :
Both nondeterminism and multilevel networks can be used to compactly characterize logic structures as well as all the flexibilities allowed for optimizing them. Synthesis results can be improved by allowing the manipulation of a larger class of networks called nondeterministic (ND) networks. These are multilevel logic networks that embody both nondeterminism and multivalued (MV) signals and, thus, enhance compactness and expressiveness. In this paper, a complete theory for representing and manipulating ND networks is developed. It is shown that an ND network´s behavior can be classified into at least three types, all of which coalesce when the network becomes deterministic. The theory addresses the classical transformations commonly applied to optimize deterministic binary networks, such as node minimization, elimination, and decomposition. These are analyzed with respect to their effects on each type of network behavior, leading to modifications of some operations to make them safe, i.e., guaranteeing that the new behavior remains within the network´s specification. Finally, it is proved that all three types of behaviors can be used in a hierarchical-synthesis paradigm
Keywords :
logic design; multivalued logic circuits; Boolean network; deterministic binary networks; hierarchical-synthesis paradigm; logic structures; logic synthesis; multilevel logic networks; multivalued signals; node decomposition; node elimination; node minimization; nondeterminism signals; nondeterministic networks; Contracts; Debugging; Helium; Logic functions; Multivalued logic; Neodymium; Network synthesis; Signal synthesis; Boolean network; don´t cares; logic behavior; logic flexibility; logic network; logic synthesis; multilevel network; multivalued logic; nondeterminism; partial cares; random simulation; simulation model;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2005.855978
