講演名 | 2000/5/5 直交でない関数分解の効率的な列挙手法 松永 裕介, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 本稿では, 与えられた論理関数に対して直交でない関数分解を求める効率の良いアルゴリズムについて述べる.このアルゴリズムは著者が以前開発した二分決定グラフを用いて直交分解を行うアルゴリズムを利用したものである.通常, 直交でない関数分解は多数存在するので無制限に関数分解の列挙を行うことは難しいので, 重複した変数の個数が規定値以下の関数分解のみを列挙する様になっている.7入力程度の論理関数に対して適用したところ, ナイーブなアルゴリズムに比べて5~6倍の高速化が達成されている. |
抄録(英) | This paper describes an efficient algorithm enumerating all the non-disjunctive decomposition of a given function. The algorithm utilized the disjunctive decomposition algorithm using binary decision diagrams that the authors have previously developed. Since, in general, there exist too many non-disjunctive decompositions for ordinary logic functions, the algorithm restricts to enumerate only decompositions whose duplicated variables are less than the given limit. Comparing to the existing naive algorithm, about 5 or 6 times acceleration has been observed for a case of applying to 7-inputs functions. |
キーワード(和) | 論理合成 / 関数分解 / 二分決定グラフ |
キーワード(英) | logic synthesis / functional decomposition / binary decision diagrams |
資料番号 | VLD2000-9 |
発行日 |
研究会情報 | |
研究会 | VLD |
---|---|
開催期間 | 2000/5/5(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | VLSI Design Technologies (VLD) |
---|---|
本文の言語 | JPN |
タイトル(和) | 直交でない関数分解の効率的な列挙手法 |
サブタイトル(和) | |
タイトル(英) | On Enumerating Non-Disjunctive Decompositions of Logic Functions |
サブタイトル(和) | |
キーワード(1)(和/英) | 論理合成 / logic synthesis |
キーワード(2)(和/英) | 関数分解 / functional decomposition |
キーワード(3)(和/英) | 二分決定グラフ / binary decision diagrams |
第 1 著者 氏名(和/英) | 松永 裕介 / Yusuke Matsunaga |
第 1 著者 所属(和/英) | (株)富士通研究所 Fujitsu Laboratories LTD. |
発表年月日 | 2000/5/5 |
資料番号 | VLD2000-9 |
巻番号(vol) | vol.100 |
号番号(no) | 36 |
ページ範囲 | pp.- |
ページ数 | 7 |
発行日 |