THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY PSEUDO-BOOLEAN LOGIC CIRCUITS John P. Hayes CRL-TR-33-84 August 1984 Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA Tel: (313) 783-8000

PSEUDO-BOOLEAN LOGIC CIRCUITS by John P. Hayes Department of Electrical Engineering and Computer Science University of Michigan Ann Arbor, MI 48109 June 1984 This research was supported by the National Science Foundation under Grant ECS-8214709.

Abstract A new class of switch-level logic circuits intended for modeling digital MOS VLSI circuits is presented. These circuits, which are called pseudo-Boolean, are composed of a single (voltage) source, connectors, switches, attenuators and wells. The latter two devices are digital versions of resistors and capacitors, respectively, and may assume an arbitrary but finite number of different sizes. Signals are bidirectional, and are assigned a finite set of values of the form (v, s), where v corresponds to voltage level, and 8 corresponds to electrical current or charge level (logical strength). It is shown that these signal values and the associated logical operations form a generalization of Boolean algebra called pseudo-Boolean or Heyting algebra. The analysis of pseudo-Boolean circuits using discrete counterparts of Kirchoff's Current Law and the Superposition Principle is discussed, as well as the application of pseudo-Boolean techniques to digital simulation. Keywords: Digital simulation, logic design, MOS circuits, pseudo-Boolean algebra, switch-level simulation, switching theory, VLSI design.

1. Introduction In the design of MOS VLSI circuits, based for example, on the Mead-Conway philosophy [1], a central role is played by CAD programs that can accurately simulate the behavior and layout of very large logic circuits. Traditional gate-level logic simulators are of limited value for this purpose, since they cannot directly model such MOS logic elements as transistor switches, pull-up loads, bidirectional buses, and the like [2]. Analog simulators such as SPICE, on the other hand, although capable of modeling all types of MOS circuits at the electrical level, require too much computation time when applied to very large digital circuits. To deal with this situation, a new class of simulation programs called switch-level simulators have recently been developed [3,4,5]. These simulators employ transistor-like devices as primitive components, and so can more accurately model the behavior and layout structure of VLSI circuits than gate-level simulators. Because they represent circuit behavior by a small set of discrete logic values rather than a potentially infinite number of analog values, switch-level simulators can also handle much more complex circuits than analog simulators. This paper investigates the theoretical basis of switch-level simulation models, with the goal of better understanding their underlying algebraic structure. Previous work in this area includes the connector-switch-attenuator (CSA) theory of Hayes [2,5], and the switch-level model theory of Bryant [4,7]. In the present paper a new and very general class of CSA switch-level logic circuits is defined which seem especially useful for MOS VLSI simulation. These circuits encompass most existing types of logic circuits, and allow the modeling accuracy to be varied systematically by changing the number of logic values and component parameters used. It is shown that the algebraic structure

2 underlying these circuits is a generalization of Boolean algebra called pseudo-Boolean or Heyting algebra 18], hence the logic circuits in question are termed pseudo-Boolean. Section 2 defines the global structure of pseudo-Boolean logic circuits, and derives the set Ln of static logic values used from discrete current, voltage, and resistance concepts. In Sec. 3 the lattice structure of L, is explored, and is shown to constitute a pseudo-Boolean algebra. A wide range of both unidirectional and bidirectional primitive logic elements for pseudo-Boolean circuits are discussed in Sec. 4. The use of dynamic logic values and digital charge-storage devices (wells) to model sequential behavior is considered in Sec. 5. Finally, Sec. 6 presents some applications of the proposed theory. 2. Basic Concepts The logic values of interest are required to represent the binary electrical signals employed in real logic circuits. This binary requirement is met by permitting only one type of source device S for generating the logical constants 0 and 1. S corresponds to an electrical voltage source that produces a constant potential difference of V volts across its terminals. The terminals of S are held at two distinct voltage levels VL and VH = VL + V, representing logical 0 and 1, respectively. To ensure that all normal voltage levels are confined to the binary set {VH, VL}, we require that all source devices have one terminal connected to a common point (ground). This prevents two copies of S from being connected in series to generate a third voltage level VL + 2V. We also require all voltage-like measurements to be made relative to ground. This eliminates the possibility of obtaining another voltage of the form -V from S. Thus all copies of the source S are effectively connected in parallel, with one terminal connected to a common ground that serves as a reference for logic value measurement.

3 Such a parallel connection of sources is functionally equivalent to a single source. Hence, without much loss of generality, we only consider logic circuits that contain a single voltage source S corresponding to the main electrical power supply. (Note that a dual theory can also be developed in which S is a current rather than a voltage source). The overall structure of a single-source (pseudo-Boolean) logic circuit N is depicted in Fig. 1. Its purpose is to realize functions of the form fj (X), where X = (zX, Z2, *', X ) denotes a set of externally controlled input variables. The function value f, (X) has a measurable voltage-like component v, E {0, 1}. v, is determined by the connections established between the f, output terminal of N and either the terminals So and S1 of the source S or the primary inputs X. These connections are made or broken by logic elements such as switches, gates, etc. For example, if switch settings in N create a path from f, to the constant terminal S1 as shown in Fig. 2a, then VJ assumes the value 1. Similarly, a path joining fj to So makes vj = 0; see Fig. 2b. In most types of logic circuits, v, is restricted to the set {0, 1}. However, there are two other possible values that v, can assume, which are also illustrated in Fig. 2. If f, is simultaneously connected to both sides of S (Fig. 2c), a situation that could result from a short-circuit fault, then v, assumes a third value denoted U. This logic value can be thought of as an intermediate voltage level VI lying somewhere between VL and VH, e.g., (VH- VL)/2. fj can also be completely disconnected from the voltage source S, as indicated in Fig. 2d, in which case it is assigned the value Z corresponding to the familiar high-impedance state. The output condition v, = Z occurs explicitly in tristate logic circuits; in other logic circuits, Z is only encountered on internal lines. The set LI = {0, 1, U, Z} constitutes the basis from which all logic values are derived. It is easily seen that if the circuit N of Fig. 1 is composed of switches that make and break connec

4 VH =1 H x. —- i fl(X) Voltage V |*1; * VL 5 ~ Voltage/-S, -. * Pseudo-Boolean ofjX) s _PReference (ground) voltage Fig. 1. Overall structure of a pseudoBoolean circuit. 1 S1 v^ - v.=O on 0 (a) (b) — Reference (ground) voltage S1 1 v.=U v.=Z 0 -i- 0 1i~ ~0 o 0 So So (c) (d) Fig. 2. Voltage values assumed by output f, (X) of Fig. 1.

