集成電路測試技術(shù)論文(2)
集成電路測試技術(shù)論文篇二
集成電路測試生成算法綜述
摘要：隨著集成電路芯片向深亞微米、特大規(guī)模集成電路和高密度方向發(fā)展，進(jìn)行測試所需要的成本也越來越高，因此尋找計(jì)算量合理、故障覆蓋率較高的測試生成算法已成為電路測試領(lǐng)域十分重要的研究課題。本文對目前電路測試生成算法做了一些介紹。
關(guān)鍵詞：集成電路;測試生成算法
1.引言
隨著電子技術(shù)的飛速發(fā)展，集成電路的規(guī)模不斷擴(kuò)大，而引腳數(shù)卻有一定的限制，許多電路被封裝在芯片內(nèi)部，外部可達(dá)到的測試點(diǎn)、原始輸入、原始輸出所占的比例越來越少，導(dǎo)致集成電路的測試和故障診斷越來越困難。故障診斷中最重要的是要找到故障的測試矢量，即測試生成。集成電路的測試生成問題是數(shù)學(xué)上公認(rèn)的難題――NP完全問題，在過去幾年中，國內(nèi)外的一些學(xué)者雖然提出了許多新的測試生成算法，但是到目前為止還沒有一種算法適用于所有的電路，集成電路的測試生成問題己經(jīng)嚴(yán)重地影響了微電子技術(shù)的發(fā)展。
2.集成電路測試生成算法的分類
(1)按照被測電路來分可以分為組合電路測試生成算法和時(shí)序電路測試生成算法兩類。組合電路測試生成算法的研究對象是組合電路，時(shí)序電路測試生成的研究對象是時(shí)序電路。
(2)按照獲取測試矢量集的方法來分可以分為確定性測試生成算法和非確定性測試生成算法。非確定性測試生成主要是偽隨機(jī)測試和加權(quán)隨機(jī)測試算法。確定性測試生成算法是通過算法確定出測試矢量或測試序列。
(3)按照故障模型來分可以分為高級測試生成算法和低級測試生成算法兩大類。高級測試生成算法的故障覆蓋率一般不如低級測試生成算法的高，但是測試時(shí)間要比低級的測試生成時(shí)間少。
(4)按照算法采用的技術(shù)或理論來分可以分為層次式的測試生成算法、符號化的測試生成算法、基于遺傳算法的測試生成算法、啟發(fā)式的測試生成算法等。層次式的測試生成算法將電路的無故障部分用功能塊表示，有故障的部分用門電路表示;符號化的測試生成算法基于二進(jìn)制判決圖(BBD);基于遺傳算法的測試生成算法通過確定能量函數(shù)的最小值點(diǎn)求得測試矢量;啟發(fā)式的測試生成算法使用一些啟發(fā)式的技術(shù)。
(5)按照算法給定的條件來分可以分為面向故障的測試生成算法和面向測試的測試生成算法。面向故障的測試生成算法從給定的目標(biāo)出發(fā)，尋找目標(biāo)故障的測試矢量或測試序列;面向測試的測試生成算法從輸入激勵(lì)出發(fā)，尋找它能測試的故障。
(6)按照算法的特征來分可以分為基于結(jié)構(gòu)的測試生成算法、基于仿真的測試生成算法等。基于結(jié)構(gòu)的算法主要利用電路的結(jié)構(gòu)信息;基于仿真的測試生成算法需要邏輯仿真器作為輔助工具。
3.電路測試生成算法的發(fā)展和現(xiàn)狀
(1)路徑敏化法。組合邏輯電路是數(shù)字電路測試的研究基礎(chǔ)，1959年Eldred提出第一篇關(guān)于組合電路的測試方法，但是該方法不能解決兩級以上組合電路的故障測試問題，是一種比較簡單的測試生成算法。隨后D.B.Armstrong根據(jù)Eldred的基本思想提出了一維通路敏化的方法，即路徑敏化法，其主要思想是：從故障源處到原始輸出之間尋找一條路徑，這條路徑就稱為敏化路徑，沿著這條路經(jīng)，故障效應(yīng)可從源處傳播到原始輸出，也就是故障效應(yīng)可觀。
(2)布爾差分法。布爾差分法由1968年seners等人提出，它將電路描述為數(shù)學(xué)表達(dá)式，從而可進(jìn)行嚴(yán)密的數(shù)學(xué)推導(dǎo)，因此有較高的理論價(jià)值。在布爾差分法的發(fā)展中具有代表性的是主路徑法，主路徑法將通路敏化的概念引入到布爾差分算法中，提高了布爾差分法的效率。近年來發(fā)展起來的二元判定圖(BDD)測試生成方法，也利用了布爾差分法的原理。布爾差分法的優(yōu)點(diǎn)是可以求得給定故障的全部測試，但是對復(fù)雜性較高的電路，用它進(jìn)行測試生成時(shí)需要做大量的布爾差分運(yùn)算，而在計(jì)算機(jī)上對這些運(yùn)算的處理是一件困難的工作。
(3)D算法。Roth等人于1966年提出了基于集合理論的多路徑算法――D算法，主要思想是同時(shí)敏化從故障源到電路輸出的所有全部可能的通路，它克服了一維通路敏化法的局限，采用多維敏化的思想同時(shí)敏化從故障位置到電路的所有輸出端的全部通路，只要所考慮的故障可測，用D算法就一定能求得故障的測試矢量。D算法是第一個(gè)建立在嚴(yán)格理論基礎(chǔ)上的組合電路測試生成算法，它具有算法上的完備性，且便于在計(jì)算機(jī)上實(shí)現(xiàn)，是比較成功和目前應(yīng)用較廣的測試生成算法之一。D算法在進(jìn)行測試生成時(shí)把大量時(shí)間花費(fèi)在對許多不同路徑的試探上，在組合電路的規(guī)模較大時(shí)，用該算法計(jì)算復(fù)雜，效率不高。
(4) PODEM算法。1981年Goel對D算法進(jìn)行改進(jìn)提出了PODEM算法，該算法思路是：對激活的故障向后追蹤到原始輸入，搜索所有可能的原輸入賦值，只要找到一符合要求的即可作為測試圖形，算法即結(jié)束。這種算法是一種分支限界的隱式枚舉算法，它吸收了窮舉法的優(yōu)點(diǎn)，采用逐個(gè)地給原始輸入賦值的辦法為給定故障生成測試，從而避免了許多盲目的試探，減少了D算法中回退與判決的次數(shù)。PODEM算法比D算法的測試生成速度快若干倍，并顯著地減少了回退與判決的次數(shù)，但仍然存在回退的問題。
(5)FAN算法及其擴(kuò)充和發(fā)展。為加速測試生成，F(xiàn)ujiwara等人于1983年提出了FAN算法。該算法在減少回退次數(shù)，降低每一次的回退時(shí)間以及對扇出點(diǎn)都做了細(xì)致處理。FAN算法的運(yùn)算速度快于PODEM算法，不僅回退次數(shù)少，而且故障覆蓋率較高。FAN算法豐富和發(fā)展了測試生成算法的基本思想，近年來出現(xiàn)的一些較為有效的方法，大都基于它的思想，是它的擴(kuò)充和發(fā)展。在FAN算法的發(fā)展中，有代表性的一種算法是Michael等人于1987年提出的SOCRATES算法。這種算法將組合電路的測試生成問題描述成一個(gè)對判定樹的搜索過程，改進(jìn)了FAN算法的蘊(yùn)涵過程，使蘊(yùn)涵更加徹底，用控制的概念解釋唯一敏化現(xiàn)象，使算法在故障傳播時(shí)對更多的情況賦予確定值，擴(kuò)展了多路回退策略。
(6)FASTEST算法。FASTEST算法是基于PODEM算法的時(shí)序電路ATPG算法。FASTEST把測試生成問題當(dāng)單個(gè)問題處理，選擇全面的優(yōu)化決策，所有處理采用時(shí)間向前處理，因此不會在確認(rèn)不可到達(dá)的狀態(tài)上浪費(fèi)時(shí)間，另外測試長度保持最小。FASTEST算法的主要優(yōu)點(diǎn)是可以快速地確認(rèn)不能達(dá)到的狀態(tài)，缺點(diǎn)是需要對時(shí)序單元的總數(shù)和激活故障的時(shí)序單元有較準(zhǔn)的估計(jì)，如果估不正確，會大大浪費(fèi)時(shí)間和存儲資源。
(7)CONTEST算法。CONTEST算法是對選定的初始矢量在模擬結(jié)果的基礎(chǔ)上計(jì)算成本函數(shù)。CONTEST算法對組合及時(shí)序電路都有效，可以對一組故障、單個(gè)故障生成測試矢量，也可生成電路的初始時(shí)序，但三方面應(yīng)用時(shí)成本函數(shù)不同。用CONTEST方法進(jìn)行測試生成要優(yōu)于其他方法，但有時(shí)會生成較多的測試矢量，因?yàn)樵囂綍r(shí)會選擇相鄰的矢量。CONTEST的另一個(gè)應(yīng)用是尋找初始化矢量序列，使得電路從未知狀態(tài)轉(zhuǎn)到已知狀態(tài)。
4.結(jié)束語
隨著微電子技術(shù)的飛速發(fā)展，有些傳統(tǒng)的算法已經(jīng)不再適用，有些方法還存在不足，探索新算法，改進(jìn)己有算法，是測試生成算法研究的重點(diǎn)。
參考文獻(xiàn)
[1] 于云華，石寅.數(shù)字集成電路故障測試策略和技術(shù)的研究進(jìn)展.電路與系統(tǒng)學(xué)報(bào)，2004，9(3):83一91
[2] 向東.數(shù)字系統(tǒng)測試及可測性設(shè)計(jì).科學(xué)出版社，1997:2一11
[3] 劉曉東.集成電路測試生成算法的研究.哈爾濱工業(yè)大學(xué)博士論文，2003:l~20
看了“集成電路測試技術(shù)論文”的人還看：