摘要：在超大規(guī)模集成電路芯片中，電路板的詳細實現(xiàn)通常是不知道的，只有功能特性對用戶是公開的。在這篇論文中，我們呈現(xiàn)了一個系統(tǒng)的方案，僅僅基于被測電路板的功能特性，我們可以檢測出并確定出固定故障和橋接故障。被提議的這個方案對于學(xué)術(shù)和工業(yè)超大規(guī)模集成電路使用者檢測固定故障和橋接故障以及確認(rèn)芯片的功能都及有幫助。規(guī)則和實驗結(jié)果將會被報告。

關(guān)鍵詞：功能特性；固定0-1故障；橋接故障；標(biāo)準(zhǔn)輸入矩陣

中圖分類號：TP3 文獻標(biāo)識碼：A 文章編號：1009-3044（2013）12-2866-05

超大規(guī)模集成電路的高速發(fā)展導(dǎo)致了單個芯片的組成元素個數(shù)的指數(shù)增長。然而，由于每個芯片的基本輸入輸出是有限的，這導(dǎo)致了測試芯片工作更加困難。此外，集成電路制造商們因為知識產(chǎn)權(quán)的問題不樂意公開電路板內(nèi)部實現(xiàn)的詳細細節(jié)。另外，為了確保一個系統(tǒng)操作的可靠性，用戶需要在在芯片提供給系統(tǒng)前對其進行測試。盡管如此，用戶通?？梢詮募呻娐分圃焐痰臄?shù)據(jù)書中找到一些該芯片的功能屬性和芯片的部分體系結(jié)構(gòu)。因此，兩個問題出來了：1）只是基于一個芯片的功能特性而不知道其內(nèi)部的實現(xiàn)細節(jié)，對其進行測試可能嗎？2）進一步，用和上一步同樣的信息，不僅測試這個芯片的固定故障而且測試其橋接故障可能嗎？事實是，對這兩個問題的回答都是積極的。

在這篇文章中，我們根據(jù)芯片的功能特性提出了一些系統(tǒng)的測試方法。不管怎樣，基于對被測電路板的有限信息，我們的測試也會受限。因此，我們在此只考慮電路板的基本輸入輸出上的故障。換句話說，我們將要測試的故障僅限于下邊幾種：

1） 基本輸入輸出上的固定故障；

2） 輸入線間的非反饋橋接故障；

3） 輸出線間的非反饋橋接故障；

4） 輸入和輸出間的反饋橋接故障。

盡管我們的測試僅僅是根據(jù)電路板的外部特性提供的有限信息，我們得到了很好的效果，可以很方便的檢測電路板的功能特性。對于大多數(shù)的用戶來說，這個方案可以直接實現(xiàn)而不用復(fù)雜設(shè)備，軟件和其他復(fù)雜工作。

1 基本定理

下邊的定理，已經(jīng)在前幾篇論文中提出并證明，在這里再次列出但不予證明。方便起見，不失一般性，在這片文章中，我們提到橋接故障時就是這與-橋接故障模型。此外，我們把橋接故障劃分為反饋型橋接故障和非反饋型橋接故障。

定理1：讓我們來考慮一個電路板，其實現(xiàn)的F（n，m）這個功能函數(shù)，該功能函數(shù)有n個輸入x1，...xn和m個輸出F1，...Fm，我們在此提出一個輸入矩陣T，其格式如下：

我們稱T為輸入矩陣T。

T可以檢測出輸入線x1，...，xm中的任何一個固定故障，當(dāng)且僅當(dāng)（a）T既不包含全0列也不包含全1列。（b）對每一個i（1≦i≤n），這里總存在一個j（1≤j≤N）和一個k（1≤k≤m）使得Fk（t1j，...ti-1j，0，ti+1j，...，tnj）≠Fk（t1j，...ti-1j，1，ti+1j，...tnj）.

定理2：定理1中提到的輸入矩陣T檢測所有的輸出線上的固定故障當(dāng)且僅當(dāng)對應(yīng)定理1中的輸入矩陣，輸出矩陣。

既不包含全0列也不包含全1列。

定理3：功能函數(shù)F（n，m），有n個輸入x1，...xm，m個輸出F1，...Fm，在這個電路板中非反饋橋接故障可以被檢測當(dāng)且僅當(dāng)至少存在一個輸入結(jié)合（a1，...as，xs+1，...，xn），（a1，...as）不是全0也不是全1，且有一個k（1≦k≦m）滿足

Fk（a1，...as，xs+1，...，xn）≠Fk（0，...，0， xs+1，...，xn）

