測試響應壓縮技術被廣泛用於降低因超大型積體電路日益複雜所造成的龐大測試資料量。然而傳統以多重輸入特徵暫存器(MISR)或互斥閘為基礎的樹狀網路(XOR-tree-based networks)為基礎的輸出壓縮方法，經常遭遇到壓縮失真、測試響應包含未知值及壓縮後錯誤診斷能力過低等問題。在這篇論文中，我們提出了一嶄新的測試響應壓縮技術，稱之為輸出位元選擇方法(output-bit-selection)。藉由透過選擇邏輯選取一小部分的輸出響應直接進行觀察，該方法能夠有效地解決所有上述提及的問題。

首先我們將輸出位元選擇問題轉換成一最小集合覆蓋問題，以分析輸出位元選擇方法對測試響應的壓縮效率。接著我們提出一高效率的貪婪演算法以快速得找到一組極趨近最佳解的輸出位元集合，用以測試電路中所有能夠被測試到的錯誤。實驗結果顯示在ISCAS標準電路上，我們的方法僅需觀察少於10%的測試響應就能夠達到100%的定值錯誤涵蓋率(stuck-at fault coverage)。針對更大型的ITC’99標準電路而言，我們的方法只需觀察少於3%的輸出測試響應，便足以測試到待測電路中所有的定值錯誤(stuck-at fault)。比起考慮單一類型的錯誤測試，當應用我們的方法至考慮多種不同類型的錯誤測試的測試響應時，其結果顯示所需觀察的測試響應比率將會更低。除此之外，我們的結果更顯示經輸出位元選擇方法壓縮後，仍然能夠保有與壓縮前幾乎相同的錯誤診斷解析度(diagnosis resolution)。

在實現輸出位元選擇方法時，所需的硬體設計複雜度與所應用的測試架構有著強烈的相關性。在本論文中，我們研究如何將輸出位元選擇方法實現在兩種較常見的掃描式測試架構，隨機存取式掃描(random access scan)與連續式掃描(serial scan)上。對於一支援隨機存取式掃描的待測電路，隨機存取式掃描測試架構中的控制器與行列解碼器均能夠被重複用於輸出選擇，因此僅需極少量的額外硬體負擔，便可選擇所需的輸出響應位元以進行觀察。

對於一支援連續式掃描的待測電路，我們提出一以計數器為基礎的輸出選擇方法，利用單一計數器與一多工器做為選擇邏輯，以選擇需要觀察的輸出響應位元。為了決定所有需觀察的輸出位元，我們提出兩種輸出選擇演算法，一考慮單一的計數器操作模式(counter operation)以簡化控制，另一則使用多種不同的計數器操作模式以達到更高的測試響應壓縮率。實驗結果顯示在測試ISCAS’89與ITC’99電路中的定值錯誤時，48%~90%的測試響應資料量能夠被我們的方法所化簡。而對於傳遞延遲型錯誤(transition fault)的測試，我們的方法更可以減少高達76%~95%的測試響應資料量。另外，實驗結果也顯示我們的壓縮方法能夠保留住多數的錯誤診斷資訊，其壓縮前後的錯誤診斷解析度的平均差異僅0.00097%。由於我們的壓縮硬體只需使用一計數器與一多工器，因此所需的面積負擔僅佔待測電路面積的0.31%~1.29%。

為了更進一步縮短所需的測試時間，我們提出以多個計數器為基礎的輸出選擇架構。此一架構能夠在單一輸出週期同時選擇多個輸出響應位元進行觀察，以減少所需的測試時間。應用於IWLS’05電路後，實驗結果顯示比起使用單一計數器的壓縮架構，使用2~4個計數器同時進行輸出位元選擇，僅需1.50%~3.00%的面積負擔便能夠成功減少47%~67%的測試時間。而對於測試響應包含未知值的壓縮問題，我們也提出一未知值避免(X-Avoidance)技術，用以在輸出位元選擇時避免選取到包含未知值響應的輸出位元。由於此一技術能夠避免掉絕大多數的未知值，因此對於極少數剩餘的未知值，只需使用非常簡單的遮蔽邏輯便能夠將所有剩餘的未知值進一步從壓縮後的測試響應中除去。在這篇論文中，我們也提出能夠考慮未知值避免的輸出選擇演算法，用以在選擇所需的輸出響應位元時，避免選取到未知值響應。應用此方法至IWLS’05電路後，其結果顯示即使高達16%的輸出響應均包含未知值，我們的方法仍舊能夠避免將任何未知值傳遞至輸出端，同時減少高達88%~92%的測試響應資料量。

