朱 敏，王石記，楊春玲

(1.哈爾濱工業(yè)大學(xué)電氣工程及自動化學(xué)院，哈爾濱 150001，zhuminhit@163.com;2北京航天測控技術(shù)開發(fā)公司，北京 100041)

改進(jìn)Tent混沌序列的數(shù)字電路BIST技術(shù)

朱 敏1，王石記2，楊春玲1

(1.哈爾濱工業(yè)大學(xué)電氣工程及自動化學(xué)院，哈爾濱 150001，zhuminhit@163.com;2北京航天測控技術(shù)開發(fā)公司，北京 100041)

針對目前數(shù)字電路規(guī)模變大，測試?yán)щy的特點，提出了一種基于改進(jìn)Tent混沌序列的數(shù)字電路BIST技術(shù).采用改進(jìn)混沌Tent映射模型構(gòu)建硬件電路并產(chǎn)生具有白噪聲特性的“0－1”隨機序列作為數(shù)字電路的自動測試生成圖形，利用CRC特征電路分析輸出響應(yīng)，并得到混沌序列的測試響應(yīng)特征碼，通過特征碼的不同來檢測故障.研究表明，本文方法易于BIST技術(shù)實現(xiàn)，相比于普通M序列性能優(yōu)越，能夠得到更高的故障檢測率和故障隔離率，適合于FPGA等大規(guī)?？删幊踢壿嬰娐返淖詣訙y試.

時序電路;Tent混沌0－1序列;內(nèi)建自測試;循環(huán)冗余碼

隨著超大規(guī)模集成電路(VLSI)和可編程邏輯器件(PLD)的發(fā)展，一般的數(shù)字電子系統(tǒng)可以在單獨的一片可編程芯片中實現(xiàn).單片芯片所能實現(xiàn)復(fù)雜設(shè)計的提高和不斷增長的設(shè)計復(fù)雜性，使得數(shù)字電路的測試變得越來越困難.其主要原因一是一般的數(shù)字電路都包括存儲單元，即各種觸發(fā)器、寄存器電路，這些記憶單元不易設(shè)定和檢測，其可控性和可觀測性差［1－4］.二是系統(tǒng)復(fù)雜度增長的同時，芯片的輸入輸出接口相對較少，即可訪問管腳的比重在下降.因此，在數(shù)字電子系統(tǒng)設(shè)計之初需要考慮測試問題，即可測性設(shè)計［5－6］.

內(nèi)建自測試(BIST)技術(shù)為數(shù)字電路測試提供了一種實用的可測性設(shè)計方案.內(nèi)建自測試將測試激勵產(chǎn)生(TPG)電路、測試控制電路和響應(yīng)分析(ORA)電路都嵌入在原電路中［7－9］.

本文提出的基于改進(jìn)Tent混沌序列的數(shù)字電路BIST技術(shù)，即在數(shù)字電路系統(tǒng)中增加Tent混沌序列發(fā)生硬件電路作為自動測試圖形生成電路，并采用CRC響應(yīng)分析電路作為輸出響應(yīng)特征分析.文中給出了針對ISCAS’85標(biāo)準(zhǔn)測試組合邏輯電路c17和ISCAS’89標(biāo)準(zhǔn)測試時序電路s27的測試結(jié)果.研究表明，本文提出的方法易于BIST技術(shù)的實現(xiàn)，可應(yīng)用于一般的數(shù)字邏輯電路，包括FPGA等VLSI的內(nèi)核功能的自動測試.

1 改進(jìn)Tent混沌序列數(shù)字電路BIST技術(shù)

1.1 改進(jìn)的Tent映射混沌特性分析

Tent映射模型［10－12］:

其中0

為便于硬件電路的實現(xiàn)，本文將Tent映射混沌序列進(jìn)行改進(jìn)，其迭代公式為

上述改進(jìn)型Tent混沌迭代的初始值x0= 150，迭代500次的映射過程如圖1所示.

圖1 初始值為150的改進(jìn)Tent混沌映射過程

圖2 改進(jìn)Tent映射的隨機特性

