李 鵬，顏學(xué)龍，孫 元

（桂林電子科技大學(xué)電子工程與自動(dòng)化學(xué)院，廣西桂林541004）

1 引言

當(dāng)今深亞微米和超亞微米技術(shù)已成為集成電路設(shè)計(jì)的主要工藝，集成電路的測(cè)試開銷已經(jīng)直接影響到了系統(tǒng)的總開銷。內(nèi)建自測(cè)試BIST（Build－In Self－Test）是解決大型復(fù)雜電路的有效方法［1～3］，其中測(cè)試矢量生成器則是決定BIST測(cè)試質(zhì)量的重要組成部分，優(yōu)質(zhì)的測(cè)試矢量生成器不僅可以用較短的時(shí)間獲得較高故障覆蓋率，而且硬件開銷較少。許多學(xué)者已經(jīng)對(duì)測(cè)試生成方法提出了各自的觀點(diǎn)，如早期的測(cè)試生成方法有確定性測(cè)試方法、窮舉/偽窮舉測(cè)試方法、偽隨機(jī)測(cè)試方法等［1，4］，它們都在測(cè)試集長(zhǎng)度、測(cè)試存儲(chǔ)、故障覆蓋率、硬件開銷等方面存在各種缺陷，近年來(lái)一些新興的測(cè)試生成方法對(duì)上述問(wèn)題做了很大程度上的改進(jìn)，如加權(quán)測(cè)試生成法［5，6］通過(guò)調(diào)整被測(cè)電路輸入引腳信號(hào)‘0’、‘1’信號(hào)出現(xiàn)的概率，以提高故障覆蓋率，但這種方法對(duì)于被測(cè)對(duì)象內(nèi)部結(jié)構(gòu)已知的電路能取得比較好的效果，若被測(cè)對(duì)象內(nèi)部結(jié)構(gòu)未知，則各輸入端的權(quán)重?zé)o法準(zhǔn)確獲得，因此測(cè)試不具備普遍性；又如文獻(xiàn)［7］提出的壓縮確定性矢量集的方法，雖可以有效地減少測(cè)試時(shí)間、提高故障覆蓋率，但壓縮的矢量集需要存儲(chǔ)機(jī)制，這樣又是以增加硬件開銷為代價(jià)。再如文獻(xiàn)［1］提出的基于線性反饋移位寄存器LFSR（Linear Feedback Shift Register）結(jié)構(gòu)優(yōu)化和初態(tài)選擇的混合測(cè)試矢量生成；文獻(xiàn)［8，9］提出的LFSR重復(fù)播種的測(cè)試方法以及文獻(xiàn)［10］提出的受控LFSR，都是通過(guò)選擇部分有針對(duì)性的測(cè)試矢量，以減小測(cè)試冗余，提高故障覆蓋率。但是，這些結(jié)構(gòu)都是需要借助特定的算法和一定的硬件結(jié)構(gòu)來(lái)完成矢量的生成。

本文綜合考慮硬件開銷和故障覆蓋率等因素，提出一種多配置LFSR的混合測(cè)試生成結(jié)構(gòu)及其反饋配置生成的優(yōu)化算法。該結(jié)構(gòu)無(wú)須存儲(chǔ)測(cè)試矢量，直接通過(guò)對(duì)LFSR反饋網(wǎng)絡(luò)的配置和分時(shí)段控制，就能用較小的硬件代價(jià)實(shí)現(xiàn)隨機(jī)性矢量和確定性矢量的生成。因此，被測(cè)電路中的隨機(jī)矢量可測(cè)性故障（Random Pattern Detectable Faults）和抗隨機(jī)性故障（Random Pattern Resistant Faults）均能夠被檢測(cè)［11，12］，從而提高了單位時(shí)間內(nèi)的故障覆蓋率。

2 可配置LFSR結(jié)構(gòu)及隨機(jī)性測(cè)試矢量生成

