素子制限のある論理回路を等価変換するための基本操作集合について
スポンサーリンク
概要
- 論文の詳細を見る
論理回路の自動設計は近年その重要性を増々大きなものにしている.数多くの手法や考え方が提案されているが,その代表的なものは,まず何らかの方法で初期回路を設計し,段階的により性質の良い回路に変形していくというものである.また,最近注目を集めているアルゴリズムの効率を実験的に評価するためのテスト例題の生成では,逆に性質の良い回路(アルゴリズムが導き出すべき答)から悪い回路(アルゴリズムの入力とする)に変形できる必要がある.いずれの場合も,論理回路の等価変換(回路が実現する論理関数を変えることなく変形する)が鍵になる.我々はこれまでの研究で,論理回路としては,AND,OR,NOT素子が使える組合せ回路を対象として,任意の論理回路から任意の等価な論理回路へ変換するための完全な基本操作規則の集合を提案した.ここで,"変換"は1回の操作が多項式時間で実行できる"基本操作"の列で定義している.本稿では,使える素子をNANDのみに制限した組合せ回路を対象とする.NANDをANDとNOTの組合せとみれば,NANDに制限された回路を素子制限のない通常のAND,OR,NOTの回路の部分集合とみなせる.従って,上記の規則を適用すれば,任意のNAND回路f_1から任意のNAND回路f_2へ変換することは可能である.しかし,この場合,f_1からf_2への変換の過程で,NAND素子のみでない回路を経由しなくてはならない.本稿の立場は,常にNAND回路という制限を犯すことなく変換を進めていることに注意されたい.いわゆる変換公式についても,AND,OR,NOTの場合に比べて,あまり知られてないようにみえる.NANDという論理はゲートの重要な電子回路実現に本質的に関係しているため,一般にシステムの回路はNAND(あるいはNOR)ゲートを使用して設計されることが多く,実用的な面でも重要である.
- 一般社団法人情報処理学会の論文
- 1993-03-01
著者
関連論文
- NP完全集合によるco-NP完全集合の近似
- 充足可能性問題に対する計数法の項の選択による高速化
- グラフの色ぬり分け問題からSATへの効率の良い変換方法とその評価
- RS型ベクトル機械上での幾つかの具体的問題に対するアルゴリズム
- 「高度応用のための情報ベースモデルとその実現技術」を目指して (メディア統合および環境統合のための高機能データベースシステム、および一般)
- ブロック同期方式による並列アルゴリズムの記述とそのプログラム化
- ブロック同期に基づく並列アルゴリズムアニメーションシステム
- 充足可能性問題に対する計数法の変数の選択による改良
- 正則グラフに対する密な部分グラフ問題
- トランスダクション法のための二分決定グラフを用いた束探索に基づく3段初期回路の生成
- ファンイン制限つき組合せ論理回路に対する完全な等価変換規則集合
- 素子制限のある論理回路を等価変換するための基本操作集合について
- 回路パタンに基づく回路変換システムの開発
- パターンベースによる冗長性の付加を考慮したトランスダクション法に関する考察
- ランダムベンチマーク例題による論理最適化システムの評価
- ランダムベンチマーク例題による論理最適化システムの評価
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理最適化アルゴリズム評価のためのテスト例題のランダム生成
- 論理回路簡単化問題に対する例題生成
- 一切の情報を漏らさずプログラムの正当性を証明する方法
- 並列計算用に拡張したTMの時間計算量の階層
- チューリング機械の領域計算量の厳密な階層について(計算理論とその応用)
- テープ記号数を制限した領域限定TMの階層について
- CNF論理式に対する局所探索法の項の追加による改良
- リテラルの出現回数を制限した充足不能な3CNF式
- リテラル出現回数が2回の充足不能な3SAT式
- 確率的手法によるCRCW PRAM間の模倣について
- ファンイン制限つきトランスダクション法におけるゲート変更の導入
- 遅延を考慮したトランスダクション法におけるファンイン制限手法
- トランスダクション法のための3段初期回路生成手続きの改良とその評価
- OR表現を含むデータベース質問に対する自然言語表現の生成
- メッシュバス上での最小全域木アルゴリズム
- グラフの最小全域木を求めるためのメッシュバス上での並列アルゴリズム
- 最大値問題に対するメッシュバス上でのO((log log n)^2)アルゴリズム
- PRAMおよび対数時間一様な論理回路族に基づく計算量の階層(計算モデルと計算の複雑さに関する研究)
- $\alpha$連結成分問題の計算複雑さの上昇について(計算量理論)
- 並列化が徐々に困難になるグラフ問題について
- 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)
- 組合せ問題に対する RS 型ベクトルアルゴリズム
- RS型ベクトル機械の実際的応用の可能性について(計算および計算量理論とその周辺)
- 密な部分グラフ問題のNP完全性とそのSAT例題生成への応用
- AIMジェネレータによるバックトラック及び局所探索SATアルゴリズムの評価