論理関数表現のモデルとシンボリックアルゴリズム

点击翻译按钮获取中文摘要

1.二分決定グラフによるデータ表現については、第一に、二分決定グラフの構造を論理関数で表現する二分決定グラフの非明示的表現を用いて、効率的な表現が可能な論理関数について研究を行ない、多変量閾値関数を入力変数のビット長に依存しないサイズで表現できることを示した。第二に、A07班山下との共同研究により、量子論理関数を効率よく表現するためのOBDDの変種データ構造を比較検討し、山下が以前に提案したDecisionDiagrams for Matrix Functions(DDMFs)の有効性を理論的に考察した。このデータ構造が、量子論理回路に特有の制約条件をうまく利用しており、単純なOBDDよりも一層データを圧縮し、処理効率を高めていることを明らかにした。2.OBDDに基づくシンボリックアルゴリズムについては、前年度に引き続き、トポロジカルソートの列挙、OBDDによる画像処理アルゴリズムについて研究を行なった。前者では先行頂点数等を求めることにより従来法より計算過程でのOBDDサイズを大幅に抑えられることを示した。後者ではOBDD予測符号化を用いることによりOBDDサイズが圧縮可能であり、提案済みの画像処理アルゴリズムをほぼそのまま利用できることを示した。また、OBDDを用いたナンバーリンクの解法、問題の正当性の判定手法の提案・実装を行なった。