基于多配置LFSR的測試生成結構設計＊

李 鵬，顏學龍，孫 元

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

1 引言

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

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

2 可配置LFSR結構及隨機性測試矢量生成

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

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

相對于傳統的外異或LFSR結構（如圖2所示），本結構將各個觸發器的輸出經過異或非配置后導入到各個觸發器的輸入，如此可以生成比傳統LFSR更優質的測試序列［13］。傳統LFSR的特征多項式為式（2），它的各項系數反映了LFSR各階節點的反饋配置，同時結合各觸發器的初值，就可以得到狀態更新序列，即狀態矩陣方程（3）中表達式QL1（n＋1）的值：

Figure 1 Configurable LFSR structure圖1 可配置LFSR結構圖

Figure 2 External XOR LFSR structure圖2 外異或LFSR結構

其中QLi（n）表示觸發器在第i時刻的值，QLi（n＋1）表示在i＋1時刻的值，B為LFSR的狀態轉移矩陣［13］。由此可知，除了第一位V1的輸入是由反饋配置而成，其余各位均由第一位移位得到。

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

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

圖3為可配置LFSR結構生成隨機性測試矢量的仿真波形。

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

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

3 多配置LFSR結構及確定性測試集的生成

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

3.1 確定性測試矢量的劃分

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

Figure 4 Multi－configurable LFSR圖4 多配置LFSR結構

定理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為任意常數。

推論 若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）無解。

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

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

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

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

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

3.2 單輸入位的優化配置

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

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

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

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

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

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

3.3 全部輸入位的優化配置

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

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

4 配置優化實例

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

Table 1 Deteministic test vectors in reference［16］表1 文獻［16］中的確定性測試序列

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

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

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

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

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

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

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

Table 3 Optimization results in reference［16］表3 文獻［16］優化的結果

Table 4 Optimization results in this paper表4 本文優化的結果

5 結束語

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

致謝

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

［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－hua，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－hui，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］ 謝永樂，孫秀斌，王玉文，等.數字集成電路的混合模式內建自測試方法［J］.儀器儀表學報，2006，27（4）：367－375.

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

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

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

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

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

［10］ 胡晨，許舸夫，張哲，等.一種基于受控LFSR的內建自測試結構及其測試矢量生成［J］.電路與系統學報，2002，7（3）：13－16.

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

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

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