論理関数のあるクラスについて最小性を保証するAND-EXOR論理式の簡単化アルゴリズム

概要

論文の詳細を見る
論理関数fを表現するAND-EXOR論理式の中で積項数が最小のものを最小AND-EXOR論理式と言い,その積項数をτ(f)で表す.与えられた論理関数に対して最小AND-EXOR論理式を求める最小化アルゴリズムは,nを変数の個数としたときO(2^<2^n>)というばく大な計算時間を必要とする.そのため,最小性を保証しないが高速に積項の少ない式を計算する簡単化アルゴリズムが必要とされている.本論文では,部分的に最小性を保証する次のような性質をもつ簡単化アルゴリズムを与える:(1)τ(f)<3(k+1)(kは非負整数)である論理関数に対して必ず最小のAND-EXOR論理式を求める.(2)求めた式の積項数が3(k+1)以下であれば,それは最小である,(3)時間計算量はO(√<3>^<kn^2+(k+C)n>)である.k=0,1,2について実験した結果,それぞれn=20,7,6であるn変数関数について現実的な計算時間で簡単化が可能であることを確認した.また,この簡単化アルゴリズムを利用し,任意の5変数関数に対して高速に最小化を行うアルゴリズムを示す.5変数関数についての最小化はこれまでに開発されたものに比べはるかに高速である.
社団法人電子情報通信学会の論文
1995-04-25