IMPCと両立性対の使用による不完全指定順序回路の最小化の一手法
スポンサーリンク
概要
- 論文の詳細を見る
本論文は不完全指定順序回路の最小化のアルゴリズムについてインプリケーション・チェーン(略してIMPC)と両立性対を用いる新たな手法について提案している.不完全指定順序回路の最小化は古くから研究されており,最近になってRao&Biswasがその手法を理論的に確立し,最小被覆の機械を一意的に求めることができるようになった.しかしながら,この手法は最小化の設計を自動的に行わせようとするとき,多くの困難が伴う.すなわち,この手法では,第一に1次両立性クラスP の閉包集合を1回目にインプライされる両立性クラスの集合と2回以降にインプライされるものとに分け,しかもそれらの両立性クラスは考え得る最大のものとしている.この閉包集合の作成法は複雑である.本論文ではこれを避けるため,各PCにたいして閉包対集合を作成し,要素はIMPC上の両立性対から成るものを採用した.第二にPCの除去に当り,Rao&Biswasの手法では,2つの除去定理を提案しているが,それを何回も繰り返して適用せねばならないという不便さがある.本論文では,IMPC上で弱結合等価UCPを除去可能なPCとして記憶し,さらにIMPC上からこれらを除去して得られたBIMPCを基準としてPCの集合から一挙に不要なものを除去るように2つの除去定理を修正した.本論文の手法を用いた最小化プログラムがBASIC言語によって実現された.
- 一般社団法人情報処理学会の論文
- 1987-06-15