基于變周期重播種LFSR的測試生成

包清明， 潘紅兵

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

0 引言

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

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

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

1 LFSR結構周期重播種測試生成

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

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

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

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

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

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

在第二個時鐘周期輸入s2后可知

同理推論可知，在n個時鐘周期后，LFSR的輸出序列為

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

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

2 變周期重播種的偽隨機測試生成

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

在變周期重復播種測試序列生成中，每個種子所產生的偽隨機測試序列長度通過一個模可變計數(shù)器來控制，跳過其無效冗余的測試序列。變周期重復播種測試生成結構如圖2所示。

圖2 變周期重復播種測試生成Fig.2 Generation of variable-cycle reseeding test

變周期重播種測試序列生成器包括一個模可計數(shù)器ROM和LFSR。與定長的重播種測試生成僅僅存儲種子信息不同的是，在ROM中同時存儲了種子S和序列長度信息L。

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

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

以ISCAS85標準測試電路中選取的典型電路C880為例，通過對其分析可知，若采用4次播種的方式分組測試序列，則其序列長度信息如圖4所示。

圖4 C880電路測試序列長度信息Fig.4 The length information of test sequence in C880 circuit

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

本文通過設計一個模可變計數(shù)器來控制種子的加載。由于對每個種子產生的序列長度信息從ROM中加載到計數(shù)器，在種子生成的序列長度達到預定的長度后，計數(shù)器控制ROM重新加載種子，從而能有效地跳過將冗余序列，加快測試序列生成的速度。

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

3 實驗結果和分析

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

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

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

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

對ISCAS85和ISCAS89中的部分典型測試電路進行模擬分析，其測試序列長度都得到精簡，結果如表2所示。

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

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

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

4 結論

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

［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)測試及可測性設計［M］.北京:科學出版社，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的內建自測試結構及其測試矢量生成［J］.電路與系統(tǒng)學報，2002，17(3):13-16.

［10］張建勝，黃維康，唐璞山.變長重復播種測試碼生成方法［J］.復旦學報:自然科學版，2006，45(4):517-522.