Intractability in Linear Switch-Level Simulation

Abstract

The linear switch-level model represents a MOS transistor as a voltage-controlled linear resistor and a storage node as a grounded, linear capacitor. For logic simulation, the linear switch-level model offers an attractive trade-off between resolution/accuracy and computational complexity over gate-level and circuit-level models. However, analysis of MOS networks using the linear switch-level model becomes increasingly difficult in the presence of unknown values, such as logic X, and heuristic methods are often employed. This paper shows the complexity of computing maximum and minimum steady-state voltages of a general MOS network using the linear switch-level model in the presence of unknown values to be NP-complete. These results partially justify the use of heuristic methods when unknown values are present. © 1993 IEEE