[go: up one dir, main page]

Information and Media Technologies
Online ISSN : 1881-0896
ISSN-L : 1881-0896
Hardware and Devices
Exact Minimum Factoring of Incompletely Specified Logic Functions via Quantified Boolean Satisfiability
Hiroaki YoshidaMasahiro Fujita
Author information
JOURNAL FREE ACCESS

2011 Volume 6 Issue 2 Pages 286-295

Details
Abstract

This paper presents an exact method which finds the minimum factored form of an incompletely specified Boolean function. The problem is formulated as a Quantified Boolean Formula (QBF) and is solved by general-purpose QBF solver. We also propose a novel graph structure, called an X-B (eXchanger Binary) tree, which compactly and implicitly enumerates binary trees. Leveraged by this graph structure, the factoring problem is transformed into a QBF. Using three sets of benchmark functions: artificially-created, randomly-generated and ISCAS 85 benchmark functions, we empirically demonstrate the quality of the solutions and the runtime complexity of the proposed method.

Content from these authors
© 2011 Information Processing Society of Japan
Previous article Next article
feedback
Top