QBF-based boolean function bi-decomposition
conference contribution
posted on 2013-02-15, 09:20 authored by Huan Chen, Mikolas Janota, Joao Marques-SilvaBoolean function bi-decomposition is ubiquitous in
logic synthesis. It entails the decomposition of a Boolean function
using two-input simple logic gates. Existing solutions for bidecomposition
are often based on BDDs and, more recently,
on Boolean Satisfiability. In addition, the partition of the input
set of variables is either assumed, or heuristic solutions are
considered for finding good partitions. In contrast to earlier
work, this paper proposes the use of Quantified Boolean Formulas
(QBF) for computing bi-decompositions. These bi-decompositions
are optimal in terms of the achieved quality of the input set
of variables. Experimental results, obtained on representative
benchmarks, demonstrate clear improvements in the quality of
computed decompositions, but also the practical feasibility of
QBF-based bi-decomposition.
History
Publication
Design, Automation & Test in Europe Conference & Exhibition;pp. 816-819Publisher
IEEE Computer SocietyNote
peer-reviewedOther Funding information
SFIRights
“© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.Language
EnglishUsage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC