Accession Number : ADA188617
Title : Two Papers on a Symbolic Analyzer for MOS (Metal-Oxide Semiconductors) Circuits.
Descriptive Note : Interim rept.,
Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s) : Bryant, R E
PDF Url : ADA188617
Report Date : Dec 1987
Pagination or Media Count : 73
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 a 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, data structures and algorithms for representing and manipulating Boolean formulas.
Descriptors : *ALGORITHMS, *BOOLEAN ALGEBRA, *METAL OXIDE SEMICONDUCTORS, *NETWORKS, *SYMBOLS, ANALYZERS, DIGITAL SYSTEMS, EFFICIENCY, EQUATIONS, FORMULAS(MATHEMATICS), VARIABLES
Subject Categories : Theoretical Mathematics
Solid State Physics
Distribution Statement : APPROVED FOR PUBLIC RELEASE