大規模集積回路技術の向上により、数十万ゲート規模の回路の実現
が可能となっている。大規模な論理回路を短時間で設計することは
重要な課題である。その一手法として論理関数分解がある。
論理関数分解は、与えられた大規模で複雑な論理関数をより簡単で
小さな複数の論理関数に分解する手法である。本論文では、入力変
数集合Xを要素の重なりのないXB,
XFの二つの集合に分割し、
f(X)=g(h(X B),XF)
という形で表される論理関数分解を考える。
分解後の論理関数hの出力線数が1となる分解を単純分解、
出力線数が2以上となる分解を非単純分解と呼ぶ。
従来の手法では、
与えられた論理関数を2分決定グラフを用いて表現し、その根ノード
側に着目して入力変数を二つの集合に分割し論理関数分解を行って
いる。本論文では2分決定グラフを用いた論理関数分解において、終
端ノード側に着目した非単純分解の手法を提案する。提案手法によ
る論理関数の非単純分解可能性の必要十分条件を導出し、非単純分
解アルゴリズムを示す。実験により、このアルゴリズムの評価を行
う。