圖2為初值x0= 150，迭代次數(shù)為500的Tent混沌模型的隨機特性圖.可以看出Tent混沌模型迭代值遍歷( 0，999)空間，說明其具有很好的隨機特性.圖3為初值相差10－11時，在迭代大約50次后，兩個混沌序列X1，X2將完全不同.因此可以看出，只要初值稍加修改，就可得到完全不同的序列.因此，本文提出的改進(jìn)的Tent混沌序列能產(chǎn)生比M序列更多更為廣泛應(yīng)用的隨機序列.

圖3 改進(jìn)Tent映射初值相差10－11時迭代圖

考慮到FPGA內(nèi)核電路是純數(shù)字電路，并結(jié)合Tent混沌序列的上述特性，所加的測試激勵需要為“0 －1”序列［13－15］，本文改進(jìn) Tent映射，得到改進(jìn)的混沌Tent映射模型的“0－1”隨機序列.

由于改進(jìn)Tent映射迭代值在( 0，999)空間是遍歷的且均勻分布，因此改進(jìn)的“0－1”混沌序列中“0”和“1”分布也是均勻的，滿足Golomb提出的隨機序列公設(shè)條件中0和1均衡分布的條件.序列的自相關(guān)函數(shù)為

式(4)中si與si+k是由同一初值所產(chǎn)生的相差K個間隔點數(shù)的序列.式(5)中si與s′i+K是不同初值所產(chǎn)生的相差K個間隔點數(shù)的序列.圖4(a)為改進(jìn)Tent混沌二進(jìn)制序列的自相關(guān)特性圖，序列的初始值為x0= 150，圖中間隔K從0到2 000，序列長度為5 000.圖4(b)為改進(jìn)Tent混沌互相關(guān)特性圖，序列分別是由初始值x0=150和x0=151所產(chǎn)生的不同序列之間互相關(guān)性仿真.

本文提出的基于改進(jìn)的Tent混沌序列的“0－1”隨機序列具有非常好的自相關(guān)和互相關(guān)特性，其自相關(guān)特性類似于δ函數(shù)，具有白噪聲的特性，且互相關(guān)值非常小，特性也接近于白噪聲.結(jié)合混沌序列的初值敏感性，只需要改變初值就可以產(chǎn)生特性很好的任意長度的隨機序列，這種特性適合作為數(shù)字電路的自動測試圖形生成電路.

圖4 “0－1”隨機序列的自相關(guān)性與互相關(guān)性

1.2 改進(jìn)Tent混沌映射的硬件電路BIST技術(shù)實現(xiàn)

本文利用改進(jìn)的Tent混沌映射在FPGA中實現(xiàn)BIST測試，其結(jié)構(gòu)框圖如圖5所示.

圖5 數(shù)字系統(tǒng)實現(xiàn)BIST結(jié)構(gòu)框圖

圖中混沌算法測試圖形生成電路采用改進(jìn)的Tent混沌映射迭代算法.利用硬件描述語言實現(xiàn)式(2)中的迭代運算.為節(jié)省硬件資源，式中的乘法運算可以通過移位運算和加減運算來實現(xiàn).算法描述如下:

Step1:初始化，x(i)取初始值x0;

Step2:if(x(i)≥333)，則x(i+1)=1499－x(i)－(x(i)?1)，進(jìn)入Step 4，否則進(jìn)入Step3;(其中“?”表示右移操作.)

Step3:x(i+1)=(x(i)?1)+x(i);(其中“?”表示左移操作.)

Step4:將當(dāng)前的x(i+1)賦值給下一次迭代運算的x(i);

Step5:判斷是否到指定的迭代次數(shù)N，如果是就結(jié)束運行，并輸出x(i)，其中i=1， 2，…N，否則返回Step2繼續(xù)執(zhí)行.

將混沌算法產(chǎn)生的序列加載在被測電路CUT(Circuits Under Test)的輸入端，在CUT的輸出端得到響應(yīng)序列.利用數(shù)據(jù)通信中CRC校驗數(shù)據(jù)傳輸?shù)脑?，將CRC作為響應(yīng)特征分析電路，其硬件通過線性反饋移位寄存器(LFSR)來實現(xiàn).

2 實驗及分析

2.1 組合電路測試分析

