多出力関数のBDDによる表現法とその最適化法

概要

論文の詳細を見る
本論文では, 多出力関数の新しい表現方法:ECFN(Encoded Characteristic Function for Non-zero outputs)を提案する.ECFNは, n入力m出力の関数を表現するために(n+u)個の2値変数を使う。ここで, u=「1og_2m」である.ECFNを表現するBDD(Binary Decision Diagram)は, SBDD(Shared BDD)より大きくなることはなく, 多くの場合小さくできる.ECFNでは出力の符号化を工夫することによってBDDを縮小できるが, これは変数順序の変更と同様に効果的である.最適な符号化をしたECFNを表現するBDDの節点数が, 2n+2個であり, 最悪の符号化をした節点数が2^<n+1>となるようなn入力2^n出力の関数が存在することを示す.次にECFNの符号化問題を定式化し, 発見的手法を提案する.標準的なベンチマーク関数を使用した実験結果により, 符号化を考慮することによってBDDの大きさを大幅に削減できることを示す.また, ECFNの組み込みシステムヘの応用も述べる.
2001-11-22