主閉包集合の上限値設定による不完全指定順序回路の複数最小解の生成法
スポンサーリンク
概要
- 論文の詳細を見る
不完全指定順序回路の内部状態の最小化について筆者が先に提案した手法はRao &Biswas の手法に比し計算機向きの手法として有効である.ただ,最小化の過程で代表的両立性クラスの数が増大したりすると,主閉包集合を求めるための計算量が膨大になり,計算が不可能になることがあった.さらにこの方法は少なくとも1個の最小閉被覆解を求めるには有効であったが複数解を求めるときには必ずしも有効ではなかった.Rao & Biswasはこれらの問題にたいし若干の着想を述べてはいるが明確ではない.本論文は理論的にこれらの問題を解析し,さらにアルゴリズムを構築してプログラムを作成し,本論文の手法の有効性を実証している.本論文では場合によって膨大な計算となる主閉包集合の計算量を減少させるため,始めに最小閉被覆を構成する代表的両立性クラスの数の上限値uvbを決定し,この値以下の個数の代表的両立性クラスよりなる主閉包集合を導出するような代表的両立性クラスを予測し,そうでないものは最初から抹消するようにしているこのような予測には主閉包集合行列の最大非冗長列線集合の概念を導入し,計算を簡便にするよう配慮した.また閉被覆を満たさない主閉包集合の合併や最小閉被覆の構成要素である代表的両立性クラスを一次両立性クラスで置換するようにする配慮も行って複数解が得られることを容易にしている.
- 一般社団法人情報処理学会の論文
- 1988-09-15
著者
関連論文
- 縮小探索行列法による不完全指定順序回路の最大両立性クラスの生成法
- 並列処理アルゴリズムを用いた多段合成による論理関数の主項の生成
- 多分枝展開法を用いた主項生成について
- 2分決定グラフ(BDD)使用による主項生成
- 積和型論理式の因数分解処理による多段合成
- 一線入力3段 NAND ゲート回路の行列法による最小化手法
- 論理関数主項の複数最小被覆の一導出法
- 縮小探索行列法による不完全指定順序回路の最大両立性クラスMCCの生成
- 1線入力3段NANDゲ-ト回路の生成の一手法
- 一線入力論理多段NANDゲート回路の縮約法の検討
- 禁止用ループの使用による一線入力NANDゲート回路の生成の一手法
- 一線入力論理3段NANDゲート回路の一設計法
- 不完全指定順序回路の内部状態数最小化のためのLISP言語プログラム
- 2分探索木による論理関数の簡単化の一手法
- 隣接グル-プ生成法と分割法による論理関数の簡単化の一手法
- 主閉包集合の上限値設定による不完全指定順序回路の複数最小解の生成法