圖1為可配置反饋網(wǎng)絡(luò)LFSR的結(jié)構(gòu)圖，其各個(gè)觸發(fā)器的輸入是由觸發(fā)器輸出經(jīng)反饋異或配置串聯(lián)選擇反向配置（合并稱“反饋配置”）得到。該電路的各個(gè)輸入Vi可用含有r個(gè)觸發(fā)器輸出的邏輯變量QL1（n），QL2（n），…，QLr（n）和反向配置邏輯變量Ci表示成二元域內(nèi)的線性非齊次方程：

其中，aki為第k個(gè)觸發(fā)器反饋接入第i位輸入的配置節(jié)點(diǎn)，aki∈｛0，1｝，k、i＝1，2，…，r。aki＝1時(shí)表示反饋接入異或門，反之表示無(wú)反饋接入；Ci為非門控制，Ci∈｛0，1｝，Ci＝1時(shí)表示通過(guò)非門接入輸入，反之則直通輸入；QLi為第i位觸發(fā)器輸出。

相對(duì)于傳統(tǒng)的外異或LFSR結(jié)構(gòu)（如圖2所示），本結(jié)構(gòu)將各個(gè)觸發(fā)器的輸出經(jīng)過(guò)異或非配置后導(dǎo)入到各個(gè)觸發(fā)器的輸入，如此可以生成比傳統(tǒng)LFSR更優(yōu)質(zhì)的測(cè)試序列［13］。傳統(tǒng)LFSR的特征多項(xiàng)式為式（2），它的各項(xiàng)系數(shù)反映了LFSR各階節(jié)點(diǎn)的反饋配置，同時(shí)結(jié)合各觸發(fā)器的初值，就可以得到狀態(tài)更新序列，即狀態(tài)矩陣方程（3）中表達(dá)式QL1（n＋1）的值：

Figure 1 Configurable LFSR structure圖1 可配置LFSR結(jié)構(gòu)圖

Figure 2 External XOR LFSR structure圖2 外異或LFSR結(jié)構(gòu)

其中QLi（n）表示觸發(fā)器在第i時(shí)刻的值，QLi（n＋1）表示在i＋1時(shí)刻的值，B為L(zhǎng)FSR的狀態(tài)轉(zhuǎn)移矩陣［13］。由此可知，除了第一位V1的輸入是由反饋配置而成，其余各位均由第一位移位得到。

因此，只要確定LFSR的初始狀態(tài)和反饋配置，那么它生成的測(cè)試矢量就是固定的。若該多項(xiàng)式是r次的本原多項(xiàng)式［1］，就可以產(chǎn)生具有最長(zhǎng)周期（2r－1個(gè)）的偽隨機(jī)測(cè)試矢量，并從各觸發(fā)器的輸出端并行導(dǎo)出。

如果將式（1）中的Ci全部清0，aki配置成式（3）中的狀態(tài)轉(zhuǎn)移矩陣（i＝1，2，…，r），那么就生成和傳統(tǒng)LFSR一樣的偽隨機(jī)測(cè)試矢量。

圖3為可配置LFSR結(jié)構(gòu)生成隨機(jī)性測(cè)試矢量的仿真波形。

此外，對(duì)于確定性矢量的生成，按其產(chǎn)生的順序，將待生成的測(cè)試矢量的第i位，從第1個(gè)序列到第s個(gè)序列依次代入到方程（1）中，即可得到矩陣方程（4）：

對(duì)應(yīng)于式（4）中的各個(gè)部分，可簡(jiǎn)記為：b＝A＊CNi，其中b為確定性矢量在第i位的次態(tài)值列向量，CNi為配置列向量，A中的Vxi為確定性矢量的現(xiàn)態(tài)值，s為確定性測(cè)試集的大小。如果方程（4）有解，說(shuō)明該確定性測(cè)試集的第i位序列可以完全通過(guò)配置向量CNi得到；反之，說(shuō)明該配置向量只能生成原確定性測(cè)試集在第i位中的一部分序列，而另一部分需要重新代入式（1），構(gòu)造新的矩陣方程，尋求新的配置向量，直到全部測(cè)試集可解為止。因此，生成完整的確定性測(cè)試集可能需要多種配置。

3 多配置LFSR結(jié)構(gòu)及確定性測(cè)試集的生成

