Gate Circuits with Feedback in Finite Multivalued Algebras of Transients
Janusz Brzozowski and Yuli Ye
Multivalued simulation of gate circuits is an efficient method of detecting hazards and oscillations that may occur in the presence of gate and wire delays. Ternary simulation, introduced by Eichelberger in 1965, consists of two algorithms, called A and B, and its results are well understood. Ternary simulation has been generalized by Brzozowski and Ésik in 2003 to an infinite algebra C and finite algebras Ck, k ≥ 2, where C2 is ternary algebra. Simulation in C has been studied extensively for feedback-free circuits, for which Algorithm A always terminates and Algorithm B is unnecessary. We study the simulation of gate circuits with feedback in finite algebras Ck, in which Algorithms A and B always terminate. The Boolean functions of the gates are restricted to a set G, where G = H∪ ˜H, H = {OR, XOR}, and ˜H is the set of functions obtained by complementing any number of inputs and/or the output of functions from H. This set G includes all the nontrivial 1- and 2-variable functions and multi-input AND, OR, NAND, NOR, XOR and XNOR functions. We introduce a simple graphtheoretic model of a circuit. We derive new properties of extensions of Boolean functions to Algebra C. We prove that Algorithm B in Algebra Ck, for k > 2, provides no more information than Algorithm B in ternary algebra. Thus, for any gate in any circuit, the final result of Algorithm B is always one of the binary values, 0 or 1, which are considered “certain”, or the third “uncertain” value; the remaining values of Ck never appear. This permits us to replace Algorithm B in Ck by the same algorithm in ternary algebra, and to reduce the simulation time.
Keywords: Algebra, circuit, dynamic, gate, hazard, multivalued, network, oscillation, simulation, static, ternary, transient.