包清明， 潘紅兵

(海軍工程大學(xué)電子工程學(xué)院，武漢 430033)

0 引言

在現(xiàn)代測(cè)試中，內(nèi)建自測(cè)試(Built-in Self Test，BIST)［1－2］技術(shù)是滿足系統(tǒng)可測(cè)試性和故障診斷要求的重要手段。BIST的主要部分包括測(cè)試序列生成器，測(cè)試響應(yīng)分析器和測(cè)試控制器等。其中測(cè)試序列生成器主要有確定性測(cè)試序列生成器，偽隨機(jī)測(cè)試序列生成器以及混合測(cè)試序列生成器。確定性測(cè)試生成主要是通過確定性算法，如 D 算法［3］、PODEM 算法［4］等，計(jì)算出電路的全部故障測(cè)試序列，然后將其存儲(chǔ)到BIST的ROM中。它能產(chǎn)生最小測(cè)試序列集，施加測(cè)試時(shí)間較短，故障覆蓋率高，測(cè)試效率較高。但其序列的計(jì)算過程復(fù)雜，在電路規(guī)模較大時(shí)，用于存儲(chǔ)測(cè)試序列的硬件開銷較大。

偽隨機(jī)測(cè)試序列生成器通常采用線性反饋移位寄存器(Linear Feedback Shift Register，LFSR)來實(shí)現(xiàn)［5］，其所需成本小，硬件實(shí)現(xiàn)簡(jiǎn)單可靠。但是偽隨機(jī)測(cè)試生成方法的故障覆蓋率難以提高，且不能解決難測(cè)故障的問題。為了克服線性反饋移位寄存器作為偽隨機(jī)碼生成器的缺點(diǎn)，提出了重播種LFSR和ROM混合測(cè)試生成結(jié)構(gòu)［6－7］，用 LFSR 產(chǎn)生加權(quán)隨機(jī)測(cè)試碼［8］等混合測(cè)試序列生成方案。然而加權(quán)測(cè)試生成法需要存儲(chǔ)數(shù)量較大的測(cè)試加權(quán)集，硬件開銷大，重播種方案中種子產(chǎn)生的偽隨機(jī)測(cè)試序列是等長(zhǎng)的，其冗余隨機(jī)測(cè)試序列仍較多。

針對(duì)此問題，本文提出一種變周期重復(fù)播種測(cè)試生成法。該方法可以有效地跳過測(cè)試生成序列中的冗余序列，縮短總的測(cè)試序列長(zhǎng)度，在保證故障覆蓋率的條件下，減少測(cè)試施加的時(shí)間，從而提高測(cè)試效率。

1 LFSR結(jié)構(gòu)周期重播種測(cè)試生成

由于所需成本小，硬件實(shí)現(xiàn)簡(jiǎn)單可靠，基于LFSR結(jié)構(gòu)的測(cè)試向量生成器已經(jīng)成為BIST的主要結(jié)構(gòu)。其方法對(duì)于組合電路和時(shí)序電路測(cè)試都適用。常用具有最大周期的LFSR產(chǎn)生的m序列作為偽隨機(jī)測(cè)試激勵(lì)，此時(shí)該LFSR的特征多項(xiàng)式為一本原多項(xiàng)式，在伽羅華域GF(2)上該多項(xiàng)式表示為

測(cè)試向量產(chǎn)生電路由一個(gè)n(n＜m)觸發(fā)器單元的LFSR和一個(gè)用于存儲(chǔ)種子的片外或片上的只讀內(nèi)存器(Read Only Memory，ROM)構(gòu)成，如圖1所示。其中hi(i=1，2，…，n－1)表示反饋線的接通情況，若hi=1則表示反饋線接通;若hi=0則表示不接通反饋線?？刂齐娐窂腞OM中周期性地向LFSR裝載種子，由種子產(chǎn)生被測(cè)電路(Circuit Under Test，CUT)期望的確定性測(cè)試向量。

圖1 n位的LFSR示意圖Fig.1 The sketch map of n bit LFSR

若假設(shè) y1(i)，y2(i)，…，yn(i)為 n 位寄存器 A1，A2，…，An在i時(shí)刻狀態(tài)的輸出值，而y1(i+1)，y2(i+1)，…，yn(i+1)表示LFSR輸入一次時(shí)鐘信號(hào)后在i+1時(shí)刻狀態(tài)，則輸出向量Y={y1，y2，…，yn}在時(shí)鐘前后輸出下應(yīng)有關(guān)系

若假設(shè)LFSR的初始狀態(tài)為0狀態(tài)，從ROM中輸出的種子序列為 s={s1，s2，…，sk}，則 y1(1)在 i=1 時(shí)刻輸出的值為;在i=1 時(shí)刻LFSR輸出的測(cè)試序列為y(1)={y1(1)，y2(1)，…，yn(1)}=。

