Presentation | 1997/10/29 Efficient Manipulation on Implicit Representation of Binary Decision Diagrams Hitoshi Yamauchi, Hiromitsu Takahashi, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | Binary Decision Diagrams (BDD) is used on computer aided design of VLSI, because of that's goodness of memory spacing on computers for representing boolean functions. Recently, though, big size boolean functions such that are not able to be represented by BDD appear on VLSI design. We presented an implicit representation of BDDs (iBDD) which is a new representation method by representing characteristics of BDD in meaning of graph implicitly, and algorithms manipulating this. This method is effective in representation size, but requires huge manipulation time. In this paper, a new faster manipulation method is presented. The negative edge technique and recursive applying method used in BDD are introduced. Experimental results on n bit adder functions says this method reduces manipulation time from O (n^<2.14>) to O (n^<1.01>). |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | binary decision diagrams / implicit representation / boolean function / computer aided design |
Paper # | VLD97-88 |
Date of Issue |
Conference Information | |
Committee | VLD |
---|---|
Conference Date | 1997/10/29(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 | VLSI Design Technologies (VLD) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | Efficient Manipulation on Implicit Representation of Binary Decision Diagrams |
Sub Title (in English) | |
Keyword(1) | binary decision diagrams |
Keyword(2) | implicit representation |
Keyword(3) | boolean function |
Keyword(4) | computer aided design |
1st Author's Name | Hitoshi Yamauchi |
1st Author's Affiliation | Department of Communication Engineering, Faculty of Computer Science and System Engineering, Okayama Prefectural University() |
2nd Author's Name | Hiromitsu Takahashi |
2nd Author's Affiliation | Department of Communication Engineering, Faculty of Computer Science and System Engineering, Okayama Prefectural University |
Date | 1997/10/29 |
Paper # | VLD97-88 |
Volume (vol) | vol.97 |
Number (no) | 344 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |