| 講演名 | 2001/11/22 多出力関数のBDDによる表現法とその最適化法 松浦 宗寛, 笹尾 勤, 井口 幸洋, 永山 忍, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本論文では, 多出力関数の新しい表現方法:ECFN(Encoded Characteristic Function for Non-zero outputs)を提案する.ECFNは, n入力m出力の関数を表現するために(n+u)個の2値変数を使う。ここで, u=「1og_2m」である.ECFNを表現するBDD(Binary Decision Diagram)は, SBDD(Shared BDD)より大きくなることはなく, 多くの場合小さくできる.ECFNでは出力の符号化を工夫することによってBDDを縮小できるが, これは変数順序の変更と同様に効果的である.最適な符号化をしたECFNを表現するBDDの節点数が, 2n+2個であり, 最悪の符号化をした節点数が2^ |
| 抄録(英) | This paper shows a new method to represent a multiple-output function: An encoded characteristic function for non-zero outputs (ECFN). The ECFN uses (n+u) binary variables to represent an n-input m-output function, where u=⌈log_2 m⌉. The binary decision diagrams (BDDs) for ECFNs are never greater than corresponding SBDDs, and can be often smaller than SBDDs. The size of a BDD depends on the encoding of the outputs as well as the ordering of the variables. We show an n-input 2^n-output function, where the optimal encoding produces a BDD with 2n+2 nodes, while the worst encoding produces a BDD with 2^ |
| キーワード(和) | 多出力関数 / 符号化問題 / BDD / 特性関数 |
| キーワード(英) | Multiple-output function / encoding problem / BDD / characteristic function |
| 資料番号 | VLD2001-100,ICD2001-145,FTS2001-47 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 2001/11/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多出力関数のBDDによる表現法とその最適化法 |
| サブタイトル（和） | |
| タイトル（英） | Compact Representaions of BDDs for Multiple-Output Functions and Their Optimization |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 多出力関数 / Multiple-output function |
| キーワード(2)（和/英） | 符号化問題 / encoding problem |
| キーワード(3)（和/英） | BDD / BDD |
| キーワード(4)（和/英） | 特性関数 / characteristic function |
| 第 1 著者 氏名（和/英） | 松浦 宗寛 / Munehiro MATSUURA |
| 第 1 著者 所属（和/英） | 九州工業大学情報工学部 Department of Computer Science and Electronics, Kyushu Institute of Technology |
| 第 2 著者 氏名（和/英） | 笹尾 勤 / Tsutomu SASAO |
| 第 2 著者 所属（和/英） | 九州工業大学情報工学部:九州工業大学マイクロ化総合技術センター Department of Computer Science and Electronics, Kyushu Institute of Technology:Center for Microelectronic Systems, Kyushu Institute of Technology |
| 第 3 著者 氏名（和/英） | 井口 幸洋 / Yukihiro IGUCHI |
| 第 3 著者 所属（和/英） | 明治大学理工学部 Department of Computer Science, Meiji University |
| 第 4 著者 氏名（和/英） | 永山 忍 / Shinobu NAGAYAMA |
| 第 4 著者 所属（和/英） | 明治大学理工学部 Department of Computer Science, Meiji University |
| 発表年月日 | 2001/11/22 |
| 資料番号 | VLD2001-100,ICD2001-145,FTS2001-47 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 467 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |