論理回路設計において、論理関数分解は回路合成等の段階で用いられる重要な処理である。本論文では論理関数の分離的非単純分解アルゴリズムを提案する。論理関数分解とは、与えられた論理関数Fを論理関数Hと、Fと出力が一致する論理関数Gに分ける処理である。ここでHの入力変数集合はFの入力変数の真の部分集合とし、Gの入力変数集合はHの出力とFの入力変数の部分集合とする。分離的分解とは、Hの入力変数集合とGの入力変数集合に共通部分がない分解である。非単純分解とはHの出力数が2以上となるような分解である。非単純分解は複雑であるため効率のよいアルゴリズムは知られていなかった。
提案するアルゴリズムでは関数を二分決定グラフを用いて操作する。二分決定グラフの終端ノードから第kレベルの各ノードはそのノード以下にあるk個の変数を入力とするk変数関数に対応する。この関数の個数について分解可能性の判定を行い、分解可能な場合はその各ノードが表す各k変数関数を、全て同じl (<k)個のk変数関数の出力を入力とするl 変数関数で表現する。このアルゴリズムを実装し、ベンチマーク回路を用いて実験を行う。