Algorithmic Aspects of MOS VLSI Switch-Level Simulation with Race Detection
- 1 May 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (5) , 462-475
- https://doi.org/10.1109/TC.1986.1676789
Abstract
We present algorithms and time complexity results for MOS switch-level simulation with particular reference to race detection. Under the switching model used in classical (Boolean) switching theory, we derive a linear-time race detection algorithm for switch-level circuits that have no feedback within a clock phase, and have unit fan-out. We show that the problem becomes NP-complete if fan-out of two or more is allowed. We Also relate this result to others that have recently been reported, using a different switching model.Keywords
This publication has 4 references indexed in Scilit:
- A Switch-Level Model and Simulator for MOS Digital SystemsIEEE Transactions on Computers, 1984
- The Second Generation MOTIS Mixed-Mode SimulatorPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1984
- An Improved Switch-Level Simulator for MOS CircuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On a Ternary Model of Gate NetworksIEEE Transactions on Computers, 1979