一種基于混沌搜索的／_ＤＤＴ測試產生算法

摘要：針對瞬態電流測試提出了一種測試產生算法。該算法利用改進FAN算法的反向蘊涵部分激活故障并將測試向量空間映射到混沌空間，采用混沌搜索來確定未確定的測試向量位。模擬實驗結果表明，將這種方法用于瞬態電流測試產生是可行的。

關鍵詞：瞬態電流；混沌搜索； 反向蘊涵； 測試產生； 波形模擬器

中圖分類號：TP331文獻標志碼：A

文章編號：1001-3695(2007)12-0094-03

隨著集成電路技術的飛速發展，集成電路的規模和時鐘頻率迅速提高，傳統的測試方法如電壓測試和單閾值靜態電流／_DDQ測試已不能滿足要求。因此，人們不斷提出新的測試方法，瞬態電流測試就是其中之一^[1~3]。通過實驗人們發現，電路中某些無法用傳統測試方法檢測的故障，可以用瞬態電流測試方法檢測出來，瞬態電流作為傳統測試方法的補充已越來越得到工業界和學術界的重視。

本文所提出的CMOS電路的瞬態電流測試產生是要尋找這樣一對向量對〈v₁，v2〉(其中：v₁是初始化向量；v2用于激活故障)，使得電路在其輸入由v₁到v2的過渡過程中，故障電路和無故障電路的平均瞬態電流／_DDQ的差別足夠大。目前已有的測試產生算法為基于貝葉斯優化的遺傳算法（BOA）^[4]和改進的FAN算法^[5]。前者把利用貝葉斯網絡概率模型指導優化的思想與學習貝葉斯網絡的方法結合起來，首先對一組優選解構造出相應的貝葉斯網絡模型；然后對網絡模型進行采樣，生成新的候選解。該算法故障覆蓋率較高，但要經過多步迭代，比較費時。后者充分考慮電路的拓撲結構，選擇最難觀察的路徑傳播跳變以期找到符合要求的測試向量。

本文采用基于改進FAN算法和混沌搜索來尋找符合要求的測試向量對。首先根據反向蘊涵找到能激活開路故障的輸入向量對的部分原始輸入，再利用混沌所表現出來的內隨機特性和遍歷性進行全局搜索，確定未確定的輸入向量位。該算法在保證一定故障覆蓋率的前提下有效地降低了測試生成時間。通過SPICE模擬實驗結果進一步表明，本文提出的測試產生算法是可行的。

1開路故障的注入

本文針對電路的開路故障進行測試。以一個二輸入CMOS與非門為例，如果CMOS邏輯門內部的一個管腳發生開路故障，通過分析得知，開路故障不一定等效于固定型故障。

當圖1中標“×”的一條管腳發生開路故障時，只要A為高電平，P₁管就截止，此時P₁管開路不影響輸出。若A為低電平，當B為低電平時，P₂管為導通狀態，輸出為高電平，也不影響輸出。只有當A為低電平，B為高電平時，此時P₂管截止，P₁管因為開路故障也無法與電源導通，輸出將維持上一個輸出狀態不變。

對其他管腳進行類似分析可得二輸入CMOS與非門開路故障表，如表1所示。

從表1可以發現，故障電路在一定輸入下，電路輸出仍然保持上一次的狀態，即變成一個具有存儲特性的電路單元。因此，CMOS邏輯門的內部管腳開路故障是一種存儲型故障或時序型故障。要能夠測試這些存儲型故障，必須使得故障發生時的邏輯輸出值與無故障時的邏輯輸出值不一樣。通過分析表1，結合與非門真值表可以得到測試每個MOS管開路故障的測試向量對，如表2所示。

從表2可知，與非門的各個開路故障在哪些條件下有可能被激活。波形模擬器^[6]提供了由輸入向量求得輸出響應的工具，因此只需要對波形模擬器進行相應的修改，采用查找上述故障測試向量表的方法，檢查邏輯門兩個連續輸入求得故障節點的輸出。通過計算無故障電路和故障電路的上跳變差Δ，找到有效的測試向量對。Δ采用文獻[1]所述定義：

2基于混沌搜索測試產生算法

對于／_DDQ測試，不需要像傳統電壓測試那樣將故障信號傳播到原始輸出端，只需要激活故障并將跳變差盡可能在電路中傳播開即可。針對本文的問題，可將整個算法分為兩個部分，即利用改進FAN算法激活故障和用混沌搜索使瞬態電流差別最大化。

2．1激活故障

激活故障就是要在故障門的輸入端產生所需要的跳變并保證故障門的輸出與正常邏輯門的輸出有跳變差。根據1．1節分析，對不同的邏輯門可以得到激活故障的故障門測試向量對。利用改進FAN算法將其反向蘊涵到原始輸入端，即得到激活故障的部分原始輸入。為了詳細說明該算法，先引入如下定義：

定義1若邏輯門的正常輸出為1，故障輸出為0，記為D=0/1，否則記為/D。