定義1：X=（x1，...，xn），xi={0，1}。對于有n個變量的布爾功能函數(shù)F來說，當(dāng)X中含有的1的個數(shù)最少且使F=1時，X成為F的最輕最小項。

定理4：實現(xiàn)布爾功能函數(shù)F的輸入輸出間的任何反饋橋接故障都可被檢測出來通過一個一步測試方案0或者一個兩步測試（0，LM），這里L(fēng)M是F的一個最輕最小項。

因為對于所有的反饋橋接故障來說，只有上邊所提的一步或兩步測試被需要。不管怎樣，在兩步測試中，LM必須提供給電路板，測試將第二步尾隨第一步進行。

2 測試固定故障和橋接故障的案例應(yīng)遵循的規(guī)則

基于上面所描述的理論，我們發(fā)現(xiàn)一些測試一個電路板的外部輸入輸出的固定故障和橋接故障應(yīng)遵循的規(guī)則。

讓我們考慮一個實現(xiàn)功能函數(shù)F（n，m）的電路板。T和F（T）是我們以上提到的輸入輸出矩陣。然后，我們可以發(fā)現(xiàn)如果T檢測錯誤，那么輸入矩陣T和輸入矩陣F（T）必須滿足如下規(guī)則：

規(guī)則1：為了檢測固定故障，T和F（T）都既不包含全0列也不包含全1列。因為，如果不這樣，一個固定型故障不能與非固定性故障但是有全0或全1列的區(qū)分開來。

規(guī)則2：為了檢測輸入線上的固定故障，對于每一個輸入線Xi，必須存在一個j和一個k，使得Fk（t1j，...ti-1j，0，ti+1j，...，tnj）≠Fk（t1j，...ti-1j，1，ti+1j，...，tnj）。

規(guī)則3：為了檢測輸入和輸出線上的非反饋橋接故障，T和F（T）都不能含有兩列相同列，這樣任意的非反饋橋接故障都可以被檢測到。因為這個原因，這里必須

規(guī)則4：為了檢測一個電路板的輸入輸出間的反饋橋接故障，輸入矩陣中必須包括上邊所提到的一步和兩步陣列。

基于上述的規(guī)則，固定故障和橋接故障的測試矩陣可以很容易的產(chǎn)生且不用去了解被測芯片的內(nèi)部詳細實現(xiàn)。

作為一個例子，我們來考慮一個8-bit RAM，其有8個輸入（x1，x2...x8），4個地址線（a1，a2，a3，a4）和一個讀寫控制線C.當(dāng)C=0時是寫模式，當(dāng)C=1時是讀模式。此RAM的8個輸入線可以被描述為：

失一般性，我們假定所有的存儲單元在測試前置0，這樣下邊的輸入輸出矩陣可以用來檢測所有以上提到的故障。我們首先按順序依次寫5個8-bit數(shù)據(jù)，然后是讀操作把數(shù)據(jù)倒序讀出來。

可以看出我們上邊提到的固定故障和橋接故障用這對輸入輸出矩陣都可以被檢測出來。為了進一步的闡述輸入輸出矩陣的用途，我們簡單的看幾個例子：

1） 檢測輸入線上的固定故障：一個控制線C上的固定故障，任何一個地址線ai或任何一個數(shù)據(jù)輸入線xj上的固定故障都可以用T和F（T）檢測到。例如，在a1上有一個固定0故障，這樣第五行的輸入變成（0011111110000），使得地址單元（0111）重新寫入（11110000），而地址單元（1111）并沒有數(shù)據(jù)寫入。因此，在輸出矩陣中，輸出的第六行變成（00000000）而且輸出的第七行變成（11110000）.因此，a1上的固定0故障可以被檢測到。

2） 檢測輸出線上的固定故障：對于人一個輸出線zi上的固定故障可以簡單的被輸出矩陣檢測到。任何輸出線上的固定故障將會形成輸出矩陣上的全0或全1列。

3） 檢測輸入線上的非反饋橋接故障：地址線間的任何非反饋橋接故障可以檢測到通過觀察到兩行相同的輸出。例如，兩個地址線a1和a3連接到了一起，那么數(shù)據(jù)輸入矩陣的第三行（01010101）將被重新寫到地址單元（0001）。結(jié)果是，輸出矩陣的第8和第9行有相同的值（01010101）。用類似的方法，一旦地址線和輸入線間有連接在一起的，這樣在輸出矩陣中將有多余一行的數(shù)據(jù)會被改變，因此這個故障可以輕易的檢測到。

