| 講演名 | 1998/9/22 FBDDの厳密最小化とパストランジスタ論理の合成への応用 畠田 宏司, 高木 一義, 木村 普二, 渡邉 勝正, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | これまで, 低消費電力回路の実現法として, パストランジスタ論理についての研究が行なわれ, OBDD(Ordered Binary Decision Diagram)を用いた設計手法が提案されている.また, OBDDよりも制約の少ないFBDD(Free BDD)を用いたヒューリスティック手法の提案も行なわれている.本稿では, FBDDを用いたパストランジスタ論理の合成法として, FBDDの節点の厳密最小化法を用いた手法の提案を行なう.まず, FBDDの最小化を, 全てのタイプに対するFBDDを求めるという手法で行なった.次にこの最小化を4変数, 5変数の全NPN同値類の代表元に対して適用し, OBDDとFBDDの最小サイズの数え挙げを行ない, 統計的なデータを求めた.5変数では616126個のNPN同値類の内56%の関数で, FBDDの節点数が少なくなることが確認された.また, MCNCベンチマーク回路を5-1LUT向けにマッピングし, 各LUTの関数をFBDDで最小化したところ, OBDDと比較して最大で約5%サイズが削減できた. |
| 抄録(英) | Recently, design methodologies for Pass-transistor Logic (PTL) circuits based on OBDDs have been studied, in which Boolean functions are expressed as aggregate of small OBDDs, and the component OBDDs are mapped directly to PTL cells. The total size (number of nodes) of OBDDs directly affects the circuit size. In this paper, we investigate a method for PTL synthesis based on exact minimization of FBDDs (Free BDDs). FBDDs are well-studied extension of OBDDs with independent variable ordering on each path. We present statistics showing that more than 56% of 616126 NPN equivalence classes of 5-variable Boolean functions have minimum FBDDs with less size than their OBDDs. We also applied the exact minimization algorithm of FBDDs to MCNC benchmarks after being mapped to 5-1 LUT based FPGAs, and found up to 5% node size reduction. |
| キーワード(和) | FBDD / パストランジスタ論理 / 論理関数 / 関数分解 / 論理最小化 / 低消費電力設計 |
| キーワード(英) | FBDD / Pass-Transistor Logic / Boolean function / function decomposition / logic minimization / low power design |
| 資料番号 | VLD98-62,ICD98-165,FTS98-89 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1998/9/22(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FBDDの厳密最小化とパストランジスタ論理の合成への応用 |
| サブタイトル（和） | |
| タイトル（英） | Exact Minimization of FBDDs for Pass-Transistor Logic Synthesis |
| サブタイトル（和） | |
| キーワード(1)（和/英） | FBDD / FBDD |
| キーワード(2)（和/英） | パストランジスタ論理 / Pass-Transistor Logic |
| キーワード(3)（和/英） | 論理関数 / Boolean function |
| キーワード(4)（和/英） | 関数分解 / function decomposition |
| キーワード(5)（和/英） | 論理最小化 / logic minimization |
| キーワード(6)（和/英） | 低消費電力設計 / low power design |
| 第 1 著者 氏名（和/英） | 畠田 宏司 / Hiroshi Hatakeda |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 2 著者 氏名（和/英） | 高木 一義 / Kazuyoshi Takagi |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 木村 普二 / Shinji Kimura |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 第 4 著者 氏名（和/英） | 渡邉 勝正 / Katsumasa Watanabe |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学情報科学研究科 Graduate School of Information Science, Nara Institute of Science and Technology |
| 発表年月日 | 1998/9/22 |
| 資料番号 | VLD98-62,ICD98-165,FTS98-89 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 287 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |