毛 蔚 ，梁華國(guó) ，程旺燕

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

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

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

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

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

1.1 LFSR編碼

線性反饋移位寄存器常用來(lái)組成測(cè)試向量生成器，它由互連的寄存器和線性邏輯單元(異或門或同或門)組成。一個(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í)，通過(guò)選定的特征多項(xiàng)式，建立狀態(tài)轉(zhuǎn)移矩陣，結(jié)合測(cè)試向量建立方程組，若方程有解，則編碼成功；否則編碼失敗。

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

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

在傳統(tǒng)的LFSR重新播種方法中，分別對(duì)每個(gè)測(cè)試向量進(jìn)行編碼，求解出測(cè)試向量的種子，計(jì)算出種子后，將種子施加到LFSR上，LFSR則利用種子來(lái)生成測(cè)試向量。記LFSR的初始狀態(tài)為S0（即為種子），當(dāng)LFSR運(yùn)行m個(gè)周期(m為掃描鏈的長(zhǎng)度)，種子擴(kuò)展為所需要的向量后，再把掃描鏈的內(nèi)容加載到電路中進(jìn)行測(cè)試。記測(cè)試向量充滿整個(gè)掃描鏈時(shí)的LFSR的下個(gè)狀態(tài)Sm+1為末態(tài)。接著測(cè)試電路又載入另一個(gè)種子，繼續(xù)生成測(cè)試向量。而由于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)相同位盡可能多，即海明距離盡可能小。

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

給定無(wú)向圖 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)化問(wèn)題可表示為：

1.4 帶多輸入端口的LFSR

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

與普通LFSR區(qū)別在于，該結(jié)構(gòu)中使用了多路選擇器MUX，使得不需要額外的邏輯便可以重載LFSR，在從ROM中載入種子時(shí)，所要做的是檢測(cè)種子集中的相應(yīng)的控制位，當(dāng)新種子和LFSR中的寄存器中的內(nèi)容不同時(shí)，重播種電路的輸出在相應(yīng)的多路選擇器的選擇端置1，載入種子位。該方法可以從各個(gè)輸入端in并行輸入，從而可以提高種子的載入效率，節(jié)省測(cè)試時(shí)間和測(cè)試費(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)測(cè)試設(shè)備ATE(Automatic Test Equipment)中，在解壓時(shí)，必須把原測(cè)試集中的所有向量還原出來(lái)。電路中，塊計(jì)數(shù)器用來(lái)進(jìn)行種子位數(shù)的計(jì)數(shù)，指示LFSR展開得到的當(dāng)前數(shù)據(jù)是控制位還是數(shù)據(jù)位，其初始值是種子的長(zhǎng)度，當(dāng)塊計(jì)數(shù)器計(jì)數(shù)為0時(shí)，控制器輸出控制位；位計(jì)數(shù)器的初始值為目標(biāo)測(cè)試向量的長(zhǎng)度；模式計(jì)數(shù)器用來(lái)計(jì)算種子數(shù)，計(jì)數(shù)初值是測(cè)試向量對(duì)應(yīng)的種子總個(gè)數(shù)，模式計(jì)數(shù)器每減1，都會(huì)通知ATE向LFSR裝載新的種子。

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

在測(cè)試過(guò)程中，模式計(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)無(wú)效，模式計(jì)數(shù)器減1；同時(shí)控制器將進(jìn)入測(cè)試的種子展開，得到控制位和實(shí)際的種子數(shù)據(jù)；經(jīng)過(guò)若干個(gè)周期，位計(jì)數(shù)器減至0，此時(shí)生成一個(gè)完整的測(cè)試向量，然后根據(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ù)該過(guò)程，直到模式計(jì)數(shù)器減至0，所有的種子施加完畢。

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

3 完整的綜合過(guò)程

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

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

(2)選擇合適的度數(shù)，選擇不同的特征多項(xiàng)式編碼TD，利用上節(jié)中介紹的方法使得所有的測(cè)試向量均能編碼成功，得到種子集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)行測(cè)試。在測(cè)試過(guò)程中，處理過(guò)的種子集S′經(jīng)過(guò)解壓電路,由該LFSR展開成目標(biāo)測(cè)試集。

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

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

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

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

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

[2]梁華 國(guó)，HELLEBRAND S，WUNDERLICH H J.一 種基于折疊計(jì)數(shù)器重新播種的確定自測(cè)試方案[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]梁華國(guó)，蔣翠云.使用雙重種子壓縮的混合模式自測(cè)試[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.