基于LFSR狀態相關的測試數據壓縮方法*

毛 蔚 ，梁華國 ，程旺燕

(1.合肥工業大學 計算機與信息學院，安徽 合肥230009；2.合肥工業大學 電子科學與應用物理學院，安徽 合肥230009)

隨著電路復雜程度的提高和尺寸的日益縮小，特別是進入深亞微米以及超高集成度的發展，通過集成各種IP核[1]系統級芯片的功能更加強大的同時也帶來了一系列的設計和測試問題。例如，如何壓縮迅猛增長的測試數據就是設計者、EDA工具廠商面臨的挑戰之一。

在傳統的測試生成方法中，測試生成過程長、測試復雜程度高、故障覆蓋率低。一種高效、經濟的測試方法是使用內建自測試(BIST)[2-3]來代替傳統的方法，它通過在芯片內部集成少量的邏輯電路實現對整個電路的測試。內建自測試(BIST)是近年來研究的熱點，而使用線性反饋移位寄存器(LFSR)[4]生成測試模式的偽隨機內建自測試，已經被學術界、工業界廣泛地使用。

在內建自測試中，一種使用LFSR重新播種的方法得到了普遍應用[5]。LFSR重新播種方法的核心思想是將確定測試向量集編碼成LFSR種子，而種子是需要裝入LFSR的一組位序列，通過運行LFSR，可將種子擴展為所需要的確定性向量，然后送入掃描鏈。

1 編碼理論及實現策略

1.1 LFSR編碼

線性反饋移位寄存器常用來組成測試向量生成器，它由互連的寄存器和線性邏輯單元(異或門或同或門)組成。一個伽羅華域GF(2)上的n級LFSR結構圖如圖1所示[6]，其中hi=1表示反饋線路接通，hi=0表示反饋線路未接通。

圖1的特征多項式為f(x)=1+h1x1+h2x2+…+hn-1xn-1+xn，該 LFSR的狀態轉移矩陣 Φ 為[10]：

圖1 n位反饋移位寄存器的結構

在LFSR重播種方法中，求解LFSR種子時，通過選定的特征多項式，建立狀態轉移矩陣，結合測試向量建立方程組，若方程有解，則編碼成功；否則編碼失敗。

1.2 方案實現策略

在LFSR重新播種方法中，為使LFSR能成功編碼測試集中所有的測試向量，其度數受測試集Smax的制約；若能降低Smax的值，就可以降低LFSR的度數，也就能提高數據壓縮率和編碼效率[4]。在本文方案中，結合了完全測試向量切分方法，根據測試向量的長度，為了使控制簡單，把所有向量切分成兩個等長的向量，這樣可以降低Smax的值，達到減少種子位數的目的。例如，將一個18位的測試向量a0a1…a17=x1x0101x110111xxxx切分成等長的兩部分，得到兩個連續的測試向量b0b1…b17=x1x0101x1xxxxxxxxx和 c0c1…c17=10111xxxxxxxxxxxx。 其中粗體部分分別為和，剩余部分由無關位填充，切分后生成的測試向量確定位數大大降低，編碼成功率將會顯著提高。可以求解得b0b1…b17和c0c1…c17的種子，分別為s1=110和s2=101,將種子展開后形成的測試序列分別為v1=110010111001011100和 v2=101110010111001011，只要將v1和v2的黑體部分組合起來，就可以得到測試向量 v=110010111101110010，它與 a0a1…a17是相容的。 在實際操作中，只需在裝載s1后，經過9個時鐘周期再裝載s2，就可以生成測試序列 v。

在傳統的LFSR重新播種方法中，分別對每個測試向量進行編碼，求解出測試向量的種子，計算出種子后，將種子施加到LFSR上，LFSR則利用種子來生成測試向量。記LFSR的初始狀態為S0（即為種子），當LFSR運行m個周期(m為掃描鏈的長度)，種子擴展為所需要的向量后，再把掃描鏈的內容加載到電路中進行測試。記測試向量充滿整個掃描鏈時的LFSR的下個狀態Sm+1為末態。接著測試電路又載入另一個種子，繼續生成測試向量。而由于LFSR的末態和種子集S中某一種子存在某種關系，它們可能僅有部分不同位，舉例如圖2所示。