在可配置LFSR的基礎(chǔ)上，將隨機(jī)性測(cè)試矢量配置和各個(gè)確定性測(cè)試矢量配置分時(shí)段作用于觸發(fā)器陣列上，就得到如圖4所示的多配置LFSR結(jié)構(gòu)。

3.1 確定性測(cè)試矢量的劃分

在多配置的LFSR結(jié)構(gòu)中，完整的確定性測(cè)試集被劃分為p個(gè)子集，每個(gè)子集由相應(yīng)的配置向量作用一定的時(shí)鐘來(lái)生成。其中配置通道的個(gè)數(shù)和配置向量的作用時(shí)鐘都需要通過(guò)對(duì)原測(cè)試矢量的劃分來(lái)決定，矢量劃分的理論基礎(chǔ)就是非齊次方程組的有解判定定理［14］。

Figure 4 Multi－configurable LFSR圖4 多配置LFSR結(jié)構(gòu)

定理1 非齊次線性方程組：

Figure 3 Simulation waveform of random test vectors圖3 隨機(jī)性測(cè)試矢量的仿真波形

則式（5）可寫成Ax＝b。方程組（5）有解的充分必要條件是矩陣A的秩R（A）等于其增廣矩陣的秩R（A｜b）。

定理2 設(shè)η是非齊次方程組的一個(gè)特解，ξ1，ξ2，…，ξn－r是其導(dǎo)出組的基礎(chǔ)解系，則非齊次方程組（5）的通解為η＋k1ξ1＋k2ξ2＋…＋kn－rξn－r，其中r＝R（A），k1，k2，…，kn－r為任意常數(shù)。

推論 若R（A）＝R（A｜b）＝n，方程組（5）有唯一解；若R（A）＝R（A｜b）＜n，方程組（5）有無(wú)窮多解，其通解為η＋k1ξ1＋k2ξ2＋…＋kn－rξn－r；若R（A）≠R（A｜b）時(shí)，方程組（5）無(wú)解。

根據(jù)上述的定理1和推論可知：方程組（4）中只有當(dāng)R（A）＝R（A｜b）時(shí)，才可以求出其配置向量CNi；若R（A）≠R（A｜b），則需要對(duì)原測(cè)試集進(jìn)行劃分，劃分的步驟為：

（1）將方程組（4）中的增廣矩陣（A｜b）做行初等變換（二元域內(nèi)的模2加），使每行第一個(gè)非零元素下面的數(shù)為0。

（2）找出增廣矩陣（A｜b）中A陣全為0、而b中不為零的行，即是R（A）≠R（A｜b）的行，那么該行便是原測(cè)試集的一個(gè)劃分點(diǎn)。

（3）將原測(cè)試集在該劃分點(diǎn)之后的測(cè)試矢量重新代入方程（4），并重復(fù)步驟（1）、（2），直到剩余的測(cè)試矢量全部可解。

劃分子集的個(gè)數(shù)即為配置向量通道的個(gè)數(shù)p，而各劃分子集的長(zhǎng)度（子集中包含測(cè)試矢量的個(gè)數(shù)）就是每個(gè)配置向量的作用時(shí)鐘數(shù)。

3.2 單輸入位的優(yōu)化配置

根據(jù)定理2可知，非齊次方程可能存在多組解，而解結(jié)構(gòu)的不同，整個(gè)結(jié)構(gòu)的硬件開銷也隨之不同，因此為了獲得較少的硬件開銷，必須對(duì)方程的通解進(jìn)行尋優(yōu)。對(duì)于配置向量CNi＝（a1ia2i…ariCi），其中各個(gè)元素取值為0或1，向量中的“1”元素對(duì)應(yīng)著配置網(wǎng)絡(luò)中的門結(jié)構(gòu)的連接，因此要使門結(jié)構(gòu)最少，應(yīng)以尋找通解中“1”最少的一組解向量作為限制條件，進(jìn)行解空間內(nèi)的尋優(yōu)。尋優(yōu)步驟為：

（1）求出矩陣方程的基解（ξ1ξ2…ξN）和特解η。

