論理関数の共有二分決定グラフによる表現とその効率的処理手法

概要

論文の詳細を見る
論理関数を効率よく表現し,論理演算を高速に行うことは,論理設計支援システムを実現する上で重要な問題である.AkersやBryantが提案した二分決定グラフによる表現法は,入力変数の順序を固定することにより論理関数を一意に表すことができ,また,多くの実用的な関数を比較的コンパクトに表現できる.さらに,複数の関数を同時に効率良く表現できるように改良したものを共有二分決定グラフと呼ぶ.本論文では,共有二分決定グラフを用いた論理関数の処理手法について述べ,その効率化手法として,否定エッジ,入力反転エッジ,変数シフトエッジの3種類の属性エッジを用いて記憶量や処理時間を削減する方法を提案する.共有二分決定グラフにおいては,入力変数の順序づけはグラフの大きさに著しい影響を与えるため,この問題について考察し,効率のよい順序づけを行う動的重みづけ法を提案する.さらに,不完全指定論理関数(Don't careを含む関数)について考察し,D変数を導入した表現法を提案する.最後に,本論文で提案した手法の効果を調べるため,実用的な論理回路を共有二分決定グラフで表現する実験を行い,本論文の手法が有効であることを示す.
一般社団法人情報処理学会の論文
1991-01-15