改進Tent混沌序列的數字電路BIST技術

朱 敏，王石記，楊春玲

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

改進Tent混沌序列的數字電路BIST技術

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

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

針對目前數字電路規模變大，測試困難的特點，提出了一種基于改進Tent混沌序列的數字電路BIST技術.采用改進混沌Tent映射模型構建硬件電路并產生具有白噪聲特性的“0－1”隨機序列作為數字電路的自動測試生成圖形，利用CRC特征電路分析輸出響應，并得到混沌序列的測試響應特征碼，通過特征碼的不同來檢測故障.研究表明，本文方法易于BIST技術實現，相比于普通M序列性能優越，能夠得到更高的故障檢測率和故障隔離率，適合于FPGA等大規模可編程邏輯電路的自動測試.

時序電路;Tent混沌0－1序列;內建自測試;循環冗余碼

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

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

本文提出的基于改進Tent混沌序列的數字電路BIST技術，即在數字電路系統中增加Tent混沌序列發生硬件電路作為自動測試圖形生成電路，并采用CRC響應分析電路作為輸出響應特征分析.文中給出了針對ISCAS’85標準測試組合邏輯電路c17和ISCAS’89標準測試時序電路s27的測試結果.研究表明，本文提出的方法易于BIST技術的實現，可應用于一般的數字邏輯電路，包括FPGA等VLSI的內核功能的自動測試.

1 改進Tent混沌序列數字電路BIST技術

1.1 改進的Tent映射混沌特性分析

Tent映射模型［10－12］:

其中0

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

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

圖1 初始值為150的改進Tent混沌映射過程

圖2 改進Tent映射的隨機特性

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

圖3 改進Tent映射初值相差10－11時迭代圖

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

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

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

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

圖4 “0－1”隨機序列的自相關性與互相關性

1.2 改進Tent混沌映射的硬件電路BIST技術實現

本文利用改進的Tent混沌映射在FPGA中實現BIST測試，其結構框圖如圖5所示.

圖5 數字系統實現BIST結構框圖

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

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

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

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

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

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

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

2 實驗及分析

2.1 組合電路測試分析

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

圖6 混沌測試電路BIST結構框圖

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

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

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

表1 c17測試結果

2.2 時序電路測試分析

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

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

表2 s27測試結果

表3 s27混沌迭代次數與檢測率關系

3 結語

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

［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，FUJIWARA 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］ 顧德均.航空電子裝備修理理論與技術［M］.北京:國防工業出版社，2001:19－20.

［6］ 丁瑾.可靠性與可測性分析設計［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.

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

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

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

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

(編輯 趙麗瑩)