在系統單晶片（SoC）越來越普及的時代，要提升系統單晶片的可靠度，往往需要藉由掃描測試技術來完成。但是掃描測試技術的測試成本往往是牽動整體測試成本最大的瓶頸所在，其中掃描測試技術成本又可分為測試時間以及測試資料量，因此如何有效降低掃描測試技術的測試時間以及測試資料量就是當前系統單晶片測試最重要的課題。另外，由於系統單晶片的開發成本很高，因此我們往往希望能夠在完成系統單晶片的測試之後還能夠進一步能夠進行系統單晶片的診斷，因此如何有效保留完整的系統單晶片測試響應亦相當重要。

　　在本篇論文中，我們首先提出一個改良式輸出腳位壓縮技術，使得我們可以找出電路中真正的偶感應錯誤，進而可以減少輸出腳位壓縮的縮減元件數量。再者，我們另外提出一個測試響應壓縮的測試流程，其中包括一個適用於壓縮測試響應資料量的編碼方式，稱之為「適應性頻率計數編碼」。透過這個所提出的流程，我們可以大幅壓縮整體測試響應的資料量，以減低在自動測試機台上的記憶體使用需求。另外我們提出「演進式掃描測試架構」配合前述的編碼方式，可以大幅降低測試時間以及測試資料量，最重要的是完整的測試響應資料可以被無失真的保留下來以便後續可以進行系統單晶片的診斷分析工作。

　　綜合以上所述，我們可以完成降低系統單晶片測試響應資料量、測試時間以及完整保存測試響應資料等三項目地。因此，透過我們所提出的輸出壓縮技術，我們可以完成大幅降低系統單晶片的整體測試成本的目標。

　　With the popularization in SOC designs, it is highly demanded to increase the SOC reliability. The conventional scan architecture is one of the most popular methods for this purpose. However, One of the bottlenecks of testing a system-on-a-chip (SoC) is the long test times arisen from the limited test data bandwidth between the tester and the SOC. Hence, the data compression techniques that reduce the test data volume have received much attention recently.

　　In this thesis, we present a test response compression approach which can greatly reduce the volume of test response, consequently, the necessary memory size of a tester and the time of transferring data from each core to output in a SoC during manufacturing test. The presented method is based on the use of a proposed encoding/decoding scheme, named as Adaptive Frequency Counted (AFC) code, for test response compression. We show that a careful sorting of test responses leads to significant improvement in the compression rate of the presented scheme. We also show that sorting all sequences of test response to achieve lowest compression rate is equivalent to the Hamiltonian path problem, a well-known NP-complete problem. A heuristic algorithm based on greedy, complete graph and branch-and-bound techniques are presented to obtain the approximately optimal sorted sequences in reasonable computational time for huge volume of test response for SoC designs. Moreover, we also propose new test architecture named Evolutional Test Architecture to reduce the test volume and test time greatly simultaneously. Also we can reserve the total test response with zero-aliasing for the SOC diagnosis. Experimental results for the ISCAS-85 and -89 benchmarks and some representative circuits from industry show that the proposed method generally provides higher compression than the previously proposed test data compression approach based on adaptive run-length code.

　　Experimental results show that the three objectives, namely reducing test time, test volume and reserving faulty test response are achieved. By our proposed output reduction and data compression techniques, the total SOC test cost can be greatly reduced.

[1] I. Hamzaoglu and J. H. Patel, “Reducing Test Application Time for Built-in-Self-test Test Pattern Generators,” in Proc. VLSI Test Symposium, pp. 369-375, 2000.

[2] R. S. Fetherston, I. P. Shaik, and S. C. Ma, “Testability Features of AMD-K6TM Microprocessor,” in Proc. International Test Conference, pp. 406-413, 1997.

[3] C. K. Yang and K. J. Lee, “Advanced scan architecture for test time and test volume reductions”, NCKU master thesis, 2002.

