| Presentation | 2005-12-02 Exact Minimum Logic Factoring via Quantified Boolean Satisfiability Hiroaki YOSHIDA, Makoto IKEDA, Kunihiro ASADA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper presents an exact algorithm 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 tree, which implicitly enumerates binary trees. Using this graph structure, the factoring problem is compactly transformed into a QBF and hence the size of solvable problems is extended. Experimental results show that the proposed algorithm successfully finds the exact minimum solutions to the problems with up to 12 literals. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Quantified Boolean formula / Boolean satisfiability / logic factoring / binary tree |
| Paper # | VLD2005-83,ICD2005-178,DC2005-60 |
| Date of Issue |
| Conference Information | |
| Committee | ICD |
|---|---|
| Conference Date | 2005/11/25(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Integrated Circuits and Devices (ICD) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Exact Minimum Logic Factoring via Quantified Boolean Satisfiability |
| Sub Title (in English) | |
| Keyword(1) | Quantified Boolean formula |
| Keyword(2) | Boolean satisfiability |
| Keyword(3) | logic factoring |
| Keyword(4) | binary tree |
| 1st Author's Name | Hiroaki YOSHIDA |
| 1st Author's Affiliation | Department of Electronic Engineering, University of Tokyo() |
| 2nd Author's Name | Makoto IKEDA |
| 2nd Author's Affiliation | VLSI Design and Education Center(VDEC), University of Tokyo |
| 3rd Author's Name | Kunihiro ASADA |
| 3rd Author's Affiliation | VLSI Design and Education Center(VDEC), University of Tokyo |
| Date | 2005-12-02 |
| Paper # | VLD2005-83,ICD2005-178,DC2005-60 |
| Volume (vol) | vol.105 |
| Number (no) | 446 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |