淡江大學覺生紀念圖書館 (TKU Library)

系統識別號 U0002-1706200514183200
中文論文名稱 以傳播技巧為基礎來降低樣本集大小和時間成本的測試策略
英文論文名稱 A Broadcast-Based Test Scheme for Reducing Test Size and Application Time
校院名稱 淡江大學
系所名稱(中) 電機工程學系碩士班
系所名稱(英) Department of Electrical Engineering
學年度 93
學期 2
出版年 94
研究生中文姓名 張俊以
研究生英文姓名 Jun-Yi Chang
學號 692390411
學位類別 碩士
語文別 英文
口試日期 2005-06-11
論文頁數 55頁
口試委員 指導教授-饒建奇
中文關鍵字 超大型積體電路  測試  自我測試  樣本集大小  時間成本 
英文關鍵字 VLSI  Testing  BIST  Test Size  Test Application Time 
學科別分類 學科別應用科學電機及電子
中文摘要 掃描測試技術(scan based)需要測試掃描鍊(scan chain)和分析輸出響應,而時間成本(test application time)會直接影響到掃描測試技術中樣本集(test pattern)和掃描鍊的大小。現今超大型積體電路中,掃描鍊設計的複雜度會增加,所以在傳統掃描架構會需要較長的時間成本,增加時間成本意謂掃描測試技術會花費較多的成本,因此,如何在掃描測試技術中使時間成本降到最低是很重要的問題。

傳統的單一掃描鍊(single scan chain)雖只有單一掃描輸入線與單一掃描輸出線,但需要較大的測試成本。多重掃描(multiple scan chain)電路可減少時間成本的問題,它將單一掃描鍊架構分成數個較短的掃瞄鍊,使得樣本集與測試結果能夠在掃描鍊中以並行的方式傳送,達到減少時間成本的目的,但是這方法需要額外的掃描輸入線與掃描輸出線。


在本篇論文中,我們使用了平均分配(balance)和限制最長子字串的方法(constraint longest common subsequence)減少在傳播掃描架構中樣本集與時間成本的大小。我們嘗試在每個待測電路掃描鍊中,平均分配一對相同位址且有最多相似內容的正反器。

為了證明所提出的方法是有效的,我們使用ISCAS'85benchmark組合電路和ISCAS'89 benchmark序向電路做模擬,實驗結果顯示我們的方法能夠有效減少樣本集與時間成本的大小。我們只需297組樣本集即可發現ISCAS'85 benchmark組合電路所有的錯。在序向電路方面,只需1322組樣本集即可發現ISCAS'89 benchmark電路所有的錯。

英文摘要 The scan-based techniques require scan the test stimuli to scan chain and analyze the output responses. The test application time for the scan-based circuits is proportional to the product of the number of test patterns and the length of the scan chain. In a modern VLSI circuit, the increased design complexity results in longer and longer scan chains. Hence, in a typical scan structure, scan operations usually require a long test application time. The increased test application time significantly increases the cost of testing a scan-based design. Hence how to reduce test application time has become an important issue when a scan base design is used.

The single scan chains technique have the long test application time. Multiple scan chains techniques have been developed to alleviate the long test application time problem. By dividing a single serial scan chain into a number of shorter scan chains test patterns and test results can then be shift in/out of all chains in parallel to reduce the test application time. This method, however, will require a much higher number of extra I/O pins.

A approach called the broadcast scan can share the test stimulus for a single input to support multiple scan chains. By appropriately connecting the inputs of all circuits under test during ATPG process such that the generated test patterns can be broadcast to all scan chains.

In this paper we shall describe a broadcast scan architecture that can reduce the test pattern and test application time. Based on the balance and constraint longest common subsequence method. There, our method tries to balance assign pairwise similar flip-flops to the same position in each CUT scan chain.