[4] R. Gupta, S. Narayanan, and M. A. Breuer, “Optimal Configuring of Multiple Scan Chains,” IEEE Trans. on Computers, vol. 42, no. 9, pp. 1121-1131, Sep. 1993.

[5] C. A. Chen and S. K. Gupta, “Efficient BIST TPG Design and Test Set Compaction via Input Reduction,” IEEE. Trans. on Computer-Aided Design, vol. 17, no. 8, pp. 692-705, Aug. 1998.

[6] I. Hamzaoglu and J. H. Patel, “Reducing Test Application Time for Built-in-Self-test Test Pattern Generators,” in Proc. VLSI Test Symposium, 2000, pp. 369-375.

[7] K. J. Lee, J. J. Chen, and C. H. Huang, “Broadcasting Test Patterns to Multiple Circuits,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 1793-1802, Dec. 1999.

[8] Ilker Hamzaoglu and Janak H. Patel, “Reducing Test Application Time for Full Scan Embedded Cores,” in Proc. Fault-Tolerant Computing, 1999, pp. 260-267.

[9] Chauchin Su and Kychin Hwang, “A Serial Scan
Test Vector Compression Methodology,” In Proc. International Test Conference, 1993, pp. 981-988.

[10] S. J. Wang and S. N. Chiou, “Generating Efficient Tests for Continuous Scan,” In Proc. Design Automation Conference, Jun. 2001, pp. 162-165.

[11] I. Pomeranz, L. N. Reddy, and S. M. Reddy, “COMPACTEST: A Method to generate Compact Test Sets for Combinational Circuits,” IEEE Trans. on CAD, pp. 1040-1049, Jul. 1993.

[12] B. Koenemann, “LFSR-coded Test Patterns for Scan Designs,” in Proc. European Test Conference, 1991, pp. 237-242.

[13] S. Hellebrand, S. Tarnick, J. Rajski, and B. Courtois, “Generaten of Vector Patterns Through Reseeding of Multiple-Polynomial Linear Feedback Shift Registers,” in Proc. International Test Conference, 1992, pp. 120-129.

[14] S.Venkataraman, J. Rajski, S. Hellebrand, and S. Tarnick, “An Efficient BIST Scheme Based on Reseeding of Multiple Polynomial Linear Feedback Shift Registers,” in Proc. IEEE/ACM International Conference Computer-Aided Design, 1993, pp. 572-577.

[15] S. Hellebrand, J. Rajski, S. Tarnick, S.Venkataraman, and B. Courtois, “Built-In Test for Circuits with Scan Based on Reseeding of Multiple-Polynomial Linear Feedback Shift Registers,” IEEE Trans. on Computers, vol. 44, no. 2, pp. 223-233, Feb. 1995.

[16] N. Zacharia, J. Rajski, and J. Tyszer, “Decompression of Test Data Using Variable-Length Seed LFSRs,” in Proc. VLSI Test Symposium, 1995, pp. 426-433.

[17] N. Zacharia, J. Rajski, J. Tyszer, and J. A. Waicukauski, “Two-Dimensional Test Data Decompressor for Multiple Scan Designs,” in Proc. International Test Conference, 1996, pp. 186-194.

[18] S. Hellebrand, H. G. Liang, and H. J. Wunderlich, “A Mixed Mode BIST Scheme Based on Reseeding of Folding Counters,” in Proc. International Test Conference, 2000, pp. 778-784.

[19] H. G. Liang, S. Hellebrand, and H. J. Wunderlich, “Two-Dimensional Test Data Compression for Scan-Based Deterministic BIST,” in Proc. International Test Conference, 2001, pp. 894-902.

[20] J. P. Hayes, “Transition Count Testing of Combinational Logic Circuits,” IEEE Trans. on Comput., vol. c-25, pp. 613-620, 1976.

[21] B. Konemann, J. Mucha, and G. Zwiehoff, “Built-In Logic Block Observation Techniques,” in Proc. IEEE International Test Conference, 1979, pp. 37-41.

[22] J. Savir, “Syndrome-Testable Design of Combinational Circuits,” IEEE Trans. on Comput., vol. c-29, pp. 442-451, 1980.

