論理関数のXOR分解アルゴリズムについて

• Item type: SIG Technical Reports(1)
• 公開日: 1996-12-12
• タイトル: 論理関数のXOR分解アルゴリズムについて
• タイトル / 言語: en
• タイトル: On Exclusive - Or Decomposition Algorithms of Logic Functions
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: （株）富士通研究所
• 著者所属(英): en
• 著者所属(英): Fujitsu Laboratories LTD.
• 著者名: 松永, 裕介
• 著者名(英): Yusuke, Matsunaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ファクタードフォームはテクノロジ独立なレベルでの回路構造，および回路面積の見積りやテクノロジマッピングの初期解に適した論理関数表現であるが，AND/OR演算子のみを用いているのでXORを含んだ回路に対しては適切な論理式表現とならない．本稿では，XOR演算子を含んだファクタードフォームを生成するための一手法として，関数のXOR分解について取り上げ，2種類のアルゴリズムを提案する．一つは互いに素なサポートを持つ関数への分解を行なうアルゴリズムであり，もう一つはただ一つの変数を共通のサポートとして持つ関数への分解を行なうアルゴリズムである．どちらも二分決定グラフを用いて効率良く実行することができるので，従来のファクタリングアルゴリズムと組み合わせることで，より簡潔な論理式表現を得ることができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Factored form is a natural way to express a logic function with keeping multi-level logic circuit's structure. Thus, its literal count is generally used for evaluating circuit area in technology independent level. And factored form is also a good start point to technology mapping. However, in the case of technology mapping including XOR cells, factored form is not a good measure nor a good start point, because it consists of only AND/OR terms. So, effective algorithms to find a good logic expression including XOR terms are required. This paper describes novel XOR factoring algorithms that find a disjoint support decomposition or a single overlapping support decomposition. Implemented with Binary Decision Diagrams, these algorithms are very efficient. Combining these XOR factoring algorithms with the conventional AND/OR factoring algorithms, simpler logic expressions are expected to be derived.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10096105
• 書誌情報: 情報処理学会研究報告計算機アーキテクチャ（ARC）; 巻 1996, 号 121(1996-ARC-121), p. 1-8, 発行日 1996-12-12
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会