本論文中所提出的輸出位元選擇方法有許多的優點，包含了極高的壓縮率、零失真、能夠容忍包含任意數量的未知值響應、高錯誤診斷能力、面積負擔低且容易控制。由於不需對待測電路或自動測試向量產生器工具進行任何修改，因此該方法能夠很輕易的整合至任何典型的工業界測試流程中，在不損失測試品質且不增加額外測試向量資料的情況下，大幅度地降低直流式掃描與交流式掃描測試所需的測試成本。

Test response compaction techniques are widely used to reduce test data volume for integrated circuits. However, the conventional output compaction methods based on Multiple-Input-Signature-Registers (MISR) and/or XOR-tree-based networks often suffer from the problems of error aliasing, unknown-values, and poor diagnosability. In this dissertation, we present an alternative technique, named the output-bit-selection method for test response compaction. By directly observing only a small subset of desired output response bits through some selection logic, this method can effectively deal with all the above mentioned problems.

We first formulate the output-bit-selection problem as a minimum set covering problem and then analyze the efficiency of output-bit-selection method for test response compaction. Efficient algorithms that can identify near optimum subsets of output bits to cover all detectable faults in very large circuits are developed. The experimental results show that less than 10% of the output response bits of an already very compact test set are enough to achieve 100% single stuck-at fault coverage for most ISCAS benchmark circuits. Even better results are obtained for ITC’99 benchmark circuits as less than 3% of output bits are enough to cover all stuck-at faults in these circuits. The increase ratio of selected bits to cover other types of faults is shown to be quite small if these faults are taken into account during test generation. Furthermore, the diagnosis resolution of this method is almost the same as that achieved by observing all output response bits.

The implementation complexity of the output bit selection method strongly depends on the test architectures employed. In this work, we investigate how to apply the output-bit- selection method to two general scan architectures: random access scan and serial scan. For a circuit with random-access scan scheme, very little additional hardware is required for output bit selection as the controller and the row/column decoders in the random-access scan test architecture can be reused to select any desired bits.

For a serial scan based design, we present a counter-based output selection approach that employs a counter and a multiplexer as the selection logic to efficiently select all desired output response bits. Two efficient output selection algorithms are presented to determine the desired output responses, one using a single counter operation for simpler test control and the other using more counter operations for better test response reduction ratio. Experimental results show that for stuck-at faults in large ISCAS’89 and ITC’99 benchmark circuits, 48%~90% reduction ratios on test responses can be achieved with only one counter and one multiplexer employed. Even better results, i.e., 76%~95% reductions, can be obtained for transition faults. It is also shown that most diagnosis information can be preserved; in general the diagnosis resolution loss is only 0.00097% on average. Since only a counter and a multiplexer are employed for our scheme, the required area overhead is quite small, ranging between 0.31% and 1.29%.

In order to further shorten the test application time, a multiple-counter-based output selection method is then presented to observe more than one output response bits at each scan-out cycle. Experimental results on IWLS’05 benchmark circuits show that compared with the single-counter-based scheme, the proposed method can reduce 47%~67% test application time by using 2~4 counters with 1.50%~3.00% area overhead. To deal with the unknown-value problems, we present an X-Avoidance technique to avoid almost all unknown values during the selection process. The remaining small number of unknowns can then be easily dealt with by using very simple masking logic. A new bit-selection algorithm with X-Avoidance capability is presented to select appropriate output bits to observe and avoid as many unknown responses as possible. Experimental results on IWLS’05 benchmarks show that even when 16% of the responses are unknowns, all unknown values can be efficiently avoided while 88%~92% response-volume reduction is achieved.

