為了解決龐大測試資料的問題，對於測試響應資料傳統上常使用硬體壓縮電路來降低測試響應的資料量，雖然可以達到相當不錯的壓縮率，但是使用硬體壓縮電路會面臨兩大問題:一個是失真問題，另一個為不確定值覆蓋錯誤資訊的問題。在本篇論文中，我們提出了一個以輸出選擇為基礎的響應壓縮技術，藉由輸出選擇的機制，選擇所想要觀察的響應資料，在此機制下，由於所想要觀察的輸出響應可直接觀察，因此不會有前述的失真以及不確定值覆蓋錯誤資訊的兩個問題。我們並且提出了相對應的啟發式方法，在不影響錯誤涵蓋率之下加以有效地選取所需觀察的輸出響應。也因為此選取機制，只觀察所須觀察的輸出響應，來加以壓縮測試響應的資料量。由實驗結果顯示，對於ISCAS的標準電路使用已緊密壓縮的測試向量，平均只需要觀察其中14%的測試響應即可達到原來的錯誤涵蓋率，其中的幾個大電路更只需要觀察5%即可。此外，我們更針對所需要觀察的資料提出了一個下限分析，此下限分析是根據一個電路上的特性加以進行運算，透過此一特性我們可以在相當低的空間複雜度以及運算複雜度下求得下限。實驗結果顯示，所求得的下限與啟發式方法所得到的觀察數平均而言只相差13%，可知啟發式方法所得的觀察數與最佳解相距不遠。

Conventionally, XOR-tree based compactors or multiple input signature registers (MISRs) are used to reduce test response volume and a very high compaction ratio has been achieved. However, these designs may suffer from the aliasing, the unknown-value and/or the X-masking problems. In this paper, we introduce a new test compaction method called the output-selection-based response compaction method that that can eliminate these problems efficiently. The basic idea is to observe only a fraction of output bits while still guarantee the same fault coverage as that can be achieved by observing all output bits. We shall show that this problem is equivalent to the set cover problem which is a well-known NP-complete problem. We thus propose a heuristic selection procedure to efficiently select the output bits that need to be observed. Experimental results for ISCAS benchmark circuits show that even for highly compacted test patterns sets, only about 5% of outputs of the test sets need to be observed for most large benchmark circuits. To evaluate how effective the proposed method is, we also analyze the lower bound of the number of bits to be selected and present an algorithm with low memory and computation complexity to estimate this lower bound. The difference between the lower bound and the number of selected observation bits obtained by the heuristic procedure is only approximately 13% on the average.

[1]　L.　T.　Wang,　C.　W.　Wu,　and　X.　Wen,　“VLSI　Test　Principles　and　Architectures:　Design　for　Testability,”　Morgan　Kaufmann,　2006.

[2]　J.　Rajski,　J.　Tyszer,　C.　Wang,　and　S.　M.　Reddy,　“Finite　Memory　test　response　compactors　for　embedded　test　applications,”　IEEE　Trans.　Computer-Aided　Design,　Vol.　24,　pp.　622-634,　April　2005.

[3]　P.　Wohl,　J.　A.　Waicukauski,　and　S.　Patel,　“Scalable　Selector　Architecture　for　X-Tolerant　Deterministic　BIST,”　in　Proc.　Design　Automation　Conf.,　pp.　934-939,　2004.

[4]　I.　Pomeranz,　S.　Kundu,　and　S.　M.　Reddy,　“On　Output　Response　Compression　in　the　Presence　of　Unknown　Output　values,”　in　Proc.　Design　Automation　Conf.,　pp.　255-258,　2002.

[5]　C.　Barnhart,　V.　Brunkhorst,　F.　Distler,　O.　Farnsworth,　A.　Ferko,　B.　Keller,　D.　Scott,　B.　Koenemann,　and　T.　Onodera,　“Extending　OPMISR　Beyond　10x　Scan　Test　Efficiency,”　IEEE　Design　&　Test　of　Computers,　Vol.　19,　pp.　65-73,　2002.

[6]　J.　Rajski,　M.　Kassab,　N.　Mukherjee,　N.　Tamarapalli,　J.　Tyszer,　and　J.　Qian,　“Embedded　Deterministic　Test　for　Low-Cost　Manufacturing,”　IEEE　Design　&　Test　of　Computers,　Vol.　20,　pp.　58-66,　2003.

[7]　M.　Naruse,　I.　Porneranz,　S.　M.　Reddy,　and　S.　Kundu,　“On-Chip　Compression　of　Output　Responses　with　Unknown　Values　Using　LFSR　Reseeding,”　in　Proc.　Int.　Test　Conf.,　pp.　1060-1068,　2003.

[8]　H.　Ando,　“Testing　VLSI　with　Random　Access　Scan,”　in　Proc.　COMPCON,　pp.　50-52,　1980.

[9]　A.　Caprara,　P.　Toth,　and　M.　Fischetti,　“Algorithms　for　the　Set　Covering　Problem,”　Annals　of　Operations　Research,　Vol.　98,　pp.　353-371,　2000.

[10]　X.　Y.　Li,　M.　F.　Stallmann,　and　F.　Brglez,　“Effective　Bounding　Techniques　for　Solving　Unate　and　Binate　Covering　Problems,”　in　Proc.　Design　Automation　Conf.,　pp.　385-390,　2005.

[11]　O.　Coudert,　"Two-Level　Logic　Minimization:　An　Overview",　Integration,　VLSI　journal,　pp.　97-140,　Oct.　1994.

[12]　O.　Coudert,　and　J.　C.　Madre,　“New　Ideas　for　Solving　Covering　Problems,”　in　Proc.　Design　Automation　Conf.,　pp.　641-646,　1995.

[13]　Vangelis　T.　Paschos,　“A　Survey　of　Approximately　Optimal　Solutions　to　Some　Covering　And　Packing　Problems,”　ACM　Computing　Surveys,　Vol.　29,　pp.　171-209,　June　1997.

[14]　S.　Kajihara,　I.　Pomeranz,　K.　Kinoshita,　and　S.　M.　Reddy,　“Cost　Effective　Generation　of　Minimal　Test　Sets　for　Stuck-at　Faults　in　Combinational　Logic　Circuits,”　IEEE　Trans.　Computer-Aided　Design,　Vol.　14,　pp.　1496-1504,　Dec.　1995.