テストパターンの静的圧縮における厳密解と貪欲解の比較

摘要

本稿ではドントケアに基づく静的テストパターン圧縮をクリーク被覆問題や頂点彩色問題として定式化し，厳密解法と貪欲解法による解法実験を行った．その結果，今回実験を行ったほとんどのテストパターンについて圧縮されたテストパターン数の上界と下界が厳密解と一致することがわかった．また，この性質はテストパターンの生成方法を変えても保たれていた。このことから，貪欲法の解は厳密解に非常に近いことがわかり，多数の回路に対して長時間かけて厳密解を求める効果が少ないことがわかった．さらに圧縮の妨げになっているテストパターンを示し，圧縮効果を高める方法を考察する．