Logical Design of VLSI Circuit with Extension of Uncertainty (or monotonic functional completeness of Kleene ternary logic)

Sun, Yong

Abstract: We consider that traditional 2-valued boolean algebra is not sufficient in representing VLSI circuit (say at gate-level), although it seems to be the case for combinational circuit. Instead of introducing the common technique of register-and-transfers to represent sequential circuit, we seek an alternative which is to define an invertor, a nor-gate and a nand-gate according to actual circuit. We identify all uncertain voltages as one, which is denoted as \bot (bottom or uncertain voltages). Other voltages with certainty are, as usual, denoted definitely as 0 (low voltage or ground) and 1 (high voltage or power). The resulting logic turns out to coincide with Kleene 3-valued logic with generalized fixed-point operators.

Unfortunately, Kleene 3-valued logic is functionally incomplete. This means that not every gate can be constructed from invertors, nor-gates and nand-gates if gates are viewed to be equivalent to functions from their inputs to outputs. However, by applying cpo domain theory [Plotkin 85] to our derived 3-valued logic system, we discover that this system is functionally monotonic complete. This implies that all constructible gates share the following property: whenever the certainty of input voltages of a gate increases, so does the certainty of output voltages of the gate. As by-products, we also obtain two main facts about logic design of VLSI circuit.

(a) For any gate, if its input voltages are uncertain, then we cannot expect to be certain about its output voltages; and

(b) even if we can always supply voltages to inputs of every gate with great certainty, there exists a constructible gate which output voltages are always with uncertainty.

So far, our results are mainly semantical ones. We are very interested in pursuing this research further but from a different point of view, i.e. from the point of view of syntactical derivability, since such research would enable us to derive mathematical secure circuit with more reality to actual circuit design. Recent Avron's work can be regarded as a few steps towards this direction [Avron 87, Avron 88]. We should also mention that Mukaidono has independently obtained the same result in [Mukaidono 86], although his approach is not as coherent as ours.


Previous | Index | Next