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
      Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE