DocumentCode :
915130
Title :
Algorithmic Aspects of Symbolic Switch Network Analysis
Author :
Bryant, Randal E.
Author_Institution :
Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Volume :
6
Issue :
4
fYear :
1987
fDate :
7/1/1987 12:00:00 AM
Firstpage :
618
Lastpage :
633
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 :
Boolean manipulation; Gaussian elimination; MOS circuit analysis; series-parallel graphs; switch networks; symbolic analysis; Algorithm design and analysis; Control systems; Data structures; Digital circuits; Digital relays; Equations; Logic; MOS devices; Switches; Switching circuits;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.1987.1270309
Filename :
1270309
Link To Document :
بازگشت