圖2 種子的處理

在圖 2中，對應種子 s1的末態是 010011，對比 s2、s3、s4，此末態與種子s3之間的變化位最小，即海明距離最小。此時，當載入完s1后，接著載入s3，在載入下一個種子s3時，可不必載入該種子的全部位，只需改變相應位的寄存器值。定義種子格式在原種子后加入控制位，以確定需要改變哪些寄存器值。當載入完s1后，其末態的第4位需要翻轉，記錄信息為100。

1.3 選擇排序策略

對于種子Si=b0b1…bN-1，bi表示各種子位數，LFSR運行Si后的末態為：

種子集S按上述方法生成對應的末態集合M。為使得在載入下一個種子時需改變的寄存器數量最少，需找到一個種子與此時LFSR末態相同位盡可能多，即海明距離盡可能小。

從全局來講，目標是要使得所有種子與其上一個末態之間的海明距離之和最小，所以需要對種子集進行排序。從某個種子開始，遍歷每個種子，并且每個種子被訪問一次且僅一次，其目標是找出一個與末態的海明距離之和最小的種子序列。在這個過程中，會產生帶控制位的新的種子序列。該問題為旅行商問題TSP(Traveling Salesman Problem)[7]，它是組合優化問題中典型的NP-hard問題，從圖論的角度，該問題的數學描述為：

給定無向圖 G=＜v，e＞，其中 V為頂點集（種子集），E為邊集，且|V|=n。D=(dij)n×n為頂點距離矩陣，其元素dij表示種子i與種子j末態之間的海明距離，又設π=(π1，π2，…，πn)表示 1，2，…，n 的一個排列，則 TSP 為約束組合優化問題可表示為：

1.4 帶多輸入端口的LFSR

在本文的方案中使用的是經過改造過的LFSR。對于被測電路的輸入，傳統的測試方法為每輸入一組種子，LFSR就對輸入值進行移位、異或運算，并將結果移入掃描鏈中，接著再輸入下一組種子重復上面步驟[8]。由于種子在LFSR中運行的末態數值可能會與其他種子相容或者有很多相同位，如果載入下一種子時仍舊重新載入這些相同位，則會占用大量的存儲空間，隨著系統的復雜度提高，導致測試向量的增多，測試時間將變長。本方案使用的是多輸入移位寄存器，結構如圖3所示。

與普通LFSR區別在于，該結構中使用了多路選擇器MUX，使得不需要額外的邏輯便可以重載LFSR，在從ROM中載入種子時，所要做的是檢測種子集中的相應的控制位，當新種子和LFSR中的寄存器中的內容不同時，重播種電路的輸出在相應的多路選擇器的選擇端置1，載入種子位。該方法可以從各個輸入端in并行輸入，從而可以提高種子的載入效率，節省測試時間和測試費用。

圖3 多輸入移位寄存器

2 硬件結構

圖4所示為本文方案的解壓電路原理框圖，該電路主要由一個狀態機(FSM)、一個多輸入端 LFSR、塊計數器、位計數器、模式計數器等器件組成，上一節介紹的編碼信息存儲在自動測試設備ATE(Automatic Test Equipment)中，在解壓時，必須把原測試集中的所有向量還原出來。電路中，塊計數器用來進行種子位數的計數，指示LFSR展開得到的當前數據是控制位還是數據位，其初始值是種子的長度，當塊計數器計數為0時，控制器輸出控制位；位計數器的初始值為目標測試向量的長度；模式計數器用來計算種子數，計數初值是測試向量對應的種子總個數，模式計數器每減1，都會通知ATE向LFSR裝載新的種子。

圖4 電路結構框圖

在測試過程中，模式計數器置為初始值，reset1和reset2信號有效，使塊計數器和位計數器復位。ATE按順序向LFSR裝載種子，每載入一個種子都會通知模式計數器進行減1計數，接著位計數器和塊計數器同時減1計數，塊計數器先減至0，enable信號無效，模式計數器減1；同時控制器將進入測試的種子展開，得到控制位和實際的種子數據；經過若干個周期，位計數器減至0，此時生成一個完整的測試向量，然后根據得到的控制位信息，在當前種子在LFSR中運行周期結束后，地址譯碼器根據控制信息，選通多輸入端LFSR中相應的端口，在相應的LFSR單元中載入下一個種子數據；同時enable信號有效，位計數器和塊計數器復位。重復該過程，直到模式計數器減至0，所有的種子施加完畢。

