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