由于文中測(cè)試序列計(jì)算均是模2運(yùn)算，且y(1)中僅s1是未知量，故簡(jiǎn)記為函數(shù)y1=f(s1)，則y(1)={f(s1)，y1(0)，…，yn－1(0)}。

在第二個(gè)時(shí)鐘周期輸入s2后可知

同理推論可知，在n個(gè)時(shí)鐘周期后，LFSR的輸出序列為

此時(shí)若假定被測(cè)電路期望的一個(gè)測(cè)試輸入序列為z={z1，z2，…，zn}，則

此方程是一個(gè)模2運(yùn)算方程組，有且僅有唯一解［9］s={s1，s2，…∈(0，1)，i∈(1，2，…，n )}。該方程組解的含義是，通過ROM中產(chǎn)生的種子序列都可以使LFSR從某個(gè)無關(guān)輸出序列跳轉(zhuǎn)到任意一個(gè)指定的輸出序列z。若在第j(j＜n)時(shí)刻LFSR的輸出序列s=z， 則說明此時(shí)的輸入種子即為方程組的解。

2 變周期重播種的偽隨機(jī)測(cè)試生成

已經(jīng)證明對(duì)于n階的基于本原多項(xiàng)式的LFSR，只需要在其輸入端輸入m(m≤n)位的控制位，一定能夠?qū)FSR中現(xiàn)有的測(cè)試矢量跳轉(zhuǎn)到另一個(gè)指定的測(cè)試矢量。因此重復(fù)播種測(cè)試生成法針對(duì)隨機(jī)測(cè)試的缺點(diǎn)，通過在ROM中存儲(chǔ)序列生成的種子，此種子加載至LFSR后展開成所需的測(cè)試序列的思路來加快故障覆蓋率的提高。但其生成的偽隨機(jī)測(cè)試序列長(zhǎng)度是不變的，即每次間隔相同的周期加載種子，其中包含較多的冗余測(cè)試序列，降低了測(cè)試加載效率。

在變周期重復(fù)播種測(cè)試序列生成中，每個(gè)種子所產(chǎn)生的偽隨機(jī)測(cè)試序列長(zhǎng)度通過一個(gè)模可變計(jì)數(shù)器來控制，跳過其無效冗余的測(cè)試序列。變周期重復(fù)播種測(cè)試生成結(jié)構(gòu)如圖2所示。

圖2 變周期重復(fù)播種測(cè)試生成Fig.2 Generation of variable-cycle reseeding test

變周期重播種測(cè)試序列生成器包括一個(gè)?？捎?jì)數(shù)器ROM和LFSR。與定長(zhǎng)的重播種測(cè)試生成僅僅存儲(chǔ)種子信息不同的是，在ROM中同時(shí)存儲(chǔ)了種子S和序列長(zhǎng)度信息L。

變周期重播種測(cè)試生成器的工作過程為:ROM將長(zhǎng)度信息L和計(jì)算好的種子S分別加載到計(jì)數(shù)器和LFSR。在clk時(shí)鐘信號(hào)的作用下，計(jì)數(shù)器開始計(jì)數(shù)，LFSR同時(shí)開始產(chǎn)生測(cè)試序列。當(dāng)LFSR產(chǎn)生的序列長(zhǎng)度達(dá)到預(yù)定的L長(zhǎng)度的時(shí)候，計(jì)數(shù)器計(jì)滿溢出，溢出信號(hào)控制ROM加載下一個(gè)種子到LFSR中，加載下一個(gè)序列長(zhǎng)度信息到計(jì)數(shù)器中。這樣每次在LFSR產(chǎn)生的測(cè)試序列長(zhǎng)度達(dá)到有效測(cè)試序列的長(zhǎng)度后，通過計(jì)數(shù)器的溢出控制信號(hào)來重新加載種子和序列信息，從而能有效地跳過冗余測(cè)試序列。其跳過冗余偽隨機(jī)測(cè)試序列的原理如圖3所示，圖中，陰影部分為有效測(cè)試序列，空白部分為冗余測(cè)試序列。每個(gè)種子擴(kuò)展后的長(zhǎng)度序列可受計(jì)數(shù)器的控制，在其產(chǎn)生冗余序列之前，通過ROM加載的種子使序列跳轉(zhuǎn)到下一段序列開始。這樣每部分種子的測(cè)試序列長(zhǎng)度將不一致，不再是以相同的周期加載種子，而是根據(jù)序列信息長(zhǎng)度變周期地加載種子信息到LFSR。

圖3 跳過冗余偽隨機(jī)測(cè)試序列的原理Fig.3 The principle of skipping the redundant test patterns

