Extracting Logic Circuit Structure from Conjunctive Normal Form Descriptions
Authors:
- 1 January 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 48 (10639667) , 37-42
Abstract
Boolean satisfiability is seeing increasing use as a decision procedure in electronic design automation (EDA) and other domains. Most applications encode their domain specific constraints in conjunctive normal form (CNF), which is accepted as input by most efficient contemporary SAT solvers (Moskewicz et al., 2001). However, such translation may have information loss. For example, when a circuit is encoded into CNF, structural information such as gate orientation, logic paths, signal observability, etc. is lost. However, recent research (Li, 2000) shows that a substantial amount of the lost information can be restored in circuit form. This paper presents an efficient algorithm (CNF2CKT) for extracting circuit information from CNF instances. CNF2CKT is optimal in the sense that it extracts a maximum acyclic combinational circuit from any given CNF using the logic gates pre-specified in a library. The extracted circuit structure is valuable in various ways, particularly when the CNF is not encoded from the circuit, or the circuit description is not readily available. As an example, we show that the extracted circuit structure can be used to derive circuit observability don't cares (Bartlett et al., 1988) for speeding up CNF-SAT (Fu et al., 2005)Keywords
This publication has 10 references indexed in Scilit:
- Managing don't cares in Boolean satisfiability2004
- BerkMin: A fast and robust SAT-solver2003
- Applying SAT Methods in Unbounded Symbolic Model Checking2002
- Pruning Techniques for the SAT-Based Bounded Model Checking Problem2001
- Dynamic detection and removal of inactive clauses in SAT with application in image computation2001
- Circuit-based Boolean Reasoning2001
- Complexity Classifications of Boolean Constraint Satisfaction Problems2001
- Automating first-order relational logic2000
- GRASP: a search algorithm for propositional satisfiabilityIEEE Transactions on Computers, 1999
- Multi-level logic minimization using implicit don't caresIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1988