4） 檢測基本處出現(xiàn)上的非反饋橋接故障：這個故障可以被直接檢測到僅僅通過檢查在輸出矩陣?yán)锸欠裼兄辽賰蓚€形同的列即可。因為任何輸出線上的非反饋橋接故障都會導(dǎo)致在輸出矩陣中至少有一對相同的列。

3 固定故障和橋接故障的確定

通過上述討論的規(guī)則，我們現(xiàn)在發(fā)明一個系統(tǒng)的方法可以確定一個電路板的固定故障和橋接故障的位置，而不用知道電路板的詳細實現(xiàn)。

方便起見，我們來考慮一個4位快速全加法器。這個加法器有9個輸入線：包括4個數(shù)據(jù)輸入線（A1，A2，A3，A4），（B1，B2，B3，B4）和一個低位向高位的進位C0，五個輸出線：4個輸出線（∑1，∑2，∑3，∑4）和一個向高位的進位線C5.然后讓我們來考慮如下的輸入-輸出矩陣。用來檢測和確定可能的固定故障和橋接故障。

從上面可以看出，4位全加器實現(xiàn)的布爾功能函數(shù)F（9，5），它有9個輸入5個輸出。為了測試和定位故障，矩陣可以稱為標(biāo)準(zhǔn)輸入矩陣（standard input matrix ， SIM）， 它生成的矩陣稱為符合輸出矩陣（corresponding output matrix， COM）。在COM中的每一行都是根據(jù)運算法則對輸入產(chǎn)生的?，F(xiàn)在我們考慮為什么這個選擇好的SIM和COM可以用來測試和定位所有可能的固定型故障和橋接故障。

1） 如果在輸入線上有任何固定型故障，那么至少會有兩個相等的形式出現(xiàn)在SIM中。因此，也會有兩個相等的形式出現(xiàn)在COM。

2） 如果在輸出線上有任何固定型故障，那么在COM中會有全0或全1的列出現(xiàn)。

3） 如果在任何兩個輸入線之間有NFBF故障，那么至少有兩個相等的形式出現(xiàn)在SIM中，因些也會有兩個相等的形式出現(xiàn)在COM中。

4） 如果在任何兩個輸出線上有NFBF故障，那么至少有兩個相等的列現(xiàn)在COM中。

5） 如果在任何輸入線和輸出線之間有FBF故障，然后根據(jù)一步或兩步測試序列，至少錯誤列上會有一個0。

從上面的例子，可以和很容易看到，不僅固定型故障和橋故障可以被測試出來，而且它們的位置也可以根據(jù)他們在輸出矩陣中的錯誤形式找出來。根據(jù)上面的討論，可以得到下面的結(jié)果。在一個電路的合適SIM中，可以找出在主輸入和輸出上的各種錯誤，只要它的相應(yīng)COM符合下面的條件：

1）在輸出矩陣中不多于兩個相等且相鄰的行。

2）在輸出矩陣中不多于兩個相等的列。

3）在輸出矩陣中沒有任何的0（1）列。

進一步，如果輸入形式SIM也滿足在III中的規(guī)則4，那么它也可以測試在輸入線和輸出線上的FBF故障。

為了定位故障，我們重新考慮下面SIM和它COM的通用例子。SIM中根據(jù)函數(shù)有個n條輸入，我們的（n+1 x n）輸入矩陣中每行ti有（i-1）0s，第（tn+1）th行是全（1，1，. . . ，1）向量。圖1（a）展示了SIM的初始化狀態(tài)。對于M列的輸出矩陣，我們稱是SIM按照F函數(shù)對應(yīng)生成的。

根據(jù)上面的呈現(xiàn)的三個可測試條件，我們現(xiàn)在可以用下面的幾個原則去定位固定型故障和橋故障。

1）如果在輸入線xi（1≤i≤n）上有一個故障s-a-0，那么SIM中的輸入形式t（n-i+2）將要變成t（n-i+1），這讓SIM中的兩個相鄰行t（n-i+2） 和t（n-i+1）相等。同樣，在輸出矩陣中，F(xiàn)（n-i+2）也將變成F（n-i+1），標(biāo)記為：F（n-i+2） → F（n-i+1）.

2）如果在兩行以上輸入線上有NFBF錯誤，就是xi和xj，（1≤i≤j≤n ）那么，根據(jù)上面相同的原因，可以很容易地知道在輸出形式COM中將發(fā)生F（n-i+2） → F（n-i+1）的變化。

3）接下來可能會瑣碎些，對于輸出線上的固定型故障或NFBF故障，可以直接觀察輸出矩陣就可以看出來。因此，上面的規(guī)則使用（n+1 x n）SIM和（n+1 x m）COM可以應(yīng)用來去確定固定型故障和橋故障。