以ISCAS85標(biāo)準(zhǔn)測(cè)試電路中選取的典型電路C880為例，通過對(duì)其分析可知，若采用4次播種的方式分組測(cè)試序列，則其序列長(zhǎng)度信息如圖4所示。

圖4 C880電路測(cè)試序列長(zhǎng)度信息Fig.4 The length information of test sequence in C880 circuit

變長(zhǎng)重播種測(cè)試生成方法在其截取冗余測(cè)試序列的時(shí)候，未能有效截掉(2799，2816)，(4032，4096)區(qū)間的冗余序列。由理論分析可知，在極端情況下，最大會(huì)有(L/4－1)長(zhǎng)度的冗余序列不能被有效截掉，或是以丟失有效測(cè)試序列的代價(jià)來截掉冗余測(cè)試序列，這點(diǎn)從文獻(xiàn)［10］中可以得到驗(yàn)證。

本文通過設(shè)計(jì)一個(gè)?？勺冇?jì)數(shù)器來控制種子的加載。由于對(duì)每個(gè)種子產(chǎn)生的序列長(zhǎng)度信息從ROM中加載到計(jì)數(shù)器，在種子生成的序列長(zhǎng)度達(dá)到預(yù)定的長(zhǎng)度后，計(jì)數(shù)器控制ROM重新加載種子，從而能有效地跳過將冗余序列，加快測(cè)試序列生成的速度。

變周期重播種的LFSR結(jié)構(gòu)測(cè)試生成的基本思想是通過計(jì)數(shù)器來控制種子生成序列的長(zhǎng)度，從而跳過冗余序列。但是當(dāng)每個(gè)種子隨后生成的有效測(cè)試序列長(zhǎng)度L分布不均勻，導(dǎo)致部分有效序列較長(zhǎng)，部分有效序列較短，因此，計(jì)數(shù)器的最大計(jì)數(shù)模數(shù)必須滿足序列中長(zhǎng)度最大的一個(gè)，而在其他計(jì)數(shù)模式下以較小的計(jì)數(shù)模計(jì)數(shù)。當(dāng)有效序列長(zhǎng)度較大時(shí)，要求計(jì)數(shù)器的最大計(jì)數(shù)位數(shù)較多，從而造成計(jì)數(shù)器硬件開銷過大。若通過在序列中增加種子的數(shù)量來縮短每個(gè)種子測(cè)試生成的有效序列長(zhǎng)度，則會(huì)使存儲(chǔ)種子和長(zhǎng)度信息L的ROM資源消耗過高，因此需要合理分組測(cè)試序列，降低計(jì)數(shù)器的硬件開銷。

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

變周期重播種測(cè)試生成方法選取ISCAS85電路中的典型測(cè)試電路。選取C880電路為分析樣本，以便于與文獻(xiàn)［10］測(cè)試生成方法做類比。其模擬分析結(jié)果如表1所示。

表1中:fcv表示故障覆蓋率;fd表示檢測(cè)到的故障個(gè)數(shù);LD表示定長(zhǎng)測(cè)試序列長(zhǎng)度;LV表示文獻(xiàn)［10］中采用的變長(zhǎng)重復(fù)播種測(cè)試生成方法得到的測(cè)試序列;LE表示本文方法的測(cè)試序列。

由表1的結(jié)果可知，采用變周期重播種測(cè)試生成的方法通過計(jì)數(shù)器能很好地跳過冗余的測(cè)試序列(2799，3071)，(4032，4095)，(4096，5120)，大大縮短了測(cè)試序列的總長(zhǎng)度，縮短測(cè)試時(shí)間。相比于定周期重播種測(cè)試生成方法，總序列長(zhǎng)度減少1357/5120≈26.5%，提高了測(cè)試效率。同時(shí)由于該方法能很好地保留有效的測(cè)試向量，保證其故障覆蓋率不會(huì)下降。相比于文獻(xiàn)［10］的方法其總測(cè)試序列長(zhǎng)度也有一定的壓縮。

事實(shí)上，該電路的測(cè)試序列減少還可以進(jìn)一步地減少。由表1中的分析可知，在種子1開始，每個(gè)向量所能檢測(cè)的故障個(gè)數(shù)開始明顯下降，因此其第2，3，4組序列中還有進(jìn)一步的分組可以減少的空間。理論分析可知，該電路的最小測(cè)試序列集長(zhǎng)度小于其全部故障數(shù)994，如若能將全部的冗余測(cè)試序列長(zhǎng)度跳過，則測(cè)試序列縮短幅度大于(5120－994)/5120≈80.59%，因此其測(cè)試序列縮短還有很大空間。