5 tions, any logic function defined on L1, or its binary subset B2 = {0, 1), can be realized. With ideal on-off switches of the type defined in Fig. 3 we can construct connector-switch (CS) networks [2] to realize any logic function defined on L1. Positive and negative switches correspond to n-channel and p-channel MOS transistors, respectively. Figure 4, for instance, shows a CS implementation of the Boolean NAND function z = X1z2 defined on B2 = (0, 1}. This circuit closely models the structure and behavior of a CMOS NAND gate. The logic values Z, U E L1, are useful in analyzing the behavior of logic circuits of this type under fault conditions [9]. From an electrical viewpoint, a CS circuit such as that of Fig. 4 is a source-resistor network [10] in which only two resistance values occur: Ro = 0 corresponding to an ideal conductor or a closed switch, and R. = oo corresponding to an open switch. It is very useful to introduce a fixed number n-1 of additional finite nonzero resistance values R,, R2,, Rn_ where R+l > R. We now have a set R = Ro, R1,..., R, of n+l resistance values from which we get a corresponding set of electric current values i=, I1, I, *, I. via Ohm's Law A3= V (1) Here V is the (fixed) magnitude of the voltage produced by circuit's source S. Suppose now that resistors with values defined in R are introduced into the network N of Fig. 1. Thevenin's theorem [10] implies that the circuit feeding any output fj is equivalent to the circuit appearing in Fig. 5. R, is the effective resistance of the source as seen by fj. As discussed later, by suitably defining the rules for combining discrete resistances, we can ensure that R, E R. We can therefore characterize the signal appearing at f, by the pair (,, where V is the open-circuit voltage at f,, and lj =. — is the short-circuit current at fj. We could equally well replace (V1, Ij) by

Behavior Type Symbol c = 1 c = c Positive a b a -- -- b C Negative a b a- — b a-b Fig. 3. Two types of ideal switch. ______ ~ Z = X1X2 F4 ntX2i 4 CershmN0 Fig. 4. Connector-switch model of a CMOS NAND gate.

7 (Vj, Rj) or (Vj, Gj), where G, == /Rj denotes electrical conductance. It is sometimes convenient to represent each logical signal value more abstractly by a pair of the form (v,, 8s), where v, E {0, 1, U, Z} = L, and 8j E {O, 1, * * *, n} = S.. v, may be called the signal's level, while 8j is its strength. As noted above, 8j can be interpreted as current, resistance, or conductance. Here 8- = 0 represents the maximum strength corresponding to Ro = 0 and Io = 0o, while s, = n represents the minimum strength corresponding to R= - oo and I. = 0. (Note that a slightly different strength numbering convention is used in [2,9].) The three levels 0, 1, U can be combined with all members of S,,-{n} to yield 3n distinct logic values. All values of the form (vi, n) and (Z, 8 ) are taken to be equivalent to the high-impedance state denoted by (Z, n), because the zero current I, = 0 can only be drawn from an open-circuited source. Hence the n+1 strength levels S, give rise to a set L, of 3n+l distinct signal values. For example, with n==2 we obtain the seven values L2= (0, 0), (0, 1), (1, 0), (1, 1), (U, 0), (U, 1), (Z, 2)} (v, 0) may be termed the strong [5] or forcing [3] version of v, while (v, 1) is the weak or non-forcing version. Resistor-like devices that only assume values from the discrete set R are termed attenuators [2] and are denoted by the symbol given in Fig. 5b. The attenuator transforms a strong signal (v, s) to a weaker signal (v, 8' ) where s' >s; note, however, that it does not change the logical level v of the signal. (A more precise definition of attenuator behavior is given later). Circuits like that of Fig. 4 that also contain attenuators have been called connector-switch-attenuator (CSA) circuits [2). For example, if an attenuator R is placed in series with each switch in Fig. 4, we obtain a CMOS NAND model in which the source-drain resistance of each transistor in the on state is R rather