（2）將基解矩陣（ξ1ξ2…ξN）T做初等行變換［15］，使每行第一個(gè)非0元素以下和以上的各行對(duì)應(yīng)元素為0，得（ξ′1ξ′2…ξ′N）T。

（3）計(jì)算η中含“1”的個(gè)數(shù)，記I（η），并在ξ′1ξ′2…ξ′N中找出與η重復(fù)度最大的基ξ′r1，做運(yùn)算η1＝η⊕ξ′r1。

（4）計(jì)算I（η1），并比較I（η）和I（η1）。若I（η）＜I（η1），則η即為最優(yōu)通解，算法停止；若I（η）≥I（η1），則在余下的ξ′1，ξ′2，…，ξ′r1－1，ξ′r1＋1，…，ξ′N中找出與η1重復(fù)度最大的基ξ′r2，重復(fù)（3）、（4）兩個(gè)步驟。

在通解尋優(yōu)過(guò)程中，若采用遍歷算法，則需要用特解η與所有基解（ξ1ξ2…ξN）進(jìn)行2N次組合，再在這些組合當(dāng)中尋找含‘1’最少的通解作為最優(yōu)配置解，然而對(duì)于基解個(gè)數(shù)較多的矩陣方程，無(wú)疑大大增加了尋優(yōu)復(fù)雜度。而通過(guò)本文提出的算法能夠快速地尋找最優(yōu)通解配置，其中初等行變換過(guò)程包括由上至下和由下至上，至多需要進(jìn)行N×（N＋1）次更新；特解的更新過(guò)程至多需要進(jìn)行N次，因此最大尋優(yōu)次數(shù)不超過(guò)N×（N＋2）次。

3.3 全部輸入位的優(yōu)化配置

式（4）僅指出了第i位的配置向量，將各位（i＝1，2，…，r）代入式（4）中并列出矩陣方程，即為式（6）。

對(duì)應(yīng)式（6）中的各個(gè)部分簡(jiǎn)記為：B＝A＊Con，B為確定性矢量的次態(tài)值，A中的Vmn部分為現(xiàn)態(tài)值，Con為所有位的反饋配置矩陣，下標(biāo)t為確定性測(cè)試集的大小減1。將這里的增廣矩陣A｜B做如同3.1節(jié)中的矢量劃分處理；再解出各個(gè)子集的通解配置向量，并按3.2節(jié)中的尋優(yōu)算法遍歷全部配置位；最后結(jié)合子集的長(zhǎng)度，一起施加到可配置LFSR結(jié)構(gòu)就可生成各確定性子集。

4 配置優(yōu)化實(shí)例

為了驗(yàn)證方案的可行性，以文獻(xiàn)［16］中一組六位測(cè)試矢量為例，如表1所示，將表1的序列1到序列15代入到式（6）中的現(xiàn)態(tài)矩陣A的Vmn中，序列2到序列16代入到次態(tài)矩陣B中，列出矩陣方程為式（7）。對(duì)式中的增廣矩陣A｜B做矢量劃分，式中用虛線繪出，解出各個(gè)子集，并對(duì)配置解向量進(jìn)行優(yōu)化。表2列出了本文提出的方案和文獻(xiàn)［16］優(yōu)化結(jié)果比較。表2中簡(jiǎn)記表達(dá)式a1iV1D＋a2iV2D＋…＋ariVrD＋Ci為配置向量CNi＝（a1ia2i…ariCi）。表2最后一行的硬件占用面積由公式（8）［16］計(jì)算得到，其中W1為二輸入異或門（XOR）的硬件面積，W2為非門（NOT）的硬件面積，W3為觸發(fā)器（FFA）的硬件面積，取W1＝11.52μm2，W2＝4.32μm2，W3＝38.88μm2。

Table 1 Deteministic test vectors in reference［16］表1 文獻(xiàn)［16］中的確定性測(cè)試序列

由此可看出，本文的方案在生成各個(gè)子序列時(shí)，對(duì)配置網(wǎng)絡(luò)使用的硬件開銷有更進(jìn)一步的減小。

