1.引言

　　隨著電子技術的飛速發展，集成電路的規模不斷擴大，而引腳數卻有一定的限制，許多電路被封裝在芯片內部，外部可達到的測試點、原始輸入、原始輸出所占的比例越來越少，導致集成電路的測試和故障診斷越來越困難。故障診斷中最重要的是要找到故障的測試矢量，即測試生成。集成電路的測試生成問題是數學上公認的難題——NP完全問題，在過去幾年中，國內外的一些學者雖然提出了許多新的測試生成算法，但是到目前為止還沒有一種算法適用于所有的電路，集成電路的測試生成問題己經嚴重地影響了微電子技術的發展。

　　2.集成電路測試生成算法的分類

　　(1)按照被測電路來分可以分為組合電路測試生成算法和時序電路測試生成算法兩類。組合電路測試生成算法的研究對象是組合電路，時序電路測試生成的研究對象是時序電路。

　　(2)按照獲取測試矢量集的方法來分可以分為確定性測試生成算法和非確定性測試生成算法。非確定性測試生成主要是偽隨機測試和加權隨機測試算法。確定性測試生成算法是通過算法確定出測試矢量或測試序列。

　　(3)按照故障模型來分可以分為高級測試生成算法和低級測試生成算法兩大類。高級測試生成算法的故障覆蓋率一般不如低級測試生成算法的高，但是測試時間要比低級的測試生成時間少。

　　(4)按照算法采用的技術或理論來分可以分為層次式的測試生成算法、符號化的測試生成算法、基于遺傳算法的測試生成算法、啟發式的測試生成算法等。層次式的測試生成算法將電路的無故障部分用功能塊表示，有故障的部分用門電路表示;符號化的測試生成算法基于二進制判決圖(BBD);基于遺傳算法的測試生成算法通過確定能量函數的最小值點求得測試矢量;啟發式的測試生成算法使用一些啟發式的技術。

　　(5)按照算法給定的條件來分可以分為面向故障的測試生成算法和面向測試的測試生成算法。面向故障的測試生成算法從給定的目標出發，尋找目標故障的測試矢量或測試序列;面向測試的測試生成算法從輸入激勵出發，尋找它能測試的故障。

　　(6)按照算法的特征來分可以分為基于結構的測試生成算法、基于仿真的測試生成算法等。基于結構的算法主要利用電路的結構信息;基于仿真的測試生成算法需要邏輯仿真器作為輔助工具。

　　3.電路測試生成算法的發展和現狀

　　(1)路徑敏化法。組合邏輯電路是數字電路測試的研究基礎，1959年Eldred提出第一篇關于組合電路的測試方法，但是該方法不能解決兩級以上組合電路的故障測試問題，是一種比較簡單的測試生成算法。隨后D.B.Armstrong根據Eldred的基本思想提出了一維通路敏化的方法，即路徑敏化法，其主要思想是：從故障源處到原始輸出之間尋找一條路徑，這條路徑就稱為敏化路徑，沿著這條路經，故障效應可從源處傳播到原始輸出，也就是故障效應可觀。

　　(2)布爾差分法。布爾差分法由1968年seners等人提出，它將電路描述為數學表達式，從而可進行嚴密的數學推導，因此有較高的理論價值。在布爾差分法的發展中具有代表性的是主路徑法，主路徑法將通路敏化的概念引入到布爾差分算法中，提高了布爾差分法的效率。近年來發展起來的二元判定圖(BDD)測試生成方法，也利用了布爾差分法的原理。布爾差分法的優點是可以求得給定故障的全部測試，但是對復雜性較高的電路，用它進行測試生成時需要做大量的布爾差分運算，而在計算機上對這些運算的處理是一件困難的工作。

　　(3)D算法。Roth等人于1966年提出了基于集合理論的多路徑算法——D算法，主要思想是同時敏化從故障源到電路輸出的所有全部可能的通路，它克服了一維通路敏化法的局限，采用多維敏化的思想同時敏化從故障位置到電路的所有輸出端的全部通路，只要所考慮的故障可測，用D算法就一定能求得故障的測試矢量。D算法是第一個建立在嚴格理論基礎上的組合電路測試生成算法，它具有算法上的完備性，且便于在計算機上實現，是比較成功和目前應用較廣的測試生成算法之一。D算法在進行測試生成時把大量時間花費在對許多不同路徑的試探上，在組合電路的規模較大時，用該算法計算復雜，效率不高。

　　(4) PODEM算法。1981年Goel對D算法進行改進提出了PODEM算法，該算法思路是：對激活的故障向后追蹤到原始輸入，搜索所有可能的原輸入賦值，只要找到一符合要求的即可作為測試圖形，算法即結束。這種算法是一種分支限界的隱式枚舉算法，它吸收了窮舉法的優點，采用逐個地給原始輸入賦值的辦法為給定故障生成測試，從而避免了許多盲目的試探，減少了D算法中回退與判決的次數。PODEM算法比D算法的測試生成速度快若干倍，并顯著地減少了回退與判決的次數，但仍然存在回退的問題。

　　(5)FAN算法及其擴充和發展。為加速測試生成，Fujiwara等人于1983年提出了FAN算法。該算法在減少回退次數，降低每一次的回退時間以及對扇出點都做了細致處理。FAN算法的運算速度快于PODEM算法，不僅回退次數少，而且故障覆蓋率較高。FAN算法豐富和發展了測試生成算法的基本思想，近年來出現的一些較為有效的方法，大都基于它的思想，是它的擴充和發展。在FAN算法的發展中，有代表性的一種算法是Michael等人于1987年提出的SOCRATES算法。這種算法將組合電路的測試生成問題描述成一個對判定樹的搜索過程，改進了FAN算法的蘊涵過程，使蘊涵更加徹底，用控制的概念解釋唯一敏化現象，使算法在故障傳播時對更多的情況賦予確定值，擴展了多路回退策略。

　　(6)FASTEST算法。FASTEST算法是基于PODEM算法的時序電路ATPG算法。FASTEST把測試生成問題當單個問題處理，選擇全面的優化決策，所有處理采用時間向前處理，因此不會在確認不可到達的狀態上浪費時間，另外測試長度保持最小。FASTEST算法的主要優點是可以快速地確認不能達到的狀態，缺點是需要對時序單元的總數和激活故障的時序單元有較準的估計，如果估不正確，會大大浪費時間和存儲資源。

　　(7)CONTEST算法。CONTEST算法是對選定的初始矢量在模擬結果的基礎上計算成本函數。CONTEST算法對組合及時序電路都有效，可以對一組故障、單個故障生成測試矢量，也可生成電路的初始時序，但三方面應用時成本函數不同。用CONTEST方法進行測試生成要優于其他方法，但有時會生成較多的測試矢量，因為試探時會選擇相鄰的矢量。CONTEST的另一個應用是尋找初始化矢量序列，使得電路從未知狀態轉到已知狀態。

　　4.結束語

　　隨著微電子技術的飛速發展，有些傳統的算法已經不再適用，有些方法還存在不足，探索新算法，改進己有算法，是測試生成算法研究的重點。

　　參考文獻

　　[1] 于云華，石寅.數字集成電路故障測試策略和技術的研究進展.電路與系統學報，2004，9(3):83一91

　　[2] 向東.數字系統測試及可測性設計.科學出版社，1997:2一11

　　[3] 劉曉東.集成電路測試生成算法的研究.哈爾濱工業大學博士論文，2003:l~20