To verify the effectiveness of the proposed method, experiments on the ISCAS’85 combinational benchmark circuits and the ISCAS’89 sequential benchmark circuits. The result show can reduce the test pattern and test application time. It is found that we only need 297 test patterns to detect all detectable faults in all five ISCAS’85 combinational circuits. For the sequential circuits, we show that with our method, 1322 test patterns are enough for the five ISCAS’89 scan-based sequential circuits.

論文目次 中文摘要 I
Abstract III
Table of Contents V
List of Figures VIII
List of Tables XI

Chapter 1 : Introduction 1
1.1 Motivation 1
1.2 Background 2

Chapter 2 : Basic Concepts 9
2.1 Scan Design 11
2.2 Scan Design Automation 15
2.3 Basic Concepts of Broadcasting Test Architecture 17
2.4 Virtual Circuits for ATPG 20
2.4.1 General Structure 20
2.4.2 Methods for Combinational Circuits 22 In-Order Mapping Method 22 Even Distribution Method 23 Nearest Signal Probability Matching Method 24 In-Order Pseudo-Exhaustive Method 25
2.4.3 Methods for Sequential Circuits 27
2.5 Hardware Configuration 28
2.5.1 Scan Architecture for Combinational Circuits 28
2.5.2 Scan Architecture for Sequential Circuits 35

Chapter 3 : Heuristic Method 37
3.1 Balance 37
3.2 Longest Common Subsequence (LCS) 38
3.2.1 Basic Concepts of and LCS 38
3.2.2 Computing the length of an constraint LCS 39
3.2.3 Balance and constraint
Longest common subsequence (BL) method 40

Chapter 4 : Design Automation for
-Broadcast based Architecture 45

Chapter 5: Experimental Results 48
5.1 Experimental Method 48
5.2 Experimental Results 48

Chapter 6 : Conclusions 52

References 53

Figure 1.1: Traditional Single Scan Architecture. 3
Figure 1.2: Traditional Multiple Scan Architecture. 4
Figure 1.3: Parallel Serial Full Scan(PSFS) Technique.5
Figure 1.4: Two Modes of Illinois Scan Architecture. 6
Figure 1.5: The Reconfigurable Shared
-Scan in Architecture. 7
Figure 2.1: Architecture of IEEE 1149.1
-standard [11]. 10
Figure 2.2: A D Flip-Flop. 12
Figure 2.3: A Single-Clock Scan Flip-Flop. 13
Figure 2.4: A Two-Clock Scan Flip-Flop. 14
Figure 2.5: A Scan Design Schematic. 14
Figure 2.6: A Flow-Chart of Automated Scan Design. 15
Figure 2.7: Traditional Single Scan
-Test Configuration. 19
Figure 2.8: Broadcasting Test Configuration. 19
Figure 2.9: Examples of Two Virtual Circuits:1 To 1
-Connection and Random Connection. 21
Figure 2.10: 1-1 In-Order Mapping Method. 23
Figure 2.11: Even Distribution Method. 23
Figure 2.12: Test Sets of Circuits A and B. 24
Figure 2.13: The Nearest Signal Probability Matching
-Method. 25
Figure 2.14: In-Order Pseudo-Exhaustive Method. 26
Figure 2.15: The First ATPG Connection Method for
-Sequential Circuits. 28