在Quartus II環(huán)境下，編寫多配置的LFSR結(jié)構(gòu)，并將上述反饋配置向量加載到結(jié)構(gòu)中，得到如圖5所示的確定性測(cè)試集的仿真波形。

表3和表4分別列出了文獻(xiàn)［16］和本文對(duì)幾種綜合基準(zhǔn)電路的矢量劃分和硬件開銷的比較結(jié)果。

實(shí)驗(yàn)所用到的確定性矢量由文獻(xiàn)［17］提供，矢量集大小以文獻(xiàn)［16］提供的大小為基準(zhǔn)，實(shí)驗(yàn)使用C代碼模擬各個(gè)矢量集劃分和各個(gè)子集所需的配置網(wǎng)絡(luò)的生成過(guò)程。

由比較結(jié)果可以看出，本文提出的方法在硬件開銷方面，異或門的數(shù)量有顯著減少，非門數(shù)量也有一定程度的減少，因此在總體硬件面積方面本文所提方法更具有優(yōu)勢(shì)。

Figure 5 Simulation waveform of determistic test vectors圖5 確定性測(cè)試集的仿真波形

Table 2 Comparison of configuration vectors results in reference［16］with this paper表2 文獻(xiàn)［16］和本文配置向量的比較結(jié)果

Table 3 Optimization results in reference［16］表3 文獻(xiàn)［16］優(yōu)化的結(jié)果

Table 4 Optimization results in this paper表4 本文優(yōu)化的結(jié)果

5 結(jié)束語(yǔ)

本文介紹了一種多配置LFSR的測(cè)試生成結(jié)構(gòu)，該結(jié)構(gòu)通過(guò)實(shí)時(shí)地配置反饋網(wǎng)絡(luò)，可以實(shí)現(xiàn)隨機(jī)性測(cè)試矢量和確定性測(cè)試矢量的生成。在配置確定性測(cè)試矢量時(shí)，利用矩陣的相關(guān)理論，提出了一種對(duì)原始序列進(jìn)行劃分的方法和一種尋求各劃分子序列的最優(yōu)配置向量解的優(yōu)化算法，算法實(shí)現(xiàn)簡(jiǎn)易可靠。通過(guò)實(shí)例和對(duì)幾種綜合基準(zhǔn)的驗(yàn)證，證明了本方案能生成任意給定的測(cè)試矢量，同時(shí)能更大程度地減少硬件開銷。

致謝

感謝數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院的段復(fù)建老師，在本文的“單輸入位的優(yōu)化配置”一節(jié)中，對(duì)通解的優(yōu)化算法提供的指導(dǎo)和幫助。

［1］ Xie Yong－le，Sun Xiu－bin，Wang Yu－wen，et al.A mixed mode BIST approach of digital integrated circuits［J］.Chinese Journal of Scientific Instrument，2006，27（4）：367－375.（in Chinese）

［2］ Zhou Bin.Research on low cost deterministic Built－In Self－Test（BIST）［D］.Haerbin：Harbin Institute of Technology，2010.（in Chinese）

［3］ Li Xin，Liang Hua－guo，Chen Tian，et al.Low power deterministic built－in self－test based on folding counter［J］.Chinese Journal of Scientific Instrument，2011，32（12）：1－5.（in Chinese）

［4］ Yang Ji－xiang.Data domain test technology and instruments［M］.Beijing：Science Press，1990.（in Chinese）

［5］ Xie Yong－le，Chen Guang－ju.Deterministic test set based random test with multiple weighted set of digital integrated circuits［J］.Chinese Journal of Scientific Instrument，2002，23（6）：576－578.（in Chinese）

［6］ Tan En－min.Optimizing methods in the design of build－in self－test for digital circuits［D］.Shanghai：Shanghai Jiaotong University，2007.（in Chinese）

［7］ Rozkovec M，Jenicek J，Novak O.Application dependent FPGA testing method using compressed deterministic test vectors［C］∥Proc of the 16th IEEE International on On－Line Testing Symposium，2010：192－193.

［8］ Yang Yi，Zhou Rui－h(huán)ua，Huang Wei－kang.On reseeding BIST schemes with variable lengths of test sequences［C］∥Proc of CTC’04，2004：215－221.（in Chinese）