以標(biāo)準(zhǔn)組合測試電路ISCAS’85中的c17作為被測電路，Tent混沌迭代算法作為測試圖形生成電路，CRC電路用于響應(yīng)分析.被測電路有5個輸入端 G 1，G 2，G 3，G 4，G 5，2 個輸出端 G16 和G 17，中間節(jié)點G 8，G 9，G 12，G 15，其混沌迭代電路BIST的結(jié)構(gòu)如圖6所示.

圖6 混沌測試電路BIST結(jié)構(gòu)框圖

混沌測試圖形生成電路是由混沌算法所構(gòu)建的硬件電路.在測試使能信號test－en和系統(tǒng)時鐘clk的作用下，測試控制狀態(tài)機產(chǎn)生激勵時鐘信號clk－out，將產(chǎn)生的混沌序列通過移位寄存器串行移入被測數(shù)字電路的輸入端.同時通過控制信號sel控制MUX選擇測試激勵，切斷正常數(shù)據(jù)通道data－in.此時混沌序列激勵信號加載在被測電路c17的輸入端，并在輸出端讀出響應(yīng)，暫存在寄存器中.在測試控制控制狀態(tài)機的控制下輸入到CRC電路中進(jìn)行分析并輸出結(jié)果.

被測電路的每個節(jié)點分別可以設(shè)置固定為“0”和“1”的故障，其中 G5－0 和 G5－1分別表示節(jié)點G5發(fā)生固定為“0”和“1”的故障，依此類推.采用CRC多項式x16+x2+1作為響應(yīng)分析電路，得到相應(yīng)的特征碼.經(jīng)過若干次的迭代，特征碼輸出將不同，測試結(jié)果見表1.

表1中給出了分別以LFSR產(chǎn)生的M序列和混沌序列作為測試激勵矢量，在輸出端G16和G17采用CRC響應(yīng)分析電路得到的特征碼.M序列的無故障特征碼為“3A6C/6634”，混沌序列的迭代次數(shù)不同故障特征碼也不同，分別將其列于表中.可以看出，利用LFSR所產(chǎn)生的M序列和混沌序列都能達(dá)到100%檢測故障的目的，混沌序列檢測所有故障的迭代次數(shù)為18次，比M序列長度要短.經(jīng)過足夠的迭代次數(shù)其故障隔離率能達(dá)到90.9%，遠(yuǎn)大于M序列45.5%的隔離率.

表1 c17測試結(jié)果

2.2 時序電路測試分析

標(biāo)準(zhǔn)時序測試電路ISCAS’89中的s27包含一個時鐘控制端CK和4個信號輸入端G 0，G 1，G 2，G3和一個可觀測輸出端G17等17個節(jié)點，因此共有34個故障.與組合電路不同的是時序電路的輸入激勵需要保持被測時序電路時鐘的20個周期，以確保時序電路有足夠的時鐘周期進(jìn)行狀態(tài)轉(zhuǎn)換.

表2給出了s27的測試結(jié)果.其中響應(yīng)輸出采用CRC多項式x16+x2+1作為響應(yīng)分析.表中M序列的無故障特征碼為“9B02”，因此可計算出M序列作為測試激勵的故障檢測率為27/34=79.41%，而 Tent混沌迭代序列最大可達(dá)85.29%.表3給出了針對s27不同迭代次數(shù)故障檢測率的關(guān)系.通過實驗驗證，s27的G2－1，G5－0，G7－0，G10－0 和 G13－0 等 5 個故障為冗余故障，無法檢測.又由于混沌序列具有初值敏感性，即改變初值能夠產(chǎn)生完全不同的隨機序列，因此，在某些情況下可以通過施加不同的混沌序列作為測試激勵來提高故障的檢測率.

表2 s27測試結(jié)果

表3 s27混沌迭代次數(shù)與檢測率關(guān)系

3 結(jié)語

提出了一種基于改進(jìn)的Tent混沌序列的數(shù)字電路BIST技術(shù).該方法通過混沌Tent模型映射生成隨機序列，并構(gòu)建硬件電路作為BIST的測試圖形生成電路，通過CRC響應(yīng)特征分析電路給出故障相應(yīng)的特征碼.實驗研究表明本文提出的改進(jìn)Tent混沌序列具有良好的隨機特性，在經(jīng)過很少的迭代次數(shù)就能產(chǎn)生很高的故障檢測率和故障隔離率.所提出的方法適合于一般的數(shù)字邏輯電路以及FPGA等VLSI的內(nèi)核功能的自動測試.

