近代的設計與封裝技術快速發展，已使得單晶片系(System-On-a-Chip，SoC)成為一個趨勢，由於它是將整個系統所能執行的功能都由一矽晶片來實現，以至於要從外部來測試系統有沒有發生錯誤和缺陷變的非常困難了。所以大部份的設計者在設計晶片的過程中就會將測試的電路也一併加入，也就是所謂的可測試設計(Design for Testability，DFT)。內建自我測試(Built-In Self-Test，BIST)是屬於可測試設計(DFT)的其中一種方法。在BIST的架構裡包含了測試結果壓縮器(response components)，信號分析器(signature analyzer)，測試向量產生器(test pattern generator，TPG), 在此我們所使用的是線性回溯移位暫存器(Linear Feedback Shift Register，LFSR)，來當作測試向量產生器。

  在BIST測試中，由於測試向量是由假性隨機測試向量產生器(pseudo-random pattern generator)所產生的，所以需要比較長的時間以及較多的功率消耗，另外，亦無法得到較高的錯誤涵蓋率(Fault Coverage)，而且一些無效的測試向量(useless pattern)也會使得測試時間(test time)變長，因此為了縮短測試長度(test length)，亦即測試時間(test time)降低以及測試期間的功率消耗，我們修改了掃描電路(scan chain)架構，使其可以依照測試需求而縮短長度，另外我們也使用ATPG產生的關鍵測試向量來做掃描電路架構的更改，進而改進整理測試長度以及錯誤涵蓋率。

  在本篇論文中，我們提出一個依照傳統的LBIST Controller架構，所修改的最新的架構，它可以降低測試應用時間(test application time)以及測試功率的消耗。我們使用ATPG產生的測試向量，此測試向量包含未確定的位元(unspecified bit)，此位元可以填入0或1。經過我們提出的演算法後，我們會將測試向量分成數個測試組合排程(section schemes)，演算法的部分我們會在第三章節詳述。然後將此結果對應至我們提出的硬體架構，當Section Counter數值大於零的時候，掃描電路會縮短長度，測試向量直接經由多工器跳過不需要輸入測試向量的掃描電路，此時這些掃描電路的數值是不變的，我們稱為固定的掃描電路(Fixed Group)，硬體架構的部分我們會在第二章節詳述。因為測試元件(scan cell)的數值是不變的，因此也沒有功率消耗的問題，因此我們提出的架構可以節省功率消耗以及測試應用時間。我們使用ISCAS’89 benchmarks來模擬我們的結果，整體來說，節省了大約20%~60%的測試功率消耗以及50%~80%的測試應用時間，詳細的模擬結果會在最後一個章節詳述。

Modern design and package technologies make external testing increasingly difficult and the built-in self-test (BIST) has emerged as a promising solution to the VLSI testing problem. BIST is a design for testability methodology aimed at detecting faulty components in a system by incorporating test logic on-chip. The main components of a BIST scheme are the test pattern generator (TPG), the response compactor, and the signature analyzer. The test generator applies a sequence of patterns to the circuit under test (CUT), the responses are compacted into a signature by the response compactor, and the signature is compared to a fault-free reference value.

  During built-in self-test (BIST), the set of patterns generated by a pseudo-random pattern generator may use longer test time and more power consumption, then it would not provide sufficiently high fault coverage and many patterns were undetected faults (useless patterns). In order to reduce the test time and power consumption in testing, we modify the scan chain architecture and use critical patterns from ATPG to improve test length and achieve high fault coverage.

  In this paper, we proposed a novel hardware architecture base on “LBIST Controller” to reduce test application time and test power consumption. A given test cubes with unspecified bits that generated by a sequential automatic test pattern generator (ATPG). Using the proposed algorithm in chapter 4.3 can group test cubes to several section schemes, then mapping to the proposed hardware architecture in chapter 4.1 and chapter 4.2. While “Section Counter” is more than zero, scan in could go through MUX and bypass the flip-flops in “Fixed Group”. And we can save power consumption and test application time. According to our simulation results, we reduce about 20%~60% power consumption and 50%~80% test application time in some ISCAS’89 benchmarks.

