Algorithmic Aspects of Symbolic Switch Network Analysis
- 1 July 1987
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 6 (4) , 618-633
- https://doi.org/10.1109/tcad.1987.1270309
Abstract
A network of switches controlled by Boolean variables can be represented as a system of Boolean equations. The solution of this system gives a symbolic description of the conducting paths in the network. Gaussian elimination provides an efficient technique for solving sparse systems of Boolean equations. For the class of networks that arise when analyzing digital metal-oxide semiconductor (MOS) circuits, a simple pivot selection rule guarantees that most s-switch networks encountered in practice can be solved with O(s) operations. When represented by a directed acyclic graph, the set of Boolean formulas generated by the analysis has total size bounded by the number of operations required by the Gaussian elimination. This paper presents the mathematical basis for systems of Boolean equations, their solution by Gaussian elimination, and data structures and algorithms for representing and manipulating Boolean formulas.Keywords
This publication has 18 references indexed in Scilit:
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Improving the Performance of a Switch-Level Simulator Targeted for a Logic Simulation MachineIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1986
- Digital CMOS Circuit DesignPublished by Springer Nature ,1986
- Simulation of MOS Circuits by Decision DiagramsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- Efficient parallel solution of linear systemsPublished by Association for Computing Machinery (ACM) ,1985
- A Unified Approach to Path ProblemsJournal of the ACM, 1981
- Algebraic structures for transitive closureTheoretical Computer Science, 1977
- Diagnosis & Reliable Design of Digital SystemsPublished by Springer Nature ,1976
- An Algebra for Network Routing ProblemsIMA Journal of Applied Mathematics, 1971
- A Machine-Oriented Logic Based on the Resolution PrincipleJournal of the ACM, 1965