［9］ Yong Zhi－yan，Hong Wang，Zhi Jia－yang，et al.A new LFSR reseeding method for BIST［C］∥Proc of the 8th IEEE International Conference on Solid－State and Integrated Circuit Technology，2006：2145－2147.

［10］ Hu Chen，Xu Ge－fu，Zhang Zhe，et al.BIST structure and test vector generation based on a controlled LFSR［J］.Journal of Circuits and Systems，2002，7（3）：13－16.（in Chinese）

［11］ Yuan X，Chen C I H.Automated synthesis of a multiple－sequence test generator using 2－D LFSR［C］∥Proc of the 11th Annual IEEE International ASIC Conference.1998：75－79.

［12］ Chen C I H，George K.Configurable two－dimensional linear feed back shifter registers for parallel and serial built－in self－test［J］.IEEE Transactions on Instrumentation and Measurement，2004，53（4）：1005－1014.

［13］ Gu Xiao－chen，Zhang Min－xuan.Multi－output fibonacci type LFSR based uniform random number generator：Design and analysis［J］.Computer Engineering ＆Science，2009，31（A1）：80－83.（in Chinese）

［14］ Yang Gui－yuan.Linear algebra［M］.Beijing：Electronic Science and Technology Press，2002.（in Chinese）

［15］ Wang Xing－quan.The essence of row－simplest form and a new proof of its uniqueness［J］.Journal of Hexi University，2010，26（5）：31－34.（in Chinese）

［16］ Zhang Xin－h(huán)ui，Chen C I H，Ckhakravarthy A.Structure design and optimization of 2－D LFSR－based multi－sequence test generator in built－in self－test［J］.IEEE Transactions on Instrumentation and Measurement，2008，57（3）：651－663.

［17］ Index of VLSI prj benchmarks synthesized［EB/OL］.［2013－05－10］.http：∥service.felk.cvut.cz/vlsi/prj/Benchmarks/Synthesized.

附中文參考文獻(xiàn)：

［1］ 謝永樂(lè)，孫秀斌，王玉文，等.數(shù)字集成電路的混合模式內(nèi)建自測(cè)試方法［J］.儀器儀表學(xué)報(bào)，2006，27（4）：367－375.

［2］ 周彬.低測(cè)試成本的確定性內(nèi)建自測(cè)試的研究［D］.哈爾濱：哈爾濱工業(yè)大學(xué)，2010.

［3］ 李鑫，梁華國(guó)，陳田，等.基于折疊計(jì)數(shù)器的低功耗確定BIST方案［J］.儀器儀表學(xué)報(bào)，2011，32（12）：1－5.

［4］ 楊吉祥.數(shù)據(jù)域測(cè)試技術(shù)及儀器［M］.北京：科學(xué)出版社，1990.

［6］ 談恩民.數(shù)字電路BIST設(shè)計(jì)中的優(yōu)化技術(shù)［D］.上海：上海交通大學(xué)，2007.

［8］ 楊懿，周瑞華，黃維康.變長(zhǎng)序列重復(fù)播種內(nèi)建自測(cè)試方案探討［C］∥第三屆中國(guó)測(cè)試學(xué)術(shù)會(huì)議，2004：215－221.

［10］ 胡晨，許舸夫，張哲，等.一種基于受控LFSR的內(nèi)建自測(cè)試結(jié)構(gòu)及其測(cè)試矢量生成［J］.電路與系統(tǒng)學(xué)報(bào)，2002，7（3）：13－16.

［13］ 谷曉忱，張民選.多輸出外部反饋型LFSR均勻分布隨機(jī)數(shù)生成器的分析與設(shè)計(jì)［J］.計(jì)算機(jī)工程與科學(xué)，2009，31（A1）：80－83.

［14］ 楊桂元.線性代數(shù)［M］.北京：電子科技出版社，2002.

［15］ 王興泉.行最簡(jiǎn)形矩陣的實(shí)質(zhì)及其唯一性的新證明［J］.河西學(xué)院學(xué)報(bào)，2010，26（5）：31－34.