| 講演名 | 1993/5/27 SBDDを用いた最小単符号単発状態割当 権 容珍, 矢島 脩三, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 非同期式順序回路に対する状態割当の一つである単符号単発状態割当において、命題論理を用いて最小解を得る新手法を提案する。この状態割当問題は、NP-completeであることが知られているHypercube-embedding問題と同値で、今までのHypercube-embedding問題を解くアルゴリズムはbacktracking手法によるものが大部分を占めている。ここでは、新たに導入されたプール変数による命題論理式を作成してみることのみで、その可能性の判定ができ、データの内部表現として共用二分決定図を用いてることにより、大きな論理式を扱うことができる。実験結果で提案された手法の有効性を示す。 |
| 抄録(英) | We propose a new method of the unicode one-shot state assignments for asynchronous sequential circuits,in which the propositional calculus,or Boolean algebra is adopted.Exact minimum solutions of the unicode assignment are obtained by our method.The problem of the unicode one-shot state assignment coincides with the hypercube embedding problem,which is known to be NP-complete. The known algorithms for the hypercube embedding problem almost consist of the mechanism of backtracking.Using newly introduced Boolean variables here,we can check the possibility of the unicode one-shot state assignment or the hypercube embedding for a given flow table or graph by even making propositional formula.In order to handle huge propositional formulas,the shared binary decision diagrams(SBDD′s)are used as an internal representation of the form ulas which denote the unicode assignment for a given flow table. Experimental results show that methods are effective to obtain minimum solutions at significantly reduced computation cost. |
| キーワード(和) | 単符号単発状態割当 / 最小 / 命題論理 / Hypercube embedding / SB DD's |
| キーワード(英) | unicode one-shot state assignment / minimum / propositional calculus / Hypercube embedding / SBDD′s |
| 資料番号 | COMP93-15,SS93-9 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | SBDDを用いた最小単符号単発状態割当 |
| サブタイトル（和） | |
| タイトル（英） | Minimum Unicode One-Shot State Assignment Using SBDD |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 単符号単発状態割当 / unicode one-shot state assignment |
| キーワード(2)（和/英） | 最小 / minimum |
| キーワード(3)（和/英） | 命題論理 / propositional calculus |
| キーワード(4)（和/英） | Hypercube embedding / Hypercube embedding |
| キーワード(5)（和/英） | SB DD's / SBDD′s |
| 第 1 著者 氏名（和/英） | 権 容珍 / Yong-Jin Kwon |
| 第 1 著者 所属（和/英） | 京都大学工学部情報工学科 Faculty of Engineering,Kyoto University |
| 第 2 著者 氏名（和/英） | 矢島 脩三 / Shuzo Yajima |
| 第 2 著者 所属（和/英） | 京都大学工学部情報工学科 Faculty of Engineering,Kyoto University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-15,SS93-9 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 7 |
| 発行日 | |