掃描測試技術(scan based)需要測試掃描鍊(scan chain)和分析輸出響應，而時間成本(test application time)會直接影響到掃描測試技術中樣本集(test pattern)和掃描鍊的大小。現今超大型積體電路中，掃描鍊設計的複雜度會增加，所以在傳統掃描架構會需要較長的時間成本，增加時間成本意謂掃描測試技術會花費較多的成本，因此，如何在掃描測試技術中使時間成本降到最低是很重要的問題。

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

    有一種掃描架構稱之為傳播(broadcast)掃描，它能夠只使用單一條輸入資料線提供測試向量給多條掃描線電路。在執行自動樣本集產生(ATPG)的過程中，藉由適當的連接多組待測電路輸入線，使得所產生的測試向量能夠在實際進行測試時以傳播的方式傳送測試向量給所有的掃描鍊。

    在本篇論文中，我們使用了平均分配(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
2.4.2.1 In-Order Mapping Method                      22
2.4.2.2 Even Distribution Method                     23
2.4.2.3 Nearest Signal Probability Matching Method   24
2.4.2.4 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, 
    pp.260-267.
[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, 
    pp.369–375.
[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-
    1934.
[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-
     54.
[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. 
     469-478.
[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, 
     pp.159-163.
[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.