尚玉玲，錢 尚，劉 鵬

(桂林電子科技大學 電子工程與自動化學院, 廣西 桂林 541004)

串擾時延故障的SAT-ATPG算法研究

尚玉玲，錢 尚，劉 鵬

(桂林電子科技大學 電子工程與自動化學院, 廣西 桂林 541004)

隨著芯片運行速度不斷提高,對串擾時延的測試已成為一個迫切需要解決的問題；文中提出一種面向多條攻擊線的受害線上最大串擾噪聲的測試生成方法；此方法建立了串擾通路時延故障模型、分析了布爾可滿足性問題、討論了七值邏輯，研究了串擾時延故障測試轉(zhuǎn)換為CNF的邏輯表達式，在非魯棒測試條件下約簡CNF范式，并提出了串擾時延故障的SAT-ATPG算法；最后通過實例分析，對本文算法進行驗證；結(jié)果表明:該算法對串擾時延故障的測試矢量的生成是有效的。

串擾時延故障；布爾可滿足性；時延測試

0 引言

隨著電子信息技術(shù)不斷發(fā)展，高速電路中信號頻率的增加、邊沿變陡、電路板的尺寸變小和布線密度的增大，這些因素使得在高速電路的設(shè)計中，信號完整性[1](Singnal Integrity，SI)問題越發(fā)突出。串擾引起的時延故障是信號完整性問題中一個突出問題，它是指相鄰信號線同時發(fā)生跳變瞬間，攻擊線對受害線所產(chǎn)生的傳輸時間的變化的故障類型。對串擾故障模型的研究方面，國內(nèi)外研究者取得了一些成果，文獻[2]用無耗傳輸線的串擾為對象，提出了最大攻擊者模型，文獻[3]提出多跳變故障模型，雖然使故障覆蓋率增加，但是大大降低了測試的效率。文獻[4]在最大攻擊者模型的基礎(chǔ)上，提出了最大信號完整性模型，它的優(yōu)點是克服了最大攻擊者模型的缺點，此外在串擾時延的測試方面，它也提出了串擾時延故障，最終得出串擾時延自動測試圖形生成(Automatic Test Pattern Generation)算法。前人基于D算法、PODEM算法、FAN算法等進行了大量研究，但是這些傳統(tǒng)的ATPG，很難求解串擾引起的瞬態(tài)故障并檢測問題。本文主要針對串擾通路時延故障模型進行測試，以跳變通路時延故障模型為基礎(chǔ)并引入串擾機制從而形成的一種串擾時延故障新模型，其特點是在跳變時延故障模型主體上引入串擾信號，將其轉(zhuǎn)化成對應邏輯值從而對整個系統(tǒng)進行測試。近年來，隨著布爾可滿足性 (Boolean -Satisfiability)，SAT求解技術(shù)的發(fā)展及其廣泛應用，基于SAT的ATPG技術(shù)已經(jīng)成為一種新的故障測試矢量的生成方法，被應用于電路時延故障測試的自動測試生成中，如Chen[5]等人對電路的時延故障探究出了生成魯棒測試集的具體方法，李玲[6]等人將增量式SAT技術(shù)應用到時延故障測試中。

1 布爾可滿足性問題

布爾可滿足性問題(SAT),它是第一個被證明的經(jīng)典NP完全問題，有著非常重要的理論意義和應用意義。是用來判斷以合取范式(Conjunctive Normal Form，簡稱CNF)形式給出的命題邏輯公式是否存在一個真值指派，使得該邏輯公式的邏輯值為真。在解決SAT問題的過程中采用DPLL(Davis-Putnam-Logemann-Loveland)算法[7]，基本DPLL算法采用深度優(yōu)化策略去遍歷所有的數(shù)，來找到一組賦值并使其滿足這個問題的要求。當找到這組賦值的時候，搜索就會停止，或者遍歷了所有的空間也沒有找到滿足條件的賦值，搜索也會停止。經(jīng)典的DPLL算法來判斷公式的布爾可滿足性一般求解思路如下。

Input:輸入一個待判定公式K；

Output：輸出公式K的滿足性判定。

Function DPLL-K

{ while(l

{

從公式K中選擇子句M；若選不到，則跳出此循環(huán)；否則，利用子句M，化簡公式K，得到新公式Kt；如果Kt為空，那么輸出公式K就是滿足條件的，停止； 否則，輸出公式K是不滿足的，停止；

}

}

2 基于SAT的串擾時延的ATPG測試方法

2.1 串擾通路時延故障模型

串擾通路時延故障模型是以跳變通路時延為基礎(chǔ)，引入串擾形成的模型。在進行測試時候應該同時滿足：1)與通路時延故障模型測試相比，它不僅需要在原始輸入端加入一個跳變信號，而且在測試路徑上每一個邏輯門的輸入都需要一個跳變信號。2)每個門輸入的跳變信號必須保持一致。在經(jīng)過非門、與非門、或非門等邏輯門取反時，下個門跳變輸入值也要取反。3)通路敏化：在測試通路上，要求旁路輸入的第二個信號的輸入值為非控制值，這樣能夠在非魯棒測試條件下將每一個時延故障都能夠通過測試路徑傳輸?shù)捷敵龆耍礄z測出一個串擾通路時延故障。4)對于攻擊線和受害線，將其轉(zhuǎn)換成邏輯信號值，作為限定條件進行測試矢量的求解。5)采用單路徑敏化測試方法，不能同時測試多條敏化路徑。

