AND/OR Reasoning Graphs for Determining Prime Implicants in Multi-Level Combinational Networks*
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E80-A No.12 pp.2581-2588
- Publication Date
- 1997/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Category
- VLSI Design Technology and CAD
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Dominik STOFFEL, Wolfgang KUNZ, Stefan GERBER, "AND/OR Reasoning Graphs for Determining Prime Implicants in Multi-Level Combinational Networks*" in IEICE TRANSACTIONS on Fundamentals,
vol. E80-A, no. 12, pp. 2581-2588, December 1997, doi: .
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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e80-a_12_2581/_p
Copy
@ARTICLE{e80-a_12_2581,
author={Dominik STOFFEL, Wolfgang KUNZ, Stefan GERBER, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={AND/OR Reasoning Graphs for Determining Prime Implicants in Multi-Level Combinational Networks*},
year={1997},
volume={E80-A},
number={12},
pages={2581-2588},
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={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - AND/OR Reasoning Graphs for Determining Prime Implicants in Multi-Level Combinational Networks*
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2581
EP - 2588
AU - Dominik STOFFEL
AU - Wolfgang KUNZ
AU - Stefan GERBER
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E80-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 1997
AB - 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.
ER -
English
