入力ベクトルからの信号値を正当化する最小キューブ抽出

摘要

ある人力ベクトルによって組合せ回路内部の信号値が正当化されるとき，その内部信号値を正当化する外部入力値はキューブで表すことができる．本論文では，ある人カベクトルから内部信号値を正当化する最小キューブ摘出手法を提案する．正当化する信号値が一つの場合を基に，複数の信号線を同時に正当化する最小キューブ抽出手法へ拡張する．複数信号値を正当化する場合は，正当化可能なすべてのキューブをBDDで表現し，キューブ抽出問題をBDD上での最短路問題に帰着させる．提案手法は，テストベクトルの特定ビット数が最小であるテストキューブの探索に使用でき，そのようなテストキューブは例えばテストデータコンプレッションの効果を高めるのに有効である．