［1］ FUJIWARA H.A new class of sequential circuits with combinational test generation complexity［J］.IEEE Transactions on Computers， 2000，49(9):895－904.

［2］ YEEOOI C，F(xiàn)UJIWARA H.A new class of sequential circuits with acyclic test generation complexity［C］//International Conference on Computer Design.San Jose:San Jose′State University，2007:425 －431.

［3］ HIKEUNG T，SRINIVAS D，NEWTON R A，el al.Test generation for sequential circuits［J］.IEEE，Transaction on Ransation on Computer-Aided Design， 1988，7(10):1081－1092.

［4］ FU M.Minimal memory inverses of linear sequential circuits［J］.IEEE Transactions on Computers， 1974，C－23(11):1155－1163.

［5］ 顧德均.航空電子裝備修理理論與技術(shù)［M］.北京:國防工業(yè)出版社，2001:19－20.

［6］ 丁瑾.可靠性與可測性分析設(shè)計［M］.北京:北京郵電出版社，1996:106－118.

［7］ SCHOTTEN C，MYER H.Test-point insertion for an area-efficient BIST［C］//Proceedings of International Test Conference.Washington，DC:Aachen Univ of Technol，1995:515 －523.

［8］ CHEN C，GUPTA S K.A methodology to design efficient BIST test pattern generations［C］//Proceedings of International Test Conference.Washington，DC:IEEE Computer Society，1995:814－823.

［9］ AHMAD A A，MITR S，MCCLUSKEY E J.BIST reseeding with very few seeds［C］//VLSI Test Symposium.California:Center for Reliable Comput，Stanford Univ，2003:69－74.

［10］JESSA M.The period of sequences generated by tentlike maps［J］.IEEE Transactions on Circuits and Systems——I:FundamentalTheoryandApplications， 2002，49(1):84 －89.

［11］STOJANOVSKI T，KOCAREV L.Chaos-based random number generators-part I:analysis［J］.Analysis.IEEE Transaction on circuits and systems——I:Fundamental theory and applications， 2001，48(3):281－288.

［12］STOJANOVSKI T，PIHL J，KOCAREV L.Chaosbased random number generators－part II:practical realization［J］.IEEE Transaction on circuits and systems——I:Fundamental theory and applications， 2001，48(3):382－385.

［13］KATZ O，RAMON D A，WAGNER I A.A robust random number generator based on a differential currentmode chaos［J］.IEEE Transactions on very large scale integration(VLSI)systems， 2008，16(12):1677 －1686.

［14］BULS J.Construction of pseudo-random sequences from chaos［C］//COC，St.Petersburg:Univ of Latvia，2000:558－560.

［15］JESSA M.Combined pseudochaotic psudorandom generator［C］//ICSES 2008 International conference on signals and electronic systems.Krakow:Poznan Univ of Technol，2008:257 －260.

BIST technique of digital circuits based on improved tent chaotic sequence

ZHU Min1，WANG Shi-ji2，YANG Chun-ling1

(1.School of Electrical Engineering and Automation，Harbin Institute of Technology，Harbin 150001，China，zhuminhit@163.com;2.Aerospace Measurement＆ Contro，Beijing 100041，China)

This paper proposed a realization method of BIST technique of digital circuits based on improved Tent chaotic sequence to address the problem of testing digital circuits.Random sequence of“0 －1”with white noise characteristics which generated by improved tent chaotic logistic map model hardware implementation is used as automatic test pattern generation(ATPG)of digital circuits.Test response signatures of chaotic sequence are obtained from CRC analysis of output response.It is shown that the method presented in this paper is easy for realization of BIST and has superior performance of higher rate of fault detection and fault isolation than that of M sequence.It is suitable for large-scale FPGA and automatic testing of other programmable logic circuits.

sequential circuits;tent chaotic 0－1 sequence;BIST;CRC

TP702

A

0367－6234(2010)04－0607－05

2009－12－07.

國家自然科學(xué)基金資助項目(60877065);哈爾濱市科

技創(chuàng)新人才研究專項資金(RC2008XK009004).

朱 敏(1981—)，男，博士研究生;

楊春玲(1965—)，女，教授，博士生導(dǎo)師.

(編輯 趙麗瑩)