中文摘要………………………………………………………………I
英文摘要………………………………………………………………III
Table of Contents …………………………………………………V

List of Figures ……………………………………………………VII

List of Tables …………………………………………………… IX

	
Chapter 1 INTRODUCTION ………………………………………… 1
	
1-1 Motivation …………………………………………………… 4
1-2 Thesis Overview ………………………………………………5
	
Chapter 2 BASIC CONCEPTS ……………………………………… 6
	
2-1 Faults …………………………………………………………………………6
2.1.1 Circuit Defects and Faults …………………………… 7
2.1.2 Fault Detection ……………………………………………10
2-2 Fault Simulation …………………………………………… 14
2.2.1 Serial Fault Simulation …………………………………16
2.2.2 Parallel Fault Simulation ………………………………17
2-3 Seed Calculation …………………………………………… 19
2-4 Built-In Self Test ………………………………………… 21
2.4.1 BIST Pattern Generation …………………………………21
2.4.2 Test Pattern Generation for BIST …………………… 23
2.4.3 Test-Per-Clock BIST Systems ……………………………27
2.4.4 Test-Per-Scan BIST Systems …………………………… 28
	
Chapter 3 PREVIOUS BIST METHODOLOGIES ………………………32
	
3-1 Transformed Patterns For BIST ……………………………32
3-2 Circuit Partitioning for BIST ……………………………36
3-3 Built-In Reseeding For BIST ………………………………38
3-4 Modifying-Bit Architecture ……………………………… 40
3-5 Multiple Polynomial LFSR Architecture …………………42
	
Chapter 4 PROPOSED HARDWARE ARCHITECTURE ………………… 43
	
4-1 Controllable Scan Chain ……………………………………44
4-2 MPLFSR Architecture …………………………………………46
4-3 The Proposed Algorithm …………………………………… 47
4.3.1 Flow Chart ……………………………………………………48
4.3.2 Algorithm 1: Group scan cells …………………………49
4.3.3 Algorithm 2: Partition test cubes into section schemes ………………………………………………………………50
4.3.4 Algorithm 3: Combine section schemes ……………… 51
4.3.5 Example of Algorithm …………………………………… 53
	
Chapter 5 SIMULATION RESULTS ………………………………… 56
	
Chapter 6 CONCLUSIONS ……………………………………………60
	
References ………………………………………………………… 61

LIST OF FIGURES
Figure 1.1     Testing of embedded cores…………………	1
Figure 1.2     Architecture of the BIST …………………	2
Figure 1.3     Principle of testing ………………………	4
Figure 2.1     A circuit of fault-free and faulty ……	8
Figure 2.2     An example of single stuck-at fault model …8
Figure 2.3     A three-input NAND gate with, (a) no faults (b) x1 with ans-a-0 fault, and (c) x1 with an s-a-1 fault ………………………………………………………………………	9
Figure 2.4     An example of a single stuck-at fault …11
Figure 2.5     A test for x1 s-a-0 detects a different between the faulty circuit and the fault-free circuit …12
Figure 2.6     Calculated the fault coverage ………13
Figure 2.7     An example of parallel fault simulation …18
Figure 2.8     A 4-stage LFSR connected to a chain ……19
Figure 2.9     The remaining equations of the scan flip-flops ………………………………………………………………	20
Figure 2.10    The matrix which represents the equations 20
Figure 2.11    Exhaustive pattern generator ………………24
Figure 2.12    Backtracing for pseudo-exhaustive testing25
Figure 2.13    Standard linear feedback shift register…26
Figure 2.14    Test-Per-Clock scheme ………………………28
Figure 2.15    Test-Per-Scan scheme ………………………	29
Figure 2.16    STUMPS test-per-scan testing system ……30
	