Figure 2.16: The Scan Configuration with First
-Selection Method: A Common MISR. 30
Figure 2.17: The Scan Configuration with First
-Selection Method: Individual and
-Multiple MISRs. 30
Figure 2.18: Broadcasting Test Patterns Using
-a STUMP-Like Structure. 31
Figure 2.19: The Scan Architecture of the Second
-Virtual Circuit With Different
-Connection Position.(a) Longer Routing
-Length, (b) Shorter Routing Length. 32
Figure 2.20: The Scan Chain Structure of the
-Figure 2.13. 33
Figure 2.21: The Alternative Scan Chain Structure
-of the Figure 2.13. 33
Figure 2.22: The Scan Architectures of the Fourth
-Method:(a) Ni-j+1 ≦ N1
-(b) Ni-j+1 > N1. 34
Figure 2.23: Scan Architecture for Sequential
-Circuits Using One Scan Input. 35
Figure 3.1: Balance Methods. 37
Figure 3.2: constraint Longest Common Subsequence. 37
Figure 3.3: The constraint LCS Number to
-the “Same Position”. 39
Figure 3.4: Test Sets of Circuits A and B. 40
Figure 3.5: All of the CUTs Are Even distribution. 41
Figure 3.6: Individual ATPG of all CUTs. 41
Figure 3.7: Choose The First Pin of CUT(2). 42
Figure 3.8: Compute The constraint LCS Number. 42
Figure 3.9: Find The Most constraint LCS Number. 43
Figure 3.10: Choose The Next Pin of CUT(2). 43
Figure 3.11: Choose The Next CUT. 44
Figure 3.12: BL Algorithm for Broadcast Test
-Configuration. 44
Figure 4.1: The GUI of Developed Design
-Automation Tool. 45
Figure 4.2: The Set of Test Patterns are Generated
-For The Circuit under Test Using the
-ATPG Tool Provided By SIS. 46
Figure 4.3: Open The CUT Blif File. 46
Figure 4.4: Input The Module Name. 47
Figure 4.5: Automation for Broadcast-Based
-Architecture. 47