2.2 多值邏輯

表1 七值邏輯表

2.3CNF范式表達

因為自動測試矢量的生成是一個NP完全問題，所以我們能用SAT矢量生成算法對此類問題求解。但是由于SAT算法是在CNF范式表達式的基礎(chǔ)上進行求解的，因此我們需要將電路串擾時延故障測試轉(zhuǎn)換為CNF的數(shù)學邏輯表達式形式。電路轉(zhuǎn)換成SAT求解器能處理的CNF范式表達形式，可分為兩步：

(1)用邏輯門的輸入輸出關(guān)系的功能函數(shù)，考慮信號的時序，進行該邏輯門特定邏輯的求解，計算出輸入輸出的邏輯表達式。

(2)根據(jù)蘊涵公式和等價公式計算邏輯表達式得出該門的合取范式，也就是CNF邏輯表達式。我們可以用一個二元組(ZS,ZV)來表示測試通路中門的輸出，二元組(XS,XV)表示門的輸入。從而按照蘊含關(guān)系和門的功能函數(shù)和，用邏輯門的輸入來表示邏輯門的輸出，最終轉(zhuǎn)換成CNF表達式。例如與非門[9]有：

(ZS,ZV) =NAND[(XS,XV),(YS,YV)]?

(1)

2.4 非魯棒性測試條件

在時延故障模型測試中,引入非魯棒測試條件，設(shè)輸入的測試矢量為，如果它能將單時延故障沿著測試路徑即敏化通路傳播到輸出端,并且在規(guī)定的時間內(nèi)檢測到跳變信號，同時輸出的結(jié)果由跳變信號所決定，那么我們就稱這次非魯棒測試是成功的。

同單通路敏化一樣，非魯棒性測試具有兩個條件。

1)在輸入端必須輸入一個跳變信號，使其沿著測試路徑傳播。

2)在測試通路上,要求邏輯門的旁路輸入的第二個向量設(shè)定為非控制值ncv,稱之為通路敏化。在非魯棒測試條件下，與門和與非門的第二個非控制量為1，或門、或非門第二個向量的非控制量為0，旁路輸入表如表2所示。

表2 旁路輸入表

其中:X1是終值為1的跳變，X0是終值為0的跳變。 根據(jù)旁路輸入表以及激活通路上跳變引起時延故障條件，可以確定一些輸入輸出值，代入標準的CNF范式中，最終可得到CNF的最簡形式。

2.5 測試生成算法

將抽象門的數(shù)字電路轉(zhuǎn)化成CNF合取范式，并對故障模型進行建模以及轉(zhuǎn)化,將ATPG問題轉(zhuǎn)化成SAT問題,最后由SAT求解器進行求解。測試矢量生成主要包括4個步驟：

STEP1:提取電路信息建立有向循環(huán)圖。

STEP2:分析每一個邏輯門，將對應的每個門電路按公式1轉(zhuǎn)換成CNF范式表達式。

STEP3:在處理所有門的邏輯轉(zhuǎn)換后，找出其中一條故障路徑，指出攻擊線和受害線，根據(jù)輸入的跳變，將對應邏輯值代入到CNF公式中去；并根據(jù)非魯棒測試的旁路敏化條件來敏化旁路輸入，并加入串擾時延觸發(fā)條件，同樣轉(zhuǎn)換到CNF范式中。

STEP4:將STEP3作為STEP2的約束條件進行CNF范式的最終化簡，然后將最終范式作為串擾時延故障的最終數(shù)學描述，輸入到SAT求解器中進行求解，由此可以得到測試矢量，否則該故障就不可測試。

3 實例及算法性能分析

3.1 實例分析

下面以ISCAS’85BenchmarksC17為例，對串擾時延故障進行分析，邏輯圖如圖1所示。

圖1 實例電路圖

其中故障點在X7處，攻擊線X2的障類型為下降減速時延，信號采樣在X10，其中被測通路為X4→X7→X8→X10。本電路的CNF范式表達式為：QC=NANDG1·NANDG2·NANDG3·NANDG4·NANDG5·NANDG6因此串擾故障時延模型情況下的組合電路的CNF表達式為：

(2)

(X8V+X10V)

(X9V+X11V)X11V

(3)

再次重復操作STEP3得到CNF最簡式：

(4)

