講演名 | 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 |
発行日 |