Generalized Ternary Simulation of Sequential Circuits

Asynchrouous gate circuits have been traditioually analyzed using binary models which are conceptually simple and natural, but are exponential in the number of state variables. A commonly usec binary method is the General Mutiple-Winner (GMW) model, which can be applied to any circuit started in any state. In contrast to this the ternary analysis method called ternary simulation is polynomial in the number of state variables, but applies only to a circuit started in a stable state. This method has been in use since 1965. The equivalence of ternary simulation to the GMW analysis was proved in 1987, for the case of a stable starting state. In this paper we present a generalized ternary simulation algorithm applicable to any state, and we prove that the new algorithm is equivalent to GMW analysis. Th new algorithm is used to prove that certain behaviors are not realizable.