基于LFSR狀態(tài)相關(guān)的測試數(shù)據(jù)壓縮方法*

毛 蔚 ，梁華國 ，程旺燕

(1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 合肥230009；2.合肥工業(yè)大學(xué) 電子科學(xué)與應(yīng)用物理學(xué)院，安徽 合肥230009)

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

在傳統(tǒng)的測試生成方法中，測試生成過程長、測試復(fù)雜程度高、故障覆蓋率低。一種高效、經(jīng)濟(jì)的測試方法是使用內(nèi)建自測試(BIST)[2-3]來代替?zhèn)鹘y(tǒng)的方法，它通過在芯片內(nèi)部集成少量的邏輯電路實(shí)現(xiàn)對(duì)整個(gè)電路的測試。內(nèi)建自測試(BIST)是近年來研究的熱點(diǎn)，而使用線性反饋移位寄存器(LFSR)[4]生成測試模式的偽隨機(jī)內(nèi)建自測試，已經(jīng)被學(xué)術(shù)界、工業(yè)界廣泛地使用。

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

1 編碼理論及實(shí)現(xiàn)策略

1.1 LFSR編碼

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

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

圖1 n位反饋移位寄存器的結(jié)構(gòu)

在LFSR重播種方法中，求解LFSR種子時(shí)，通過選定的特征多項(xiàng)式，建立狀態(tài)轉(zhuǎn)移矩陣，結(jié)合測試向量建立方程組，若方程有解，則編碼成功；否則編碼失敗。

1.2 方案實(shí)現(xiàn)策略

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

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

圖2 種子的處理

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

1.3 選擇排序策略

對(duì)于種子Si=b0b1…bN-1，bi表示各種子位數(shù)，LFSR運(yùn)行Si后的末態(tài)為：

種子集S按上述方法生成對(duì)應(yīng)的末態(tài)集合M。為使得在載入下一個(gè)種子時(shí)需改變的寄存器數(shù)量最少，需找到一個(gè)種子與此時(shí)LFSR末態(tài)相同位盡可能多，即海明距離盡可能小。

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

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

1.4 帶多輸入端口的LFSR

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

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

圖3 多輸入移位寄存器

2 硬件結(jié)構(gòu)

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

圖4 電路結(jié)構(gòu)框圖

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

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

3 完整的綜合過程

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

表1 本文方案的實(shí)驗(yàn)結(jié)果及與混合碼的比較

本文實(shí)現(xiàn)了一種應(yīng)用LFSR編碼的測試壓縮數(shù)據(jù)新方法。在這種方法中，利用了當(dāng)前LFSR狀態(tài)和種子的相關(guān)性，對(duì)載入過程中的種子需要改變的位進(jìn)行控制，而對(duì)種子不需要改變的位保留，從而提高了編碼效率和數(shù)據(jù)壓縮率，并在實(shí)驗(yàn)中得到了較好的結(jié)果。與同類測試數(shù)據(jù)壓縮方法相比，這種方法能很好地提高編碼效率。

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

[2]梁華 國，HELLEBRAND S，WUNDERLICH H J.一 種基于折疊計(jì)數(shù)器重新播種的確定自測試方案[J].計(jì)算機(jī)研究與發(fā)展，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].計(jì)算機(jī)研究與發(fā)展，2004，41(1)：214-220.

[6]ABRAMOVICI M，BREUER M，F(xiàn)RIEDMAN 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.