相對于一般的LFSR編碼方案，硬件結構中的模式計數器和位計數器是必需的，本文方案只增加了一個塊計數器和地址譯碼器，但由于本文方案大幅度縮小了LFSR的度數，因此相比單獨使用LFSR重播種方法硬件開銷更小。

3 完整的綜合過程

基于多輸入端LFSR的測試數據壓縮方案的完整綜合過程可由下面4個步驟組成：

(1)選擇LFSR和期望產生的隨機模式數 N，對初始的N個隨機模式進行故障模擬,確定出偽隨機測試阻尼硬故障集 Fhard，即確定的測試立方集 TD?{0，1，-}n；

(2)選擇合適的度數，選擇不同的特征多項式編碼TD，利用上節中介紹的方法使得所有的測試向量均能編碼成功，得到種子集S，并記錄相應的LFSR；

(3)使用第(2)步中記錄的 LFSR，對種子集 S中的每個種子s(i)生成末態m(i)，得到末態集合M，利用選擇排序策略對S中的種子進行處理排序，最后得到S′；

(4)加載種子進行測試。在測試過程中，處理過的種子集S′經過解壓電路,由該LFSR展開成目標測試集。

4 實驗結果分析

為了驗證本方法的有效性，采用了ISCAS-89標準電路中的 s5378、s9234、s13207、s15850、s38417、s38584 電路，并使用測試生成工具預先計算的測試向量進行實驗。本方案實驗結果如表1所示，其中，需要說明的是第3欄是種子位數，即LFSR的度數；第4欄是壓縮后的總位數TE；第5欄為壓縮率，壓縮率的計算公式為(TD－TE)/TD，在編碼過程中，壓縮率會受到種子編碼順序的影響。為了與國際上同類壓縮方法進行比較，第6欄列出了混合碼[9]的實驗結果。由表1看出，本文方案的壓縮效果要優于混合碼。

表1 本文方案的實驗結果及與混合碼的比較

本文實現了一種應用LFSR編碼的測試壓縮數據新方法。在這種方法中，利用了當前LFSR狀態和種子的相關性，對載入過程中的種子需要改變的位進行控制，而對種子不需要改變的位保留，從而提高了編碼效率和數據壓縮率，并在實驗中得到了較好的結果。與同類測試數據壓縮方法相比，這種方法能很好地提高編碼效率。

[1]MOURAD S.Principle of testing electronic system[M].John Wiley&Sons，Inc，2000.

[2]梁華 國，HELLEBRAND S，WUNDERLICH H J.一 種基于折疊計數器重新播種的確定自測試方案[J].計算機研究與發展，2001，38(3)：931-937.

[3]HELLEBRAND S，RAJSKI J，TARNICK S，et al.Built-in test for circuits with scan based on reseeding of multiplepolynomial linear feedback shift registers[J].IEEE Trans on Comp，1995，44(2)：223-233.

[4]KOENEMANN B.LFSR-coded test patterns for scan designs[C].Proceedings of the european test conference.Munich，germany，1991：237-242.

[5]梁華國，蔣翠云.使用雙重種子壓縮的混合模式自測試[J].計算機研究與發展，2004，41(1)：214-220.

[6]ABRAMOVICI M，BREUER M，FRIEDMAN A.Digital systems testing and testable design[M].New York：Computer Science Press，1990.

[7]GREGORY G，ABRAHAM P.The traveling salesman problem and its variations[M].Dordrecht Hardbound：Kluwer Academic Publishers，2002.

[8]KOENEMANN B，BARNHART C，KELLER B，et al.A smart BIST variant with guaranteed encoding[C].Proceedings of VLSI test symposium，Marina Del Rey，CA，2001：325-330.

[9]WURTENBERGER A，TAUTERMANN C S，HELLEBRAND S.A hybrid coding strategy for optimized test data compression[C].Proceedings of IEEE International test conference，Charlotte，NC，2003：451-459.