Comparative Study by Solving the Test Compaction Problem
Doina Logofătu, Rolf Drechsler · Proceedings/Proceedings - International Symposium on Multiple-Valued Logic · 2008
Beside issues like the low power dissipation and the increase of defect coverage, test compaction is an important requirement regarding large scale integration (LSI) testing. The overall cost of a VLSI circuit’s testing depends on the length of its test sequence; therefore the reduction of this sequence, keeping the coverage, will lead to a reduction of used resources in the testing process. In this paper we study test vectors over a five-valued logic. The problem of finding minimal test sets is NP-complete. Consequently, an optimal algorithm has limited practical use and is only applicable to small problem instances. We describe three approaches for reducing the length of test sequences: an optimal algorithm using a recursive backtracking method (OPT) and two greedy algorithms (GRNV and GRBT). The behavior of these algorithms is discussed and analyzed by experiments. Finally, directions for future work are given.