The proposed output-bit-selection method has several advantages, including very high compaction ratio, zero aliasing, fully X-tolerance, high diagnosability, low area overhead and simple test control. Also no circuit/ATPG modification is needed, hence this method can be easily integrated into any typical industrial test flow to significantly reduce the test cost of both DC- and AC-scan testing with no pattern inflation and no test quality loss.

[1] 2013 International Technology Roadmap of Semiconductors (ITRS) roadmap, link: http://www.itrs.net/Links/2013ITRS/Home2013.htm.
[2] L.-T. Wang, C.-W. Wu, and X. Wen, VLSI Test Principles and Architectures: Design for Testability, Morgan Kaufmann, 2006.
[3] K. Chakrabarty and J. P. Hayes, “Zero-Aliasing Space Compaction of Test Response Using Multiple Parity Signatures,” IEEE Transactions on Very Large Scale Integration Systems, Vol. 6, Issue 2, pp. 309-313, Jun. 1998.
[4] S. Biswas, S. R. Das, and E. M. Petriu, “Space Compactor Design in VLSI Circuits Based on Graph Theoretic Concepts,” IEEE Transactions on Instrumentation and Measurement, Vol. 55, Issue 4, pp. 1106-1118, Aug. 2006.
[5] A. Hossain, S. R. Das, A. R. Nayak, E. M. Petriu, S. Biswas, and M. Sahinoglu, “Further Studies on Zero-Aliasing Space Compression Based on Graph Theory,” in Proc. Instrumentation and Measurement Tech. Conference, 2007, pp. 1-6.
[6] K. Chakrabarty, B. T. Murray and J. P. Hayes, “Optimal Zero-Aliasing Space Compaction of Test Responses,” IEEE Transactions on Computers, Vol. 47, Issue 11, pp. 1171-1187, Nov. 1998.
[7] Bhargab B. Bhattacharya, A. Dmitriev, M. Gössel, and K. Chakrabarty, “Synthesis of Single-Output Space Compactors for Scan-Based Sequential Circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 21, Issue 10, pp. 1171-1179, Oct. 2002.
[8] S. Mitra and K. S. Kim, “X-Compact: An Efficient Response Compaction Technique,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 23, Issue 3, pp. 421-432, Mar. 2004.
[9] S. Manish and W.-T. Cheng, “X-filter: filtering unknowns from compacted test responses,” in Proc. International Test Conference, 2005, pp. 1089-1098.
[10] L.-T. Wang, X. Wen, H. Furukawa, F.-S. Hsu, S.-H. Lin, S.-W. Tsai, K.S. Abdel-Hafez, and S. Wu, “VirtualScan: A New Compressed Scan Technology for Test Cost Reduction,” in Proc. International Test Conference, 2004, pp.916-925.
[11] H. Tang, C. Wang, J. Rajski, S. M. Reddy, J. Tyszer and I. Pomeranz, “On efficient X-handling using a Selective Compaction Scheme to Achieve High Test Response Compaction Ratios,” in Proc. International Conference on VLSI Design, 2005, pp. 59–64.
[12] J. Rajski, J. Tyszer, C. Wang, and S. M. Reddy, “Finite Memory Test Response Compactors for Embedded Test Applications,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24, Issue 4, pp. 622-634, Apr. 2005.
[13] M. Naruse, I. Porneranz, S. M. Reddy, and S. Kundu, “On-Chip Compression of Output Responses with Unknown Values Using LFSR Reseeding,” in Proc. International Test Conference, 2003, pp. 1060-1068.
[14] S. Wang, K. J. Balakrishnan and W. Wei, “X-Block: An Efficient LFSR Reseeding-Based Method to Block Unknowns for Temporal Compactors,” IEEE Transactions on Computer, Vol. 57, Issue 7, pp. 978-989, May 2008.
[15] I. Pomeranz, S. Kundu, and S. M. Reddy, “On Output Response Compression in the Presence of Unknown Output values,” in Proc. Design Automation Conference, 2002, pp. 255-258.
[16] Y. Tang, H.-J. Wunderlich, P. Engelke, I. Polian, B. Becker, J. Schloffel, F. Hapke and M. Wittke, “X-masking during logic BIST and its impact on defect coverage,” IEEE Transactions on Very Large Scale Integration Systems, Vol. 14, Issue 2, pp. 193-202, Feb. 2006.
[17] 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, Issue 5, pp. 65-72, Sep. 2002.
[18] 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, Issue 5, pp. 58-66, Sept.-Oct. 2003.
[19] W.-C. Wang, C,-Y. Hsu, J. Li, Y.-C. Sung, A. Rao and L.-T. Wang, “Row-linear feedback shift register-column x-masking technique for simultaneous testing of many-core system chips,” IET Computers & Digital Techniques, Vol. 5, Issue 4, pp. 238-246, Jul. 2011.
[20] T. Rabenalt, M. Richter, F. Poehl and M. Goessel, “Highly Efficient Test Response Compaction Using a Hierarchical X-Masking Technique,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 31, Issue 6, pp. 950-957, Jun. 2012.
[21] A. Chandra, Y. Kanzawa and R. Kapur, “Proactive Management of X's in Scan Chains for Compression,” in Proc. International Symposium on Quality Electronic Design, 2009, pp. 260-265.
[22] D. Czysz, G. Mrugalski, N. Mukherjee, J. Rajski and J. Tyszer, “On Compaction Utilizing Inter and Intra-Correlation of Unknown States,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 29, Issue 1, pp. 117-126, Jan. 2010.
[23] P. Wohl, J. A. Waicukauski and F. Neuveux, “Increasing Scan Compression by Using X-chains,” in Proc. International Test Conference, 2008, pp. 1-10.
[24] P. Wohl, J. A. Waicukauski, F. Neuveux and E. Gizdarski, “Fully X-Tolerance, Very High Scan Compression,” in Proc. Design Automation Conference, 2010, pp. 362-367.
[25] J. Rajski, J. Tyszer, G. Mrugalski, W.-T. Cheng, N. Mukherjee, and M. Kassab, “X-Press: Two-Stage X-Tolerant Compactor with Programmable Selector,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, Issue 1, pp. 147-159, Jan. 2008.
[26] J.-S. Yang and N. A. Touba, “X-Canceling MISR Architectures for Output Response Compaction with Unknown Values,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 31, Issue 9, pp. 1417-1427, Sep. 2012.
[27] A. A. Bawa, M. T. Rab and N. A. Touba, “Using Partial Masking in X-Chains to Increase Output Compaction for an X-Canceling MISR,” in Proc. International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, 2012, pp. 19-24.
[28] P. Wohl, J. A. Waicukauski, S. Patel, and M. B. Amin, “X-tolerant compression and application of Scan-ATPG patterns in a BIST architecture,” in Proc. International Test Conference, 2003, pp. 727-736.
[29] P. Wohl, J. A. Waicukauski, and S. Patel, “Scalable Selector Architecture for X-Tolerant Deterministic BIST,” in Proc. Design Automation Conference, pp. 934-939, 2004.
[30] A. S. Mudlapur, V. D. Agrawal and A. D. Singh, “A random access scans architecture to reduce hardware overhead,” in Proc. International Test Conference, 2005, pp.350-358.
[31] D. H. Baik and K. K. Saluja, “Progressive Random Access Scan: a simultaneous solution to test power, test data volume and test time,” in Proc. International Test Conference, 2005, pp.359-368.
[32] C. Yao, K. K. Saluja and A. A. Sinkar, “WOR-BIST: A Complete Test Solution for Designs Meeting Power, Area and Performance Requirements,” in Proc. International Conference on VLSI Design, 2009, pp. 479-484.
[33] Y. Hu, X. Fan and H. Fujiwara, “Localized random access scan: Towards low area and routing overhead,” in Proc. Asia and South Pacific Design Automation Conference, 2008, pp. 21-24.
[34] A. Caprara, P. Toth, and M. Fischetti, “Algorithms for the Set Covering Problem,” Annals of Operations Research, Vol. 98, Issue 1-4, pp. 353-371, Dec. 2000.
[35] X. Y. Li, M. F. Stallmann, and F. Brglez, “Effective Bounding Techniques for Solving Unate and Binate Covering Problems,” in Proc. Design Automation Conference, 2005, pp. 385-390.
[36] Vangelis T. Paschos, “A Survey of Approximately Optimal Solutions to Some Covering and Packing Problems,” ACM Computing Surveys, Vol. 29, Issue 2, pp. 171-209, Jun. 1997.
[37] O. Coudert, “Two-level logic minimization: an overview,” Integration, the VLSI Journal, Vol. 17, Issue 2, pp. 97-140, Oct. 1994.
[38] O. Coudert and J. C. Madre, “New Ideas for Solving Covering Problems,” in Proc. Design Automation Conference, 1995, pp. 641-646.
[39] R. P. Tewarson, Sparse Matrices (Mathematics in Science & Engineering), Academic Press, 1973.
[40] 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 Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 14, Issue 12, pp. 1496-1504, Dec. 1995.
[41] T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introductions to Algorithms, The MIT Press, 3/e, 2009.
[42] P. Camurati, A. Lioy, P. Prinetto, and M. S. Reorda, “Diagnosis Oriented Test Pattern Generation,” in Proc. European Design Automation Conference, 1990, pp. 470-474.
[43] G. Chen, S.M. Reddy, I. Pomeranz and J. Rajski, “A test pattern ordering algorithm for diagnosis with truncated fail data,” in Proc. Design Automation Conference, 2006, pp. 399-404.
[44] Y. Huang, C. Wang, M. Sharma, G. Chen and W.-T. Cheng, “The Effects of Space Compactors on Fault Diagnosis Resolution,” in Proc. North Atlantic Test Workshop, 2008, pp. 1-6.
[45] Y. R. Hong, J. D. Huang, “Reducing Fault Dictionary Size for Million-Gate Large Circuits,” ACM Transactions on Design Automation of Electronic Systems, Vol. 14, Issue 2, pp. 1-14, Mar. 2009.
[46] C.-H. Wu, K.-J. Lee and W.-C. Lien, “An efficient Diagnosis Method to Deal With Multiple Fault Pairs in a Single Circuit,” in Proc. VLSI Test Symposium, 2014, pp. 240-245.
[47] M. Alioto and G. Palumbo, “Interconnect-Aware Design of Fast Large Fan-In CMOS Multiplexers,” IEEE Transactiosn on Circuits and Systems II: Express Briefs, Vol. 54, Issue 6, pp. 484-488, Jun. 2007.
[48] S. Pilarski and T. Kameda, A Probabilistic Analysis of Test Response Compaction, IEEE Computer Society Press, 1995.
[49] W.-C. Lien, K.-J. Lee, T.-Y. Hsieh, S.-S. Chien and K. Chakrabarty, “Accumulator-Based Output Selection for Test Response Compaction,” in Proc. International Symposium on Circuits and Systems, 2012, pp. 2313-2316.
[50] J. Schat, “On the Relationship between Stuck-At Fault Coverage and Transition fault Coverage,” in Proc. Design, Automation & Test in Europe Conference, 2009, pp. 1218-1221.
[51] SynTest TurboScan ATPG, link: http://www.syntest.com/ProdDataSheet/ TurboScan_ datasheet.pdf.
[52] Synopsys TetraMAX ATPG, link: http://www.synopsys.com/Tools/ Implementation/ RTLSynthesis/Test/Pages/TetraMAXATPG.aspx.
[53] MATLAB linear programming tool, link: http://www.mathworks.com/help/optim/ linear-programming-and-mixed-integer-linear-programming.html.
[54] lp_solver, link: http://lpsolve.sourceforge.net/5.5/.
[55] IWLS 2005 Benchmarks, link: http://iwls.org/iwls2005/benchmarks.html.