對(duì)ISCAS85和ISCAS89中的部分典型測(cè)試電路進(jìn)行模擬分析，其測(cè)試序列長(zhǎng)度都得到精簡(jiǎn)，結(jié)果如表2所示。

表2 ISCAS85和ISCAS89中典型電路模擬分析結(jié)果Table 2 The analysis result of circuit from ISCAS85 and ISCAS89

對(duì)比定長(zhǎng)周期播種的測(cè)試生成方法可知，該方法是以額外的硬件消耗為代價(jià)的。如果分組越多，則能跳過的冗余序列越多，其測(cè)試效率越高，但是所對(duì)應(yīng)的?？勺冇?jì)數(shù)器的硬件開銷以及存儲(chǔ)序列長(zhǎng)度消耗的ROM存儲(chǔ)的資源開銷過大。例如，S27電路規(guī)模是21門，若采用該方法則計(jì)數(shù)器本身的硬件開銷大于60門，此時(shí)此方法顯然不具備可行性。若是分組過少，則會(huì)導(dǎo)致其中的冗余序列過多，改進(jìn)效果不明顯。因此在此方法針對(duì)實(shí)際電路運(yùn)用時(shí)候，應(yīng)該根據(jù)電路規(guī)模和測(cè)試復(fù)雜長(zhǎng)度合理設(shè)計(jì)其BIST測(cè)試生成模塊，以均衡硬件資源開銷。

分析本文的方法可知，其計(jì)數(shù)器和測(cè)試序列長(zhǎng)度信息存儲(chǔ)均需要消耗一定的硬件資源，因此，對(duì)于小規(guī)模的電路而言，其硬件增加開銷規(guī)模相對(duì)也會(huì)較大，在應(yīng)用中不具有可行性。但是對(duì)規(guī)模較大的電路，其硬件的消耗的相對(duì)比例較小，而測(cè)試效率卻得到大幅度提高，此時(shí)此測(cè)試方法是可行的。

4 結(jié)論

針對(duì)偽隨機(jī)測(cè)試生成中包含的冗余測(cè)試序列較多測(cè)試效率不高的問題，提出了變周期重播種的LFSR結(jié)構(gòu)的測(cè)試生成方法，利用模可變計(jì)數(shù)器來控制測(cè)試序列長(zhǎng)度，并分析了其設(shè)計(jì)思路。然后運(yùn)用該方法對(duì)ISCAS85和ISCAS89中的部分測(cè)試電路進(jìn)行模擬分析。由分析結(jié)果可知，該方法在針對(duì)較大電路的時(shí)候，在保證電路的故障覆蓋率的條件下，能以較少比例的硬件開銷跳過冗余測(cè)試序列，減少總測(cè)試序列長(zhǎng)度。對(duì)于一般較大規(guī)模的電路，其序列長(zhǎng)度平均減少20%～50%，減少了測(cè)試施加時(shí)間，提高重播種測(cè)試效率。

［1］CHEN C，GUPTA S.BIST test pattern generators for two pattern testing-theory and design algorithms［J］.IEEE Trans.on Computers，1996，45(3):257-269.

［2］WUNDERLICH H J.Accumulator based deterministic BIST.［C］//Proc.IEEE Int.Test Conf.Washington，DC.1998:412-421.

［3］ROTH J P.Diagnosis of automata failures:A calculus and a method［J］.IBM J.Res.Develop，1966，10(7):278-291.

［4］GOEL P.An implicit enumeration algorithm to generate tests for combinational logic circuits［J］.IEEE Trans.Compute，1981，30(2):215-222.

［5］向東.數(shù)字系統(tǒng)測(cè)試及可測(cè)性設(shè)計(jì)［M］.北京:科學(xué)出版社，1997.

［6］LI Lijian，MIN Yinghua.An efficient BIST using LFSRROM architecture［EB/OL］.［2005-10-12］http://ieeexplore.ieee.org/ie15/7181/19338/00893645.pdf.

［7］KAGARIS D.Multiple seed TPG structures［J］.IEEE Transactions on Computers，2003，52(12):1633-1639.

［8］PROMERANZ I，REDDY S M.3-Weight pseudo random test generation based on a deterministic test set for combinational and sequential circuits［J］.IEEE Trans.On CAD，1998，12(6):1050-1058.

［9］胡晨，許舸夫，張哲，等.一種基于受控LFSR的內(nèi)建自測(cè)試結(jié)構(gòu)及其測(cè)試矢量生成［J］.電路與系統(tǒng)學(xué)報(bào)，2002，17(3):13-16.

［10］張建勝，黃維康，唐璞山.變長(zhǎng)重復(fù)播種測(cè)試碼生成方法［J］.復(fù)旦學(xué)報(bào):自然科學(xué)版，2006，45(4):517-522.