李 鵬，顏學龍，孫 元

（桂林電子科技大學電子工程與自動化學院，廣西桂林541004）

1 引言

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

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

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

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

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

相對于傳統(tǒng)的外異或LFSR結(jié)構(gòu)（如圖2所示），本結(jié)構(gòu)將各個觸發(fā)器的輸出經(jīng)過異或非配置后導入到各個觸發(fā)器的輸入，如此可以生成比傳統(tǒng)LFSR更優(yōu)質(zhì)的測試序列［13］。傳統(tǒng)LFSR的特征多項式為式（2），它的各項系數(shù)反映了LFSR各階節(jié)點的反饋配置，同時結(jié)合各觸發(fā)器的初值，就可以得到狀態(tài)更新序列，即狀態(tài)矩陣方程（3）中表達式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時刻的值，QLi（n＋1）表示在i＋1時刻的值，B為LFSR的狀態(tài)轉(zhuǎn)移矩陣［13］。由此可知，除了第一位V1的輸入是由反饋配置而成，其余各位均由第一位移位得到。

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

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

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

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

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

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

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

3.1 確定性測試矢量的劃分

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

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

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

Figure 3 Simulation waveform of random test vectors圖3 隨機性測試矢量的仿真波形

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

定理2 設η是非齊次方程組的一個特解，ξ1，ξ2，…，ξn－r是其導出組的基礎解系，則非齊次方程組（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）有無窮多解，其通解為η＋k1ξ1＋k2ξ2＋…＋kn－rξn－r；若R（A）≠R（A｜b）時，方程組（5）無解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了驗證方案的可行性，以文獻［16］中一組六位測試矢量為例，如表1所示，將表1的序列1到序列15代入到式（6）中的現(xiàn)態(tài)矩陣A的Vmn中，序列2到序列16代入到次態(tài)矩陣B中，列出矩陣方程為式（7）。對式中的增廣矩陣A｜B做矢量劃分，式中用虛線繪出，解出各個子集，并對配置解向量進行優(yōu)化。表2列出了本文提出的方案和文獻［16］優(yōu)化結(jié)果比較。表2中簡記表達式a1iV1D＋a2iV2D＋…＋ariVrD＋Ci為配置向量CNi＝（a1ia2i…ariCi）。表2最后一行的硬件占用面積由公式（8）［16］計算得到，其中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 文獻［16］中的確定性測試序列

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

致謝

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

［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.

附中文參考文獻：

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

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

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

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

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

［8］ 楊懿，周瑞華，黃維康.變長序列重復播種內(nèi)建自測試方案探討［C］∥第三屆中國測試學術會議，2004：215－221.

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

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

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

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