Figure 3.1     Example of a Rectangle in the B-Matrix and its Corresponding Bit-Fixing Logic ……………………………33
Figure 3.2     Cube Mapping with Source Cube and Image cube ……………………………………34
Figure 3.3     Block Diagram for Generating Transformed patterns ……………35
Figure 3.4     Output cones ……………………………………………………37
Figure 3.5     General and independent of the underlying BIST scheme ………38
Figure 3.6     4-stage LFSR with reseeding circuit ……………………………39
Figure 3.7     The architecture of modifying-bit ………………………………	40
Figure 3.8     Obtaining the useful pattern ……………………………………	41
Figure 3.9     Multiple Polynomial LFSR Architecture ………………………	42
	
Figure 4.1     System View of BIST Environment ………………………	43
Figure 4.2     Controllable Scan Cells Aarchitectures …45
Figure 4.3     Multiple Polynomial and Changeability LFSR Architecture …	46
Figure 4.4     Overview of the Proposed Algorithm …………………………	48
Figure 4.5     Example of the proposed algorithm ……………………………	55

Table 2.1     The system of test-per-clock is different from system of the test-per-scan ………………………………………………………	31
	
Table 4.1     Group scan cells algorithm ………………………………………50
Table 4.2     Partition test cubes into section schemes algorithm ………………51
Table 4.3     Combine section schemes algorithm ………………………………53
	
Table 5.1     Statistics of ISCAS 89 benchmark ………………………………57
Table 5.2     Summary result of Hardware Design Policy ………………………	58
Table 5.3     Summary result of Compare with Gave Test Cubes ………………	59

















LIST OF TABLES
Table 2.1     The system of test-per-clock is different from system of the test-per-scan ……………………………………………………….	31
	
Table 4.1     Group scan cells algorithm ………………………………………..	50
Table 4.2     Partition test cubes into section schemes algorithm ………………	51
Table 4.3     Combine section schemes algorithm ………………………………	52
	
Table 5.1     Statistics of ISCAS 89 benchmark ………………………………...	56
Table 5.2     Summary result of Hardware Design Policy ………………………	57
Table 5.3     Summary result of Compare with Gave Test Cubes ………………	58

[1] Al-Alyamani A., and E. J. McCluskey, “Built-In Reseeding for Serial BIST,” In Proc. of VLSI Test Symopsium, Apr. 2003.

[2] Al-Alyamani A., S. Mitra, and E.J. McCluskey, “BIST Reseeding with Very Few Seeds,” In Proc. of VLSI Test Symopsium, Apr. 2003.

[3] Chiang, C.-H., and S.K. Gupta, “Random Pattern Testable Logic Synthesis,” In Proc. of International Conference on Computer-Aided Design (ICCAD), 1994, pp. 125-128.

[4] Eichelberger, E. B., and E. Lindbloom, “Random-Pattern Coverage Enhancement and Diagnosis for LSSD Logic Self-Test,” IBM Journal of Research and Development, Vol. 27, No. 3, May. 1983, pp. 265-272.

[5] Eichelberger, E. B., and E. Lindbloom, F. Motica, and J. Waicukauski, “Weighted Random Pattern Testing Apparatus and Method,” US Patent 4,801,870, Jan. 89.

[6] Fagot, C., O. Gascuel, P. Girard and C. Landrault, “On Calculating Efficient LFSR Seeds for Built-In Self Test,” In Proc. of European Test Workshop, 1999, pp. 7-14.

[7] Hellebrand, S., B. Reeb, S. Tarnick, and H.-J.Wunderlich, “Pattern Generation for a Deterministic BIST Scheme,” In Proc. of International Conference on Computer-Aided Design (ICCAD, 1995), pp 88-94.

[8] M. Lempel, S.K. Gupta and M.A. Breuer, “Test Embedding with Discrete Logarithms,” IEEE VLSI Test Symp., 1994, pp. 74-78.

[9] McCluskey, E.J., “Built-In Self-Test Techniques,” IEEE Des. & Test of Comp., Apr. 85, pp. 21-28.

[10] Rajski, J., J. Tyszer and N. Zacharia, “Test Data Decompression for Multiple Scan Designs with Boundary Scan,” IEEE Transactions on Computers, Vol. 47, No. 11, Nov. 1998, pp.1188-1200.

