Exact Minimum Factoring of Incompletely Specified Logic Functions via Quantified Boolean Satisfiability

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• Information and Media Technologies 編集運営会議の論文

著者

• YOSHIDA Hiroaki

  VLSI Design and Education Center, The University of Tokyo

関連論文

• Interconnect-Aware Pipeline Synthesis for Array-Based Architectures
• Exact Minimum Factoring of Incompletely Specified Logic Functions via Quantified Boolean Satisfiability

スポンサーリンク