對于輸入線和輸出線間的FBF故障，可以使用測試序列（0，LM）在加在SIM的前面就測試任何在輸入線和輸出線間的FBF故障。

事實上，在圖1上描述的SIM不一定能保證產(chǎn)生一個有效的COM去滿足上面的三個測試條件。因此，現(xiàn)在的測試生成算法如果生成一個錯誤的SIM，就交換SIM中的列再生成合適的COM，可以有效地適應(yīng)初始SIM。這里講一種列交換算法，它將修飾輸出形式COM以滿足合適的測試條件。

列交換算法的任務(wù)是進行列交換，描述如下。

列交換規(guī)則：

第一步：對于給定的函數(shù)F（n ， m），形成初始化的a （n+1） x n SIM，可如圖3所示。

第二步：根據(jù)給定的函數(shù)和SIM，運算生成它相應(yīng)的COM。

第三步：檢查新生成的COM是否符合三個條件。 符合條件就停止運行。不符合條件進行第四步。

第四步：完成當(dāng)前SIM中所有列的交換以生成一個新SIM，轉(zhuǎn)回第二步。

為了舉例說了列交換算法中的列交換，我們考慮了一個熟知的電路上的應(yīng)用。如圖4，它是一個4位的ALU，帶著14條輸入線和5條輸出線，首先從它初始的SIM通過函數(shù)得到相應(yīng)的COM。

然而很明顯可以看到，從初始SIM計算出來的COM并不滿足上面三個可測試條件。因為一些COM中相鄰的行是相等的。如F4 =F5 ，F(xiàn)6 =F7 ，F(xiàn)10 = …=F14。經(jīng)過重復(fù)執(zhí)行2-4步，我們通過交換SIM中列的位置可以改變的輸入形式，因此再次計算所得的COM也會改變它的值，此時再次重新檢查新的COM是否滿足三個輸出條件。經(jīng)過幾次重復(fù)列交換算法后，初始的SIM和COM已經(jīng)改變了他們的形式產(chǎn)生出新的COM，新計算的COM也可滿足可以可測試條件，這樣我們就可以根據(jù)原則進行測試。變成圖5所示。

4 加速尋找速度和實驗結(jié)果

交換算法可以生成有效的SIM和它的COM，事實上，最壞的情況下，交換算法的時間復(fù)雜度可以達O（n），n為被測試電話的輸入線數(shù)。這是因為它需要所有可能的輸入排列去找到一個合適的SIM。當(dāng)N增加時，算法的時間復(fù)雜度也就增加。因此，一個隨機的交換算法可以很好地提高查找速度以生成符合條件的COM。使用隨機交換算法，我們每次交換的SIM的n個輸入數(shù)列是隨機產(chǎn)生的，而不是以前算法中的相鄰地一個接一下產(chǎn)生的。理論上，最壞的情況下，隨機交接算法和原始算法有相同的時間復(fù)雜度，但在實際操作中，前者卻是更高效的。下面的表中，列出了以四項基準(zhǔn)比較這兩種算法的實驗運行時間。

參考文獻：

[1] S.Xu and S.Y. H. Su， “Detecting I/O and Internal Feedback Bridging Faults”， IEEE Trans. On Computers Vol.34， No.6， pp.553-557， 1985 ；Also re-printed in IEEE Computer Society Press， 1992， pp.9 –13.

[2] S.Xu and S.Y. H. Su， “Testing Feedback Bridging Faults Among internal， Input and Output Lines by two patterns”， Proc. ICCC 82， 1982， pp.214-217

[3] S. M. Thatte and J. A. Abraham， “Test Generation for Microprocessors”， IEEE Trans. on Computers C29， 1980， pp.429-441.

[4] S. Y. H. Su and Y. I. Hsieh， “Testing Functional Faults in Digital Systems Described by Register Transfer Language”， J. Digital Systems. Vol. 6， 1982， pp.161-183.

[5] M. Karpovshy and S. Y. H. Su， “Detecting Bridging and Stuck-at Faults at Input and Output Pins of Standard Digital Components”， IEEE Proc. 17th Design Automation Conf. pp. 494-505

[6] J. P. Shen et al， “Inductive Fault Analysis of MOS Integrated Circuits”， IEEE Design & Test， Dec. 1985， pp. 13-26

[7] H. Fujiwara， “Computational Complexity of Controllability /Observability Problems for Combinational Circuits”， IEEE Trans. on Computers Vol.39， No.6， 1990， pp.762-767.