A Theory of Non Deterministic Networks Alan Mishchenko and Robert Brayton Portland State Univ and Univ of California Berkeley email alanmi ece psu edu and brayton eecs berkeley edu Abstract Both non determinism and multi level networks compactly characterize the flexibility allowed in implementing a circuit A theory for representing and manipulating non deterministic ND networks is introduced The theory supports the usual network manipulations done on deterministic binary networks such as node minimization elimination decomposition etc Three ways to interpret the behavior of an ND network are given Operations performed on ND networks are analyzed for how they can change behavior under each interpretation Some common network operations can increase different behaviors and thus might cause the network to violate its external specification Several methods to correct this problem are proposed 1 Introduction A non deterministic ND network is similar to a Boolean network except that nodes have multi valued MV outputs and are represented by non deterministic relations Don t cares are a form of non determinism where for some input minterms the output takes any allowed value More generally non determinism occurs when for an input minterm the output takes values from a subset of allowed values Non determinism and multi level networks offer compact ways to represent behaviors Non determinism arises naturally in a synthesis setting A system s specification is given by an ND network or ND automaton A known or well defined part of the system may be given also To be synthesized is an unknown component The set of all possible behaviors of the unknown component can be derived as an ND relation or automaton using complementation and composition operations 10 In logic synthesis an initial network representation is given along with possibly compatible don t cares at the primary outputs In some RTL specifications incomplete specification can be specified at internal nodes Incomplete specification is interpreted as don t cares i e for some inputs the output can be any value allowed for the variable Don t cares are also derived from the network s functionality as observability or satisfiability don t cares When these concepts are generalized to MV networks they give rise to non determinism Using the initial specification a Boolean network is manipulated to obtain a smaller one which finally is mapped into a set of logic gates for implementation in hardware An analogous network and set of operations is desired for ND networks It has been found that the use of such networks can lead to smaller deterministic binary implementations since the generalization to MV ND networks allows a wider scope for optimization algorithms 5 In developing a theory for ND networks some of the classical operations need to be modified to account for the presence of non determinism and the different effects caused by non deterministic nodes need to be clarified We define three network simulation models SS NS NSC for ND networks which reduce to the same behavior if the network is deterministic One of these is equivalent in the binary case to simulation with three values 0 1 X 1 We prove results about how the corresponding ND network behaviors can be changed under some common network operations such as decomposition substitute eliminate collapse node minimize and merge 8 We also study the limits within which the functionality of a node in an ND network can be changed without violating the external specification We show that for all behaviors the complete flexibility CF as computed in 4 correctly specifies all deterministic behavior that can be implemented at the node but unlike for NS and NSC for SS it incorrectly specifies ND behavior The computational procedures for network optimization proposed in 4 for finding a small ND implementation of an ND relation are supplemented with one that finds an exact minimum ND representation Minimum ND representations are never larger than minimum deterministic ones and often much smaller In Section 2 we define an ND network and introduce some notation Section 3 compares three methods for interpreting the behavior of an ND network Section 4 analyzes the changes in the behaviors caused by node minimization Section 5 examines the node elimination process Section 6 extraction and decomposition and Section 7 merging Section 8 discusses the relative merits of the two computationally viable behaviors NSC and SS Section 9 provides three methods for minimizing an ND relation including a new one for finding an exact minimum cover Section 10 discusses how a circuit can become non compliant when SS behavior is used and gives one method to correct this Section 11 concludes with some longer term goals for the application of this theory Because of space limitations we do not give any proofs of the theorems which can be found in 6 The main purpose of this paper is to present the theory and provide the set of results known so far 2 ND Networks 0 1 L n i An ND network is an acyclic directed graph A node represents an ND relation between its inputs and its single output An edge is directed from node i to j if the relation at node j depends syntactically on the variable yi associated with node i The output of node i can take values from domain D i Primary input nodes PI have no inputs Primary output nodes PO deliver the functionality of the network to its environment Single input and output storage element nodes have the next state NS variables as inputs and the present state PS variables as outputs Since this paper is concerned only with the combinational portion of the network the set PI PS is denoted CI and represented by the vector X and the set PO NS is denoted CO and represented by the vector Z The CI and CO are the combinational inputs and outputs respectively specRX Z is the set of all acceptable CI CO minterm pairs An external specification of a network These sets of pairs can be in two forms compatible or output m m such that symmetric and free A free external specification has no restrictions on which pairs are allowed except that it is well defined Rm m X 1 spec X Z Z Definition A relation is well defined if for each input minterm there exists at least one output minterm in the relation A free specification in the binary case has been called a Boolean relation 9 A compatible specification has an additional symmetry restriction Definition A relation produce a value for output zi in a set Si and any