[23] A. K. Susskind, “Testing by Verifying Walsh Coefficients,” IEEE Trans. on Comput., vol. c-32, pp. 198-201, 1983.

[24] K. Chakrabarty, and J. P. Hayes, “Zero-Aliasing Space Compaction of Test Response Using Multiple Parity Signatures,” IEEE Trans. on VLSI Systems, vol. 6, pp. 309-313, 1998.

[25] S. R. Das, E. M. Petriu, T. F. Barakat, M. H. Assaf, and A. R. Nayak, “Space Compaction Under Generalized Mergeability,” IEEE Trans. on Instrumentation and Measurement, vol. 47, pp. 1283-1293, 1998.

[26] W. B. Jone, “DSC – A SPACE COMPRESSION METHOD,” IEEE International Symposium on Circuits and Systems, vol. 4, pp. 2756 -2759, 1990.

[27] A. Dmitriev, M. Gossel, K. Chakrabarty, “Robust Space Compaction of Test Responses,” in Proc. Asian Test Symposium, 2002, pp. 254-259.

[28] Bhargab B. Bhattacharya, A. Dmitriev, M. Gössel, and K. Chakrabarty, “Synthesis of Single-Output Space Compactors for Scan-Based Sequential Circuits,” IEEE Trans. on Computer-Aided Design of Integrated Circuits and
Systems, vol. 21, no. 10, pp. 1171-1179, 2002.

[29] V. Iyengar, K. Chakrabarty and B. T. Murray, “Built-in self testing of sequential circuits using precomputed test sets”, in Proc. VLSI Test Symposium, pp. 418-423, 1998.

[30] V. Iyengar, K. Chakrabarty and B. T. Murray, “Deterministic built-in pattern generaten for sequential circuits”, Journal of Electronic Testing: Theory and Applications, vol. 15, pp. 97-114, 1999.

[31] A. Jas, J. Ghosh-Dastidar and N. A. Touba, “Scan vector compression/decompression using statistical coding”, in Proc. IEEE VLSI Test Symposium, pp. 114-120, 1999.

[32] I. Hamzaoglu and J. H. Patel, “Test set compaction algorithms for combinational circuits”, in Proc. International Test Conference on CAD, pp. 283-289, 1998.

[33] S. Kajihara, I. Pomeranz, K. Kinoshita and S. M. Reddy, “On compacting test sets by addition and removal of vectors”, in Proc. VLSI Test Symposium, pp. 202-207, 1994.

[34] S. Kajihara, et. al., “Test data compression using don’t-care identification and statistical encoding”, in Asian Test Symposium, 2002.

[35] A. Jas and N. A. Touba, “Test vector decompression via cyclical scan chains and tts application to testing core-based Designs”, in International Test Conference, 1998.

[36] A. Chandra and K. Chakrabarty, “Test data compression for system-on-a-chip using Golomb codes”, in Proc. VLSI Test Symposium, 2000.

[37] A. Chandra and K. Chakrabarty, “System-on-a-chip test data compression and decompression architectures based on Golomb codes”, in IEEE transactions on CAD, pp. 355-368, 2001.

[38] A. Chandra and K. Chakrabarty, “Low-power scan testing and test data compression for system-on-a-chip”, in IEEE transactions on CAD, pp. 597-604, 2002.

[39] A. Chandra and K. Chakrabarty, “Frequency-directed run-length (FDR) codes with application to system-on-a-chip test data compression”, in Proc. IEEE VLSI Test Symposium, pp. 42-47, 2001.

[40] A. Chandra and K. Chakrabarty, “A united approach to reduce SOC test data volume, scan power and testing time”, in IEEE transactions on CAD, pp. 352-362, 2003.

[41] S. Kajihara, Y. Doi, L. Li and K. Chakrabarty, “On combining pinpoint test set relaxation and run-length codes for reducing test data volume”, in Proc. International Conference on Computer Design, pp. 355-368, 2003.