AND/OR reasoning graphs for determining prime implicants in multi-level combinational networks
- 22 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper presents a technique to determine prime implicants in multi-level combinational networks. The method is based on a graph representation of Boolean functions called AND/OR reasoning graphs. This representation follows from a search strategy to solve the satisfiability problem that is radically different from conventional search for this purpose (such as exhaustive simulation, backtracking, BDDs). The paper shows how to build AND/OR reasoning graphs for arbitrary combinational circuits and proves basic theoretical properties of the graphs. It will be demonstrated that AND/OR reasoning graphs allow us to naturally extend basic notions of two-level switching circuit theory to multi-level circuits. In particular, the notions of prime implicants and permissible prime implicants are defined for multi-level circuits and it is proved that AND/OR reasoning graphs represent all these implicants. Experimental results are shown for PLA factorization.Keywords
This publication has 12 references indexed in Scilit:
- Verification of large synthesized designsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Introduction of permissible bridges with application to logic optimization after technology mappingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Advanced Verification Techniques Based on LearningProceedings of the 39th conference on Design automation - DAC '02, 1995
- Recursive learning: a new implication technique for efficient solutions to CAD problems-test, verification, and optimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1994
- Boolean ReasoningPublished by Springer Nature ,1990
- The transduction method-design of logic networks based on permissible functionsIEEE Transactions on Computers, 1989
- MIS: A Multiple-Level Logic Optimization SystemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Graph-Based Algorithms for Boolean Function ManipulationIEEE Transactions on Computers, 1986
- Logic Minimization Algorithms for VLSI SynthesisPublished by Springer Nature ,1984
- Diagnosis of Automata Failures: A Calculus and a MethodIBM Journal of Research and Development, 1966