定義2對于二輸入門，若輸出為D 或/D 且兩根輸入線均未被賦值，或者對于輸入線多于兩根的門，若輸出為D 或/D 且至少存在兩根輸入線未被賦值，而已賦值的輸入線均賦值為該門的非控制值，則稱這些多輸入門為前向D 前沿。

定義3從扇出點接出的線（可通過一級門）叫做有界線，其他非有界線叫做自由線。

具體算法如下：

a）給故障門的故障線faultl、輸出線和其他輸入線賦值，取故障門的輸出線作為目標線，line=faultl。

b）若故障線為原始輸入，則故障可觀測標志pobsin=faultl。

c）自目標線開始作蘊涵，若蘊涵成功，轉e）。

d）回朔，選擇目標線，若成功轉c）；否則轉g）。

e）若pobsin!=0 ，且有界線均賦值，給自由線賦值，轉h）；否則多路回退選擇新的目標線，若成功轉f）；否則轉d）。

f）在前向D 前沿中選擇一個目標線，若成功轉c）；否則轉d）。

g）無法產生測試向量，失敗返回。

h）成功，結束。

2．2瞬態電流差別最大化

瞬態電流差別最大化就是要使故障門產生的跳變差盡可能向后傳播。筆者采用混沌搜索策略確定未確定的輸入向量位。相關概念及算法如下：

在其參數u=4.0時，表現為混沌映射，由此產生的序列為一個混沌序列。混沌運動具有遍歷性、內隨機性和規律性，能在一定范圍內按其自身規律不重復地遍歷所有狀態。利用混沌的這個特性，在優化過程中采用混沌變量進行搜索，搜索過程按混沌運動的自身規律進行。其隨機性保證了大范圍搜索能力，遍歷性使算法按系統自身的規律不重復地遍歷所有可能狀態，有利于克服一般隨機算法中以分布遍歷性搜索帶來的局限性。

3模擬實驗

本文算法尋找測試向量的依據是使Δ盡可能大，以便無故障電路和故障電路產生足夠大的差異。Δ的大小可由本文算法計算得到。為了驗證本文算法的計算結果，筆者使用SPICE對C432電路進行了模擬實驗，采用0.35 μm工藝的CMOS模型。對節點168（二輸入與非門）設置了P₁管開路故障。

4實驗結果及分析

利用前述基于改進FAN算法和混沌搜索的測試生成算法，在VC環境下，對ISCAS’85和ISCAS’89中部分電路進行測試生成并統計故障覆蓋率。從表4和5的比較可以看出，本文算法的故障覆蓋率優于改進FAN算法。本文算法搜索上限定為10 000個測試向量對，故如果增大搜索空間，本文算法的故障覆蓋率還有進一步提高的希望。從數據比較中可以推斷：改進FAN算法選擇最難觀測的路徑傳播跳變不一定能使Δ的差別最大化，從而使原來可測的故障變得不可測了。從表4和6的比較中可以看出，本文算法故障覆蓋率略低于遺傳算法，但本文算法的收斂速度和算法復雜度明顯優于遺傳算法，故本文算法更具實用性。由表7可以看出，本文算法作一次測試產生最多只需要幾秒，這也進一步說明本文算法比較有效。

5結束語

本文在瞬態電流測試方法的基礎上，針對開路故障這一故障類型提出了一種測試產生算法。該算法充分考慮了電路的拓撲結構，算法思想簡單，測試生成時間短，且有較高的故障覆蓋率。通過SPICE模擬實驗，表明測試產生的結果是有效的，用該方法能夠使無故障電路與故障電路的平均瞬態電流產生較大的差別，從而達到檢測故障的目的。

參考文獻：

[1]閔應驊.CMOS電路電流測試綜述[J].計算機研究與發展，1999，36（2）：129-133.

[2]SU S， MAKKI R， NAGLE T. Transient power supply current testing of digital CMOS circuits[C]//Proc of International Test Conference. Washington DC:IEEE Press， 1999:892-901.

[3]RIUS J，FIGUERAS J. Exploring the combination of ／_DDQ and ／_DDQ testing: energy testing[C]//Proc of Design， Automation and Test in Europe Conference and Exhibition. Munich:DATE Press， 1999:543-548.

[4]MIN Ying－hua， KUANG Ji－shun， NIU Xiao－yan. At-speed current testing[C]//Proc of the 12th Asian Test Symposium.[S.l.]:IEEE Press， 2003:396-399.

[5]魏小芬，鄺繼順. FAN算法在瞬態電流測試產生中的應用[J].同濟大學學報，2002，30(10):1 239-1244.

[6]李立健，閔應驊.基于布爾過程的組合電路波形模擬[J]. 計算機輔助設計與圖形學學報，2001，13(3)：242-246.

[7]MIN Ying－hua， ZHAO Zhu－xing， LI Zhong－cheng. ／_DDQ testing[C]//Proc of the 6th ATS. Akita:IEEE Press， 1997:378-383.

[8]楊士元.數字系統的故障診斷與可靠性設計[M].2版.北京:清華大學出版社， 2000:19-60.

[9]朱啟建，鄺繼順，張大方. 一種動態電流測試產生算法的SPICE模擬驗證[J].電子學報，2002，30（8）:1164-1166.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”