Table 5.1: Individual ATPG Results of ISCAS’85
-Circuits. 48
Table 5.2: Experimental Results for ISCAS’85
-Circuits. 49
Table 5.3: Individual ATPG Results of ISCAS’89
-Circuits. 50
Table 5.4: Experimental Results for ISCAS’89
-Circuits. 50
參考文獻 [1] Zhang and R.D. Mcleod, “An Efficient Multiple Scan
Chain Testing Scheme” in 6th Great Lakes Symp. VLSI,
March. 1996,pp.294-297.
[2] K-J. Lee, J-J. Chen and C-H. Huang, “Using A Single
Input to Support Multiple Scan Chains,” Dig. Tech.
Papers, IEEE/ACM Int. Conf. Computer-Aided Design,
1998, pp.74-48.
[3] I. Hamzaoglu and J. H. Patel, “Reducing Test
Application Time for Full Scan Embedded Cores,” Proc.
IEEE Int. Symp. On Fault Tolerant Computing, 1999,
[4] S. Samaranayake, E. Gizdarski, N. Sitchinava, F.
Neuveux, R. Kapur, T.W. Williams, “A Recofigurable
Shared Scan-in Architecture,” Proc. VLSI Test Symp.,
2003, pp.9-14.
[5] A.R. Pandey and J.H. Patel, “An incremental algorithm
for test generation in illinois scan architecture
based designs”, in Proceedings of the Design,
Automation and Test in Europe Conference, 2002,
[6] A.R. Pandey and J.H. Patel, “Reconfiguration
Technique for Reducing Test Time and Test Data Volume
in Illinois Scan Architecture Based Design,” Proc.
VLSI Test Symp., 2002, pp.9-15.
[7] F. Brglez and H. fujiwara, “A neutral netlist of 10
combinational benchmark designs and a special
translator in Fortran,” in Proc. Int. Symp. Circuits
and Systems, June 1985, pp.663-698.
[8] F. Brglez, D.Bryan, and K. Kozminski, “Combinational
profiles of sequential benchmark circuits, in Proc.
Int. Symp. Circuits and Systems,May 1989, pp. 1929-
[9] J. S. Chang and C. S. Lin, “Test set compaction for
combinational circuits,” IEEE Trans. Computer-Aided
Design, vol. 14, Nov. 1995, pp. 1370–1378.
[10] K-J. Lee, J-J. Chen and C-H. Huang, “Broadcasting
Test Pattern to Multiple Circuits, ” in IEEE Trans.
on CAD, Dec. 1999, pp. 1793-1802.
[11] Supplement to IEEE Std. 1149.1-1990. IEEE Standard
Test Access Port and Boundary Scan Architecture.
McGraw-Hill, New-York, 1994.
[12] R. Gupta, S. Narayanan, and M. A. Breuer. “Optimal
Configuring of Multiple Scan Chains” In IEEE Trans.
On Computers, Sep.1993 ,pp. 1121-1131.
[13] S. Narayanan and M. A. Breuer. “Asynchronous
Multiple Scan Chains.” In Proc. Of VLSI Test
Symposium, 1995, pp. 270-276.
[14] Zhang and R.D. McLeod. “An Efficient Multople Scan
Chain Testing Scheme.” In Proc. Of Sixth Great Lakes
Symposium on VLSI, 1996, pp. 294-297.
[15] S. J. Jou, C.-C. Su, and Y.-T. Ting. “Decentralized
BIST for 1149.1 and 1149.5 Based Interconnects.” In
Proc. Of European Design and Test Conf., Mar. 1996,
pp. 120-125.
[16] P. Goel. An Implicit Enumeration “Algorithm to
Generate Tests for Comginational Logic Circuit.” In
IEEE Trans. On Computers, Mar. 1981.
[17] M. Abramovici and J. J. Kulikowski. “Smart and Fast:
Test generation for VLSI scan-design circuits.” In
IEEE Design and Test of Computers, Aug. 1986, pp. 43-
[18] M. J. Y. Willams and J. B. Angell, “Enhancing
Testability of Large-Scale Integrated Circuits via
Test Points and Additional Logic,” IEEE Trans. On
Computers, vol.C-22, no. 1, Jan. 1973, pp. 46-60.
[19] E. B. Eichelberger, E. Lindbloom, J. A. Waicukauski,
and T. W. Williams, “Structured Logic Testing.”
Englewood Cliffs, New Jersey: Prentice-Hall, 1991.
[20] T. W. Williams and K. Parker, “Design for
Testability – A Survery,” IEEE Trans. On Computers,
vol. C-31, no. 1, Jan. 1982, pp. 2-15.
[21] D.K. Bhavsar, “Design for Test Calculus: An
Algorithm for DFT Rules Checking,” in proc. of the
20th Design Automation Conf., June 1983, pp. 300-307.
[22] H. C. Godoy, C. B.Franklin, and P. Bottorff,
“Automatic Checking of logic design structures for
Compliance with Testability Ground Rules,” in Proc.
of the 14 th Design Automation Conf., June 1977, pp.
[23] V. D. Agrawal, S. K. Jain, and D. M. Singer,
“Automation in Design for Testability,” in Proc. of
the Custom Integrated Circuits Conf., May 1984,
[24] A. E. Dunlop, V. D. Agrawal, D. N. Deutsch, M. F.
Jukl, P. Kozak, and M. Wiesel,”Chip Layout
Optimization Using Critical Path Weighting,” in
Proc. of the 21st Design Automation Conf., June 1984,
pp. 133-136.
[25] I. Bayraktaroglu and A. Orailoglu, “Test volume and
application reduction through scan chain
concealment,” in Proc. ACM/IEEE Design Automation
Conf., 2001, pp. 151–155.
[26] A. Jas, B. Pouya, and N. A. Touba, “Virtual scan
chains: A means for reducing scan length in cores,”
in Proc. IEEE VLSI Test Symp., 2002, pp. 73–78.
[27] B. Krishnamurthy and S. B. Akers. “On the complexity
of estimating the size of a test set,” IEEE Trans.
on Computers, Aug. 1984,pp.750-753.
[28] P. H. Bardell and W.H. McAnney. “Self-Testing of
Multichip Logic Modules,” In Proc. of Int’l. Test
Conf., Nov.1982, pp. 200-204.
[29] P. H. Bardell and W.H. McAnney. “Parallel
Pseudorandom Sequences for Built-In Test,” In Proc.
of Int’l. Test Conf., Oct.1984, pp. 302-308.
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2007-07-12公開。
  • 同意授權瀏覽/列印電子全文服務,於2007-07-12起公開。

  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信