8 Resistor R. 0-44 —W —-- fj Voltage Open-circuit Short-circuit source V. voltage j j current (a) Strong Weak (Vj,o) Attenuator Rj (Vj, I) ( _V i 3 J3 i+ota Voltage r source V. (b) Fig. 5. (a) Thevenin equivalent of a source-resistor circuit; (b) Corresponding source-attenuator circuit. (v2,i) - _V2_ i,(v, i) =#((vii ), (v2,i2),' / Connector* (r'ir)) / P (Vrir) -- Fig. 6. Behavior of a connector with respect to L.n

9 than zero. This switch-attenuator model of. a transistor corresponds to the primitive switch used in MOSSIM [4]. 3. Signal Evaluation Suppose that r voltage-current signals (v, il), (v2, i2),...., (v, i,) from L, are applied to a connector P as in Fig. 6. P assumes a value S(P) = (v, i) termed the state of P, which is required to be a member of Ln also. Kirchoff's Current Law suggests that the strength (current) components of the applied signals might be summed to yield the strength of S(P) thus::= ij (2) j=1 Ordinary summation, however, can lead to values of i that are not in the (n+l)- member set I of available current values. We therefore replace (2) by the approximation i=MAX{ij} (3) which takes i to be the maximum of the applied current signals, thereby guaranteeing that i E i. Thus the (current) strength of the output signal (v, i) is that of the strongest input signal. Equation (3) can be regarded as a discrete version of Kirchoff's Current Law appropriate to pseudo-Boolean circuits. The voltage component v of the connector state S(P) = (v, i) in Fig. 6 may be computed as follows. Let W = {vl, v2, *,vm } denote the voltage levels of all applied signals (vt, i ) for which it = MAX {ij }= i. There are four possible cases: (a) v=U if U E Wor0, 1 W.

10 (b) v =OifOE Wandl, U I H'. (c) v=lif 1 E Wand0, U i W. (4) (d) v =Zif 0,1, U W. These rules for combining discrete voltages are consistent with the behavior of analog voltages. For example, if (0, i) and (1, i) are the only signals applied to P, we would expect P to assume an intermediate voltage level, represented here by U, that lies approximately halfway between the 0 and 1 levels. The foregoing rules for computing (v, i) can be combined into a single operation # by observing that L. is a lattice. The # operator corresponds to the lattice operator that is variously called least upper bound, join, and or. Thus for Fig. 6 we can write (v, i)= #((vl il), (V2, i2),.*,(V*, i )) The lattice structure of L, has been recognized for some time as underlying switch-level simulators. We now demonstrate that L,, L2, * L, form a class of pseudo-Boolean algebras, which explains our use of the term pseudo-Boolean logic circuit. A lattice L is a set with a partial ordering < such that every pair of elements a, b E L have a least upper bound a U b = #(a, b), and a greatest lower bound a n b. An element 1 in L with the property a < 1 for all a E L is termed a unit element, while an element 0 such that 0 < a for all a E L is a zero element. A finite lattice, but not necessarily an infinite one, always contains unit and zero elements. An element c E L is called the pseudo-complement of a relative to 6, if c is the greatest element such that a n c < b; following [8j c is denoted by a= b. A lattice L is said to be relatively pseudo-complemented if a=-b exists for all a, b E L. Such a lattice must contain a unit element 1, since for any a E L, a=-a=1. A relatively pseudo

11 complemented lattice with a zero element 0 is called a pseudo-Boolean or Heyting algebra. For every element a in a pseudo-Boolean algebra, there is an element a=>0, which is called the pseudo-complement of a and is denoted by -a. A pseudo-Boolean algebra is therefore an abstract algebra L with the binary operations U, n, and =E, the unary operation -, and the special elements 0 and 1. This type of algebra was first defined about 1930 to characterize intuitionistic logic [8]. Boolean algebras form a special class of pseudo-Boolean algebras in which the pseudo-complement operator - is replaced by a stronger complement operator- (overbar). Pseudo-Boolean algebras obey the associative, commutative and distributive laws for n and U. The pseudocomplement operator obeys such familiar laws as a n -a = 0 and -(a U b) = -a n -b However, the idempotence law a = a of Boolean algebra is replaced by a < — a in pseudo-Boolean algebra. It follows directly from the foregoing definition that L, is a pseudo-Boolean algebra with 0 = (Z, n) and 1 = (U, 0). Values of the form (0, i) and (1, i) are each other's pseudo-complement relative to (U, i+1). Only in the case n=1 is Ln also a Boolean algebra. Returning to the general pseudo-Boolean circuit of Fig. 1, we see that the value assumed by an output signal fj with respect to L, is determined by the effective resistance of the paths linking f, to the source S. Figure 7 shows a representative case; compare Fig. 2. R, and Rk model a voltage divider circuit that which is only capable of

12 ___ _ _ v,, - (1,0) aRi (1,Ii) if I. Ik + ( 4 s(1 I1 S = #((l Ii),(oIk)) (o,1k) if I <k Source C ) 1T * f. l(U,I.) if I. Ik Source f (o-,Ik) _ V ( VL = (0,0o) Fig. 7. Voltage-current values assumed by output fj(X) of Fig. 1. in X. xl ^ out x (v',i') x 2 _ General "'.^~X component * M (V" Ottf in Line L n x --- n oMut n (a) (b) Fig. 8. Bidirectional signals associated with (a) a line L; (b) an arbitrary component M.

13 assigning v(fj) to the discrete voltage levels 0,1,U,Z. (Recall that when I, = Ik = 0, (U,,) = (Z, n).) As observed already, fj is usually restricted to the 0 and 1 levels in logic circuits. Consequently, the attenuator circuit of Fig. 7 acts as a threshold circuit with respect to voltages, only assigning them to the 0 and 1 levels. The existence of such a strong threshold effect is characteristic of binary circuits. The addition of an unrestricted number of strength levels allows a much wider range of logic circuit behavior and structure to be modeled than is possible with conventional Boolean logic circuits. As Fig. 7 suggests, an abstract logic signal (v, 8) may be assigned a direction indicated by an arrow in much the same way as an electric current. The source S of a circuit N supplies maximum-strength signals of the form (1,0) and (0,0) from which all other signals in N are ultimately derived; these signals have a natural direction away from S. In general, a line L can have two opposing signals (v',s') and (v'',s'') associated with it, as illustrated in Fig. 8a. The resultant state S(L) of L is expressed by S(L)= (v, ) = #((v', 8 ), (v,' )) (5) Equation (5) defines a Superposition Principle analogous to that of electrical network theory, where summation of voltages and currents is replaced by the lattice operator #. In general, a pseudo-Boolean circuit can be constructed from any primitive components with bidirectional input-output signals defined on L,; see Fig. 8b. Each output signal ziou is typically a function of the input signals zi", zx, X * * A, and may be defined by a truth table or an equation. For example, if M in Fig. 8b is a simple connector, we can define its behavior by the following set of pseudo-Boolean equations:

14 X - =:2, # Z:, **', X) XI = #( Z w3 Xn) Z = #(z ", 4",n xn1) The state S(M) of the connector is given by #( in, out)= #(n", )=-***= #(,, ^) Unidirectional lines are represented by setting either zx" or t^ut to the null signal (Z, n). Thus pseudo-Boolean circuits can be defined which represent any unidirectional components such as gates, multiplexers, etc., as well as bidirectional devices such as buses and transmission gates. Classical Boolean logic circuits, and special circuit types such as tristate logic, wired logic, and open-collector logic are all examples of pseudo-Boolean circuits. 4. Component Types With the foregoing machinery, we can define a powerful set of logic elements to model many different types of digital circuits. Figure 9 shows an assortment of connectors that transmit signals unchanged in either one or two directions. The triangle symbol can be thought of as a current amplifier (a unidirectional device) with unit gain; it can also be viewed as an arrowhead denoting signal direction. In the case of Fig. 9c, for instance, the signal b n applied to b has no affect on a, since by the Superposition Principle, S(a) = # (a", (Z, n)) = a".

15 in out (,i) x (v,i) zO = (v,i x -- -= z x t = (Zn) zn (Z,n) (a) (b) in out in a b a a -- — >- b aOUt (Z,n) bin (c) in out in a b a a * * b a b out in in a b b (d) (e) Fig. 9. Terminals and connectors: (a) input terminal; (b) output terminal; (c) unidirectional line: (d) bidirectional line: (e) equivalent circuit for a bidirectional line. C in c out bin a b in bout Fig. 10. A three-terminal poa bipor or MS Fig. 10. A three-terminal positive switch representing a bipolar or MOS transistor.

16 A positive switch may be represented as shown in Fig. 10. Here the control input c is assumed to be a unidirectional input terminal, while the a and b terminals are bidirectional. The on-off state of the switch can be made any function of a i bin, cin, a out bout c ut that reflects the underlying device technology. For example, if c'i = (1, ij) turns the switch on, and c'" = (0, i,) turns it off for any ij, we can specify the corresponding a out and b " signals in the following truth-table form, which is the usual definition of an ideal switch, c1 a out b out Switch State (6) (1,ii) b"5 a"a On (0, i) (Z, n) (Z, n) Off We can also define more complex behavior where the switch's state depends, say, on the relative voltage levels of the b and c terminals; this is typical of both bipolar and MOS transistors. Consider the following partial definition of switch behavior. S(a) c" a out b out Switch State (0, i,) (1, )'" a " On (0, i) (0, i (,.n) (Z, n) Off (7) (1, ij) (0, i) (Z, n) (Z, n) Off (1, i,) (1l it) (Z, n) (Z, n) Off Let the switch be initially off with S(a) = a'" = (0, ii), b'" = (1, im) and c" = (1, it),

17 where im > ij. According to (7), the switch should immediately turn on, making S(a) = #(a"', b")= (1, im). This new value of S(a) turns the switch off, causing S(a) to resume its original value (0, is). Thus a contradictory condition is obtained corresponding to oscillation in a physical device. An even richer range of switch behavior, including sequential behavior, becomes possible when the values (U, ij) and (Z, n) are permitted on the control input c. As demonstrated by Fig. 5, the function of an attenuator is to reduce the strength of an input signal. It therefore resembles a current amplifier with a gain less than unity, as suggested by the reversed amplifier symbol in the attenuator symbol. While an attenuator is often used only to attenuate unidirectional signals, it most frequently represents an analog resistor, an inherently bidirectional device. The general behavior of a bidirectional attenuator, and a more appropriate symmetric circuit symbol for it are specified in Fig. 11. An attenuator is associated with a current Ij determined by its size (resistance value) Rj according to Eq. (1). It transmits an applied signal (v, i) leaving v unchanged, but reducing i to the lesser of i and Ij. This behavior approximates the current-reducing role of an analog resistor, while ensuring that the resulting current is confined to the discrete set I. The relationship between electrical and pseudo-Boolean models is further illustrated by the attenuator circuits of Fig. 12. The size r of an attenuator equivalent to the series connection of k attenuators of size rl, r2, *,rk as in Fig. 12a is given by r=MAX {r} (8) corresponding to the resistor equation

18 in out a = (v'i') R. b (v',MIN[i',I j) < —-----, ----- a* b out In a0 = (v",MIN[i",Ij}) b (",i") Fig. 11. A bidirectional attenuator of size Ry = V/Ij. k r. r2 rk r = MAXr r2 r j=13 aS* —** — b a- (a) rk a * —, <i —eb a — o> - b (b) Fig. 12. Equivalent circuits for attenuators connected (a) in series; (b) in parallel.

19 r_= E r (9) j=l The correctness of (8) follows from the fact that a signal (v',' ) transmitted through the chain of resistors is reduced to (v, i ) = (v,, MIN {i, i,. 2, * }) where i =-. If r = MAX {r, }, then i = = MIN {i }, hence (v, i")= (v', i), which is =r r the signal produced by r alone. In a similar fashion it can be shown that the parallel connection of attenuators in Fig. 12b is equivalent to a single attenuator r defined by the equation r = MIN (rj } j==4 This corresponds to the analog resistor equation 1 = 1 r j- r Often when modeling logic circuits, a relatively small number of strength levels or, equivalently, attenuator sizes, provide a good approximation to analog behavior. MOS logic circuits, for instance, can be usefully approximated using three attenuation values specified as follows Ro= 0 R1 k where 0 < k < oo R2= 00 R1 can be used to represent the load or pull-up device normally included in nMOS or pMOS gates. In CMOS circuits that do not contain load devices, R1 may be used to represent the non-zero source-drain resistance of a switched-on transistor. Better approximations can be obtained by introducing additional attenuator/strength values.

20 Suppose, for example, that we must model circuits with up to k resistors rl, r2, * *,rk connected in series as in Fig. 12a, where the resistors may assume m < k different values. It is characteristic of logic circuits that the relevant resistance values are far apart, i.e., R,+1 >> R so that the voltages and currents they produce can be segregated into two groups as required for binary behavior. This separation of the resistance values means, for example, that in series connections like Fig. 12a, the maximum resistance dominates the others. Hence the pseudo-Boolean attenuator combination rule (8) is a good approximation to the analog resistor combination rule (9). It is easily shown that if we have only m attenuator types R = R1, R2, R,Rm defined so that Rj+l > 2kRj, then for any series connection of k or fewer attenuators, Eq. (8) yields the equivalent attenuator size from R that is as close as possible to the analog value defined by Eq. (9). Many variants of the foregoing components are possible. The unidirectional connector of Fig. 9c can be generalized to an amplifier that transforms a'" = (v, i) to b ~ou = (v, MAX{i, Ij }); such a device is the inverse of a unidirectional attenuator. A two-terminal switch can be defined that approximates the behavior of an electronic diode. Conventional logic devices such as gates, decoders, delay elements, ROM's, etc., can also be included in pseudo-Boolean circuits, provided their behavior is defined on an appropriate subset of L, 5. Dynamic Behavior The dynamic behavior of integrated circuits is primarily due to resistive-capacitive effects. It is therefore extremely useful to be able to include in pseudo-Boolean circuits a digital charge-storage element corresponding to an analog capacitor. Such a device,

21 termed a well, has been defined in 12]; similar devices are implicit in the stored-charge signal state found in some simulators [3,4]. Just as in Sec. 3 we quantized resistance into n+1 discrete values R = (R, R, l,Rn), we now quantize capacitance into p+1 discrete values C = (Co, C1, *,Cp) where C+1 > C,. These capacitance values represent the p+1 distinct well sizes that are recognized. A well Ci stores a maximum charge Qi defined by the usual capacitor equation Qi = C, V Thus charge is also quantized into p+l discrete values. It is convenient to make Co = Qo = 0 and C, = Qp = oo corresponding to the capacitance of an open circuit and a conductor (short circuit), respectively. A well Ci charges and discharges in a manner similar to a capacitor. The state of C, can be measured by the instantaneous voltage level across it, and is confined to the value set L1 = {0, 1, U, Z}. The charging and discharging process involves several discrete steps as indicated in Fig. 13, with the duration of these steps determined by the well size Cj and the size R, of the attenuator through which charging or discharging occurs. These step sizes may be chosen to approximate the exponential charging and discharging behavior of an analog capacitor, which is indicated by broken lines in Fig. 13. Thus during charging (Fig. 13a), the voltage v aeross the well Cj is initially 0. At time ti it changes to U as Cj enters a partially charged condition. Finally, at time t2, C, is fully charged and v = 1. A partially or fully charged well acts as a dynamic voltage source generating a time-varying output signal of the form (v(t), i(t)). To distinguish this from a static sig

22 R.' to 1 Voltage v I —-- C2Ef -- T- 1- v = V(1'- e-t/(RiCj)) l O 1V. 2 Tm e Well S V volts v C T/ I t0 t1 t2 Time t (a) ttO < Voltage v 1 \ v = Ve-t/(RiCj) R. v C. 0 I Nt~ — to tt t2 Time t (b) Fig. 13. Behavior of a well: (a) charging; (b) discharging. a ain I " out C. -j J Fig. 14. Signals associated with a well.

23 nal (v, i), we employ the notation <v(t), i(t)> for dynamic signals produced by wells. The value of the signal generated by well Cj at any time can be specified by <v, Cj > or < v, Q, > where v E (0, 1, U, Z}. Note that v = U only when Cj is partially charged, and v = Z only when one or both terminals of C, are disconnected, so that it is incapable of charging or discharging. Because wells behave like voltage sources, the problem of creating new undefined voltage values discussed in Sec. 2 occurs if capacitors can be interconnected in arbitrary fashion. For instance, k fully-charged wells connected in series produce an effective voltage of kV. As in Sec. 2, we eliminate this possibility by requiring all wells and the static voltage source to share a common terminal, namely the circuit ground. Note that it is not necessary to restrict the number of wells appearing in a pseudo-Boolean circuit; their sizes are restricted to the set C. With these assumptions, every well Cj E C in a pseudo-Boolean circuit has the general behavior shown in Fig. 14. The grounded terminal b has the strongest static 0 signal, namely (0, 0), applied to it, and so is permanently in the (0, 0) state. The remaining terminal outputs a dynamic signal a ut which represents the state of the well. The externally applied input signal a n may be static or dynamic, or may result from a combination of static and dynamic signals. First, consider the behavior of well Cj in Figs. 13 and 14 when a"' is static. At time to let an =- (dj, i) and aut = <d2, j> where d, d2 E {O, 1, U}. After some time r (i, j), whose value depends on the strengths of ai" and a~", i.e., on the associated Ri C, time constant, S(a) and a"ut become (d1, i) and <d1, i>, respectively. Thus the static a'" overrides the dynamic a ot after a delay r (i, i). We can therefore specify the sequential behavior of S(a) = a as follows:

24 a(t + (i, j))= #((di, i), <di, i>) (10) In this way discrete delays are introduced into pseudo-Boolean circuits as a consequence of the interaction between attenuators and wells, i.e., between resistance and capacitance. If a'" = (Z, n) in Fig. 14, then a ot and S(a) remain indefinitely at <d2 j>. Now suppose that a" = <dl, i>, which corresponds to connecting the a-terminal of a second well C, to C,. We must model the resultant charging and discharging behavior while limiting the well states to the prescribed set of dynamic values. Just as large attenuators override the effects of smaller ones, we allow the larger well to override the smaller one. Hence if Cj > C,, and a' = <dl, i> is applied by C, to Cj (see Fig. 14), then S(a) and a'" both eventually change to a t = <d2, j>. For example, if ai = <1, i> and a~" = <0,j>, then C, effectively discharges C, without itself becoming charged. Similarly if a~t = <1, j>, C, charges Cj, with the size difference between C, and Cj ensuring that Cj remains fully charged. In the case where C, = Cj, charge sharing occurs between C, and C, when their states differ. Thus if a = <0, i> = <0, j> and a~ut = <1,j>, then a'" and a~ut both become <U, i>. The foregoing analysis implies that with p+l dynamic strength levels, i.e., p+l well sizes, there are 3p+l distinct dynamic logic values of the form <v, q> which form a pseudo-Boolean algebra Li isomorphic to Lp, the algebra of static values (v, i) with p+1 attenuator sizes. It is readily seen that when p=l, Li and L1 coincide, so that there is no distinction between static and dynamic values. The zero elements <Z, p> and (Z, n) of Lp and L., respectively are also identical, since each represents the signal produced by an open circuit, i.e., the high-impedance state. If n+1 attenuator sizes and p+1 well sizes are permitted in a pseudo-Boolean circuit, then the corresponding algebras L,, and

25 (U,o) (0,0) (1,0) (0,1) t f (1,1) Static (U,2) values (on —1) ~MU, <Un> <0,n n> <i,n> <U,n+i.> <0,n+i>^ <l,n+l> Dynamic \ <U,n+2> values 0 <<U,n+p-2> <0,n+p-2> ) <l,n+p-2> <Z,n+p-l> Fig. 15. The lattice structure of the pseudo-Boolean algebra Ln,

26 Lp are merged to form a single [3(n+p-l)-ll-member pseudo-Boolean algebra whose structure is illustrated in Fig. 15. This algebra, denoted L,,, is isomorphic to Ln+p-l and may be formed by concatenating the dynamic algebra Lp_1 to the static algebra L,. This concatenation reflects the fact that any dynamic signal can eventually be overridden by any static signal. Using the dagger symbol of [11] for lattice concatenation we can write L, p = L, t Lp-1 for n > 1 and p > 1; when p = 1, L, p reduces to L1 = L. In general, L,, is used to analyze the behavior of pseudo-Boolean circuits in which there are up to n-l finite nonzero attenuator sizes and p-1 finite nonzero well sizes. In Fig. 15 the strength levels of Lp_1 are numbered n, n+1,..., n+p-1, to emphasize that they are weaker than the strength values appearing in L,. All interactions between signals applied to any connector of a pseudo-Boolean circuit N are determined by the least upper bound operator # for L,,. When both static and dynamic signals are involved, signal transitions are delayed by a appropriate amount as in Eq. (10). For example, suppose that a connector a has a stable dynamic signal <1, i> applied to it at time t, so that the connector state a(t) is <1, i>. If the static signal (0, j) is now applied to a, it remains in state <1, i> for a period rF and then changes to (0, j) thus: a(t)= <1, i> a(t+rF) #(<1, i>, (0, ) ) (0, j) TF can be viewed as the signal (voltage) fall time, and is a function of the signal strength levels i and j. Similarly, a rise time TR, not necessarily equal to TF, can be associated

27 with the interaction of <0, i> and (1, j). The time delays derived from the interaction of static and dynamic signals in this manner are more accurate and more natural than those obtained using unidirectional lumped delay elements of the kind employed by most logic simulators. Of course, lumped delays can also be included in pseudo-Boolean circuits, if desired. 8. Applications Pseudo-Boolean circuits provide a unified framework for the analysis of many types of logic circuits [2]. Their practical significance lies in their ability to model the behavior and, to a lesser extent, the layout structure of MOS circuits of the kind used in VLSI design. In particular, they constitute the theoretical basis for switch-level simulation programs, which have become widely used since the early 1980's for VLSI design verification. These simulators can perform more detailed behavioral analysis than traditional gate-level simulators, using component and signal types that better reflect the physical properties of real circuits. By varying the number of strength levels recognized, i.e., the number of distinct resistance and capacitance sizes, useful tradeoffs between simulation accuracy and computational complexity can be made. Figure 16 shows several pseudo-Boolean approximations to an MOS switching transistor which is the basic building block of VLSI circuits. The simplest model is the ideal switch of Fig. 16b, whose behavior is defined in (6) and Fig. 3. The input line c corresponding to the transistor's gate terminal, controls the path between the switch's bidirectional a and b terminals. The behavior of circuits such as that of Fig. 4, which are composed solely of ideal switches, can be defined using the four-valued signal set L1. Figure l1c shows a better transistor approximation in which the source-drain resistance

28 Drain a a Gate c c S Source b b (a) (b) a ~c! I.2"I' R1 I A (0 0) 0I! [ R I C I C ~ s I b i (0o0o) b r -- -A__ - A l (o) (0,0) l _ _ — -- _ (e) Fig. 16. (a) An nMOS switching transistor; (b-e) various pseudo-Boolean models of this transistor.

29 in the on-state is represented by the attenuator R1. In this case L2 is the appropriate pseudo-Boolean algebra for defining transistor behavior. Note that we can replace the circuit of Fig. 16b by a primitive switch that has the following behavior, where a "n = (va, i ) and b' = (vb, ib ); compare (6), C i,a6 b0ut Switch State (1, i,) (vb, MIN {ib, II}) (v,, MIN ia, I,}) On (0, i,) (Z, n) (Z, n) Off Figure lOd adds a well C1 to the preceding model to represent the gate-substrate capacitance of the transistor; this circuit may be analyzed using Lz2 = L2 t L1. Note that if c = (Z, n), i.e., the transistor's gate terminal is open-circuited, the well can hold the switch S in its previous on or off state indefinitely. Much more complex transistor models are possible, but require increasingly larger pseudo-Boolean algebras to describe them. The circuit of Figure 16e, for instance, includes two additional attenuator sizes R2 and Rs, representing the off (source-drain) resistance and input (gate-source) resistance of the transistor, respectively. The algebra L4 t LI having 16 values would be necessary to cover this case. An inverter stage from a two-phase nMOS dynamic shift-register [12] is depicted in Fig. 17a. Q1, Q2 and Q4 are switching transistors, while Qs is a clocked load transistor. C1 denotes the gate-substrate capacitance of Q2, which plays a key role as a temporary data storage device in dynamic circuit operation. An equivalent pseudo-Boolean circuit for the inverter stage appears in Fig. 17b. Here the switch-attenuator transistor model of Fig. 16c represents Q, Q s and Q4, while the switch-attenuator-well model of Fig. 16d represents Q2. As observed earlier, these transistor models, which are enclosed in broken

30 $1 vDD V2 a —, ca. —-— ^: —---- d Qi Q4 b Q2 C1' —F1 1cT - 13 I/ (1,0) I _ J in 7 rl c hi t -in ari ^ X' I e a Ahr —r — c<-;___! 7 ^rf —. (' * I ^r I ~ ^ *out in 4 rL 4 - out il.' out,. c2 Ln 4Ld 4 louttou 1 1 ^f ^ ^ef0 - < —. - L-" b- b I 1 Ed I out I (0,0) I (o,o) (b) Fig. 17. (a) Inverter stage of a dynamic shift register; (b) pseudo-Boolean model.

31 lines in Fig. 17b, can be defined as primitive elements, thus preserving a one-to-one correspondence between the structure of the pseudo-Boolean circuit model and that of the electrical circuit (Fig. 17a). The attenuators rl, r2 and r4 can all be assigned a relatively small resistance value R1, while attenuator r3 representing a load element is assigned a much larger value R2. Thus the circuit is characterized by the parameters R = {Re = 0, R1, R2, Rs = oo} and C = {C, = 0, C0, C2 = oo), and the 13-member pseudo-Boolean algebra L3,2 = L3 t L. A weaker, but nevertheless useful, approximation to this circuit can be obtained by setting r = r2= r= 0, in which case the ten values of L2, 2 = L2 t L suffice to describe its behavior. We now briefly illustrate the analysis of pseudo-Boolean circuits using Fig. 17b as an example. We are primarily interested in determining the states of the connectors a, b, c, and d with respect to L,2; the other connectors have either constant values (VDD and ground) or externally controlled clock signals (q1 and 42) applied to them. Suppose that the circuit is in the initial state (l^, 0, a, b, c, d)= ((, 0), (0, 0), (1, 0), <0, 3>, <Z, 4>, <Z, 4>) whose strength levels are defined as in Fig. 15. Assume that well C1 is discharged, and all clock signals and switches are initially in the off state. Node b is held at the weakest 0 value <0, 3> by the well, while c and d are disconnected from all signal sources and thus assume the high-impedance state <Z, 4>. Now suppose that 01 changes from (0, 0) to (1, 0). This turns switch S1 on, thereby applying a' = (1, 0) to attenuator rl. This in turn causes b " to change from <Z, 4> to (1, 1), and the well C1 begins to charge. After some time r(R1, C1), b reaches the 1 level causing switch S2 to turn on, and immediately changing c from <Z, 4> to (0, 1).

32 Since S4 is still switched off, d remains unchanged. If i0 now returns to (0, 0), Cl holds S2 in the on state, and the signal of interest have the following states. (O1, 02 at, b, c, d) = ((, 0), (0, 0), (1, 0), <1, 3>, (0, 1), <Z, 4>) Next suppose that 02 becomes (1, 0). This causes both S3 and S4 to switch on. ci changes from <Z, 4> to (1, 2), and c assumes the state #((1, 2), (0, 1)) = (0, 1). This state is applied via c Ut and r4 to d causing dOut to become (0, 1). Thus the circuit is now in the state (b1,, 2, a, b, c, d) = ((0 0), (1, 0), (1, 0), <1, 3>, (0, 1), (0, 1)) Most existing switch-level simulators implicitly use subsets of L,, p corresponding to very small values of n and p. The 10-valued pseudo-Boolean algebra L2 = L2 t L1 is explicitly used by the fault simulator CSASIM [5]. CSASIM recognizes one finite nonzero attenuator size R1 and one finite non-zero well size C1. In nMOS or pMOS circuit analysis, for example, R1 is typically equated to the resistance of the load transistor of a logic gate; C1 is equated to the gate-substrate capacitance of a switching transistor. Essentially the same pseudo-Boolean algebra is used in LOGIS [3], one of the first commercial simulators with comprehensive switch-level simulation capabilities. LOGIS does not explicitly identify the zero element <Z, 3>, corresponding to the high-impedance state Z, as a logic value. Hence, it is described as a 9-valued simulator, whose values consist of all combinations of the three voltage levels ({0, 1, U} and the three strength levels {0, 1, 2). In LOGIS an attenuator is termed a "resistive gate." LOGIS has no explicit digital storage device corresponding to a well; instead a circuit node P is allowed to be in a "trapped charge" state, which is tantamount to connecting a well of fixed size C1 between P and ground. The following table compares the ways in which the logic values

33 of L.22 are interpreted by CSASIM and LOGIS. Value CSASIM LOGIS (0,0) Strong static 0 Forcing low (unlimited charge sink) (1,0) Strong static 1 Forcing high (unlimited charge source) (U,0) Strong static U Forcing indeterminate (short-circuit) (0,1) Weak static 0 Non-forcing low (restricted charge sink) (1,1) Weak static 1 Non-forcing high (restricted charge source) (U,1) Weak static U Non-forcing indeterminate (unknown charge) <0,2> Dynamic 0 High-Z low (minimum trapped charge) <1,2> Dynamic 1 High-Z low (maximum trapped charge) <U,2> Dynamic U High-Z indeterminate (unknown trapped charge) <Z,3> High-impedance state A second version of the CSASIM simulator in which L,, p is the logic value set, and n and p are treated as user-selectable parameters, is currently under development at the University of Michigan. 7. Discussion A new class of logic circuits that accurately represent the structure and behavior of many important types of digital circuits has been presented. It has been shown that the mathematical structure underlying these circuits is a type of pseudo-Boolean algebra. The circuits in question can therefore be seen as a generalization of gate-type or contact-type logic circuits based on Boolean algebra. At the same time, pseudo-Boolean circuits are discrete approximations to electrical circuits, where parameters like voltage, current, charge, resistance, and capacitance are confined to finite closed sets. We have demonstrated that basic electrical properties of signals such as bidirectionality, Kirchoffs Current Law, and the Superposition Principle, can be rigorously mapped from

34 the electrical to the logical plane. Thus it can be concluded that pseudo-Boolean circuits occupy a well-defined complexity level (the switch level) lying between the classical electrical and logic circuit levels. A variety of approaches to the analysis of switch-level circuits have been proposed, including graph-theoretical methods [4,71 and characteristic functions [6,131. In this paper an alternative technique based on the superposition of bidirectional signals has been described. It has been implemented explicitly in the simulation program CSASIM [5], and appears to be especially useful for simulating both the normal and the faulty behavior of complex MOS circuits. Acknowledgement The contributions of Masato Kawai to the development of the CSASIM simulator are gratefully acknowledged.

35 References [1] C. Mead and L. Conway: Introduction to VLSI Systems, Reading, Mass., AddisonWesley, 1980. [2] J.P. Hayes: "A unified switching theory with applications to VLSI design." Proc. IEEE, vol. 70, pp. 1140-1151, Oct. 1982. [3] Information Systems Design, Inc.: Logis User's Manual, Santa Clara, circa 1978. [4] R.E. Bryant: "MOSSIM: a switch-level simulator for MOS LSI," Proc. 18th Design Automation Conf., Nashville, pp. 786-790, June 1981. [5] M. Kawai and J.P. Hayes: "An experimental MOS fault simulation program CSASIM," Proc. 21st Design Automation Conf., Albuquerque, pp. 2-9, June 1984. [6] J.P. Hayes: "A logic design theory for VLSI," Proc. Second Caltech Conf. on VLSI, Pasadena, pp. 455-476, Jan. 1981. [7] R.E. Bryant: "A switch-level model and simulator for MOS digital systems," IEEE Trans. Computers, vol. C-33, pp. 160-177, Feb. 1984. [8] H. Rasiowa and R. Sikorski: The Mathematics of Metamathematics, Polska Akad. Nauk Monografie Math., vol. 41, Warsaw, 1963. [9] J.P. Hayes: "Fault modeling for digital MOS integrated circuits," IEEE Trans. Computer-Aided Design, vol. CAD-3, pp. 200-207, July 1984. [10] G.H. Hostetter: Engineering Network Analysis, New York, Harper and Row, 1984. [11] R. Balbes and P. Dwinger: Distributive Lattices, Columbia, Mo., Univ. of Missouri Press, 1974. [12] W.N. Carr and J.P. Mize: MOS/LSI Design and Application, New York, McGrawHill, 1972. [13] E. Cerny and J. Gecsei: "Functional description of connector-attenuator-switch networks," Universite de Montreal, Dept. d'Informatique et de Recherche Operationelle, Pub. No. 479, June 1983.