最后令最簡范式等于1，則所有的真值按照一定的賦值順序構(gòu)成了一個搜索空間的集合,即V={X1S,X3S,X5S,X5V,X6S,X9S,X9V,X11S}，經(jīng)過反復賦值和回溯，最終可得到測試向量V的空間。存在兩種情況：V1={11011001}，V2={10011001}綜合上面各個輸入量得到Vtotal={1X1SX2S1X3S11001111110001101},故最終得到8組測試矢量X1,X2,X3,X4,X5如表3所示。

表3 測試矢量表

將X3,X4,的向量組帶入到與非門的CNF范式中，并且使與非門范式值為1，即可得到故障點X7的變化，即(X7S,X7V)=(1,1),又因為(X2S,X2V)=(1,1)。那么指定的故障點是由攻擊線X2和受害線X7同時同向跳變引起的下降時延減速故障。由以上測試向量可以求得該故障電路。

3.2 算法性能分析

[10]可以發(fā)現(xiàn)，本文引用的SAT方法相對于傳統(tǒng)的ATPG算法(例如FAN算法)效率更高。在linux系統(tǒng)CPU2.93 GHz，內(nèi)存512M的PC機上，對標準電路ISCAS’85電路進行了驗證。對比FAN算法如文獻[11]中的CPU時鐘，本算法具有明顯的優(yōu)勢。如表4所示，隨機注入20個故障得出相應測試矢量所耗時間的平均值。

表4 實驗結(jié)果與文獻[11]對比

4 結(jié)論

在高速互聯(lián)電路中，串擾作為影響信號完整性問題中的一重要因素嚴重影響信號傳輸?shù)馁|(zhì)量，為了確保電路的正確，需要對電路引起的故障進行檢測，傳統(tǒng)的ATPG算法無法滿足求解規(guī)模較大的問題，文章提出的在串擾通路時延遲故障模型下使用布爾可滿足性求解技術(shù)求解，能夠有效的、省時的解決時延故障的測試問題。

參考文獻：

[1] 石光耀, 尚玉玲, 曲 理. BGA焊點形態(tài)和布局對信號完整性的影響[J]. 桂林電子科技大學學報, 2013, 33(4):279-283.

[2] Ahmed N, Tehranipour M, Nourani M. Extending JTAG for Testing Signal Integrity in SoCs[C]. Conference on Design, Automation and Test in Europe. IEEE Computer Society, 2003:218-223.

[3] 張 月，李華偉，宮月戰(zhàn)等,針對串擾引起的時延故障的測試產(chǎn)生[J].計算機輔助設(shè)計圖形學學報，2004：1448-1553.

[4] Chen W Y, Gupta S K, Breuer M A. Test Generation for Crosstalk-Induced Delay in Integrated Circuits[C]. IEEE, 1999:191-200.

[5] Cheng KT，Chen CH. Generation of high quality non-robust test for Path dealy fsults .Proceedings of design automation conference,1994,PP.365-369.

[6] 李 玲.基于SAT的數(shù)字電路測試生成算法研究[D].哈爾濱：哈爾濱工程大學,2012.

[7] 付 宇，吳為民，姜 升,等.基于SAT的組合電路自動測試向量生成[J]微電子學:2011,14(2):230-234.

[8] 楊德才，謝永樂，陳光禹.基于布爾可滿足性的層次化通路時延故障測試[J].電子測量與儀器學報:2008,22(3):6-10.

[9] 姜 升. 基于SAT的通路時延故障測試生成技術(shù)的研究[D]. 北京交通大學, 2011.

[10] Drechsler S. Acceleration of SAT-Based ATPG for industrial designs[J].IEEE Transactions on Computer-Aided Design of Integrated Circ-uits and Systems:2008,27(7):1329-13.

[11] 顏學龍，梁曉琳,尚玉玲.基于MAF模型的串擾時延故障的測試矢量生成.計算機工程與應用:2009(19).

Study on SAT-ATPG Algorithm for Time Delay Fault of Crosstalk

Shang Yuling，Qian Shang，Liu Peng

(Guilin University of Electronic Technology School of Electronic Engineering and Automation, GuiLin 541004,China)

As the improvement of chip operating speed, so it is high time to consider and take some measures to solve the problem. A test-generation method based on multiple crosstalk-induced glitch fault model is proposed. In this method ,it discusses Boolean satisfiability problem and analyse the crosstalk path delay fault model as well as Seven value logic of test vectors. It also analyse the mathematical logical expression converted by the crosstalk path delay fault model. And simplified CNF expression under the condition of non robust test,then a SAT-ATPG test algorithm of crosstalk delay fault is proposed.Finally,the algorithm is verified by specific example and the performance of the algorithm is effective for crosstalk-induced delay faults.

crosstalk delay fault;Boolean Satisfiability;delay faults testing

2016-07-25；

2016-11-08。

尚玉玲(1977-)，女，廣西桂林人，博士，副研究員，主要從事高速電路信號完整性測試研究。

1671-4598(2017)03-0018-04

10.16526/j.cnki.11-4762/tp.2017.03.006

TP3

A