[11] Touba, N.A., and E.J. McCluskey, “Automated Logic Synthesis of Random Pattern Testable Circuits,” In Proc. of International Test Conference, 1994, pp. 174-183.

[12] Touba, N.A., and E.J. McCluskey, “Synthesis of Mapping Logic for Generating Transformed Pseudo-Random Patterns for BIST,” In Proc. of International Test Conference, 1995, pp. 674-682.

[13] Touba, N.A., and E.J. McCluskey,   “Test Point Insertion Based on Path Tracing,” In Proc. of VLSI Test Symposium, 1996, pp. 2-8.

[14] Touba, N. and E.J. McCluskey, “Altering Bit Sequence to Contain Predetermined Patterns,” US Patent 6,061,818, May. 2000.

[15] Krishna, C. V., A. Jas, and N. Touba, “Test Vector Encoding Using Partial LFSR Reseeding,” In Proc. of International Test Conference, 2001, pp. 885-893.

[16] V. D. Agrawal, R. Dauer, S. K. Jain, H. A. Kalvonjian, C. F. Lee, K. B. McGregor, M. A. Pashan, C. E. Stroud, and L.-C. Suen, “BIST at Your Gingertips Handbook,” AT&T, June 1987

[17] V. D. Agrawal and H. Kato, “Fault Sampling Revisted,” IEEE Design and Test of Computers, vol. 7, no. 4, Aug. 1990, pp. 32-35.

[18] V. D. Agrawal, C. R. Kime, and K. K. Saluja, “A Tutorial on Built-In Self-Test, Part 1: Principles,” IEEE Design and Test of Computers, vol. 10, no. 1, Mar. 1993, pp. 73-82.

[19] P. H. Bardell and W. H. McAnney, “Self-Testing of Multichip Logic Modules,” In Proc. of the International Test Conf., Nov. 1982, pp. 200-204.

[20] P. H. Bardell, W. H. McAnney, and J. Savir, “Built-In Test for VLSI: Pseudorandom Techniques,” New York: John Wiley & Sons, Inc., 1987

[21] Touba, N.A., and E.J. McCluskey, “Transformed Pseudo-Random Patterns for BIST,” In Proc. of VLSI Test Symposium, 1995, pp. 410-416.

[22] H.-J. Wunderlich, G. Kiefer: “Bit-Flipping BIST,” In Proc. of the International Test Conf. on Computer-Aided Design, 1996, pp. 337-343.

[23] N. A. Touba, E. J. McCluskey: “Altering a pseudo-random bit sequence for scan-based BIST,” In Proc. of the International Test Conf., 1996, pp. 167-175.

[24] B. Koenemann, J. Mucha, and G. Zwiehoff, “Built-In Test for Complex Digital Integrated Circuits,” IEEE Journal of Solid-State Circuits, vol. SC-15, no. 3, June 1980, pp.315-318.

[25] E. J. McCluskey, “Verification Testing – A Pseudo-Exhaustive Test Technique,” IEEE Trans. on Computers, vol. C-33, no. 6, June 1984, pp. 541-546.

[26] C. Dufaza and G. Cambon, “LFSR-Based Deterministic and Pseudo-random Test Pattern Generator Structures,” In Proc. of the European Test Conf., Apr. 1991, pp. 27-34.

[27] Michael L. Bushnell, and Vishwani D. Agrawal, “Essentials of Electronic Testing For Digital, Memory and Mixed-Signal VLSI Circuit”, Kluwer Academic, 2000.

[28] J. C. Rau, T. W. Yang and Y-F Ho, “Built-In Reseeding with Modifying Technique for BIST,” WSEAS international Conference on CIRCUITS, 2004.

[29] Yinhe Han, Yu Hu, Huawei Li, Xiaowei Li, and Anshuman Chandra, “Rapid and Energy-Efficient Testing for Embedded Cores”, Asian Test Symposium (ATS), 2004.

[30] Nan-Cheng Lai, Sying-Jyan Wang, and Yu-Hsuan Fu, “Low Power BIST with Smoother and Scan-Chain Recoder”, Asian Test Symposium (ATS), 2004.