混合分?jǐn)?shù)與FDR碼的測試數(shù)據(jù)壓縮方法

李 瑞，吳 瓊

（安慶師范大學(xué) 數(shù)理學(xué)院，安徽 安慶 246133）

隨著超大規(guī)模集成電路集成度的日益提高、芯片尺寸的逐步縮小，電路的復(fù)雜性急劇增加。復(fù)雜的電路給系統(tǒng)芯片的測試工作帶來了極大挑戰(zhàn)。測試過程中快速增加的數(shù)據(jù)量對自動測試設(shè)備的存儲空間、運(yùn)行頻率等方面提出了更高要求，在不顯著增加測試時間和測試成本的情況下，系統(tǒng)芯片的測試工作變得越來越困難。為緩解上述問題，國內(nèi)外學(xué)者提出了許多有效減少測試數(shù)據(jù)量的方法，一般分為三類：測試集緊縮[1]、內(nèi)建自測試[2]和測試數(shù)據(jù)壓縮[3-10]。（1）測試集緊縮：該技術(shù)使用軟件調(diào)整并緊縮測試數(shù)據(jù)中的無關(guān)位，以此來減少測試向量的個數(shù)，節(jié)省了硬件開銷和測試時間，其缺點(diǎn)是會降低非模型故障的覆蓋率。（2）內(nèi)建自測試：該方法的思想是預(yù)先在芯片上設(shè)計測試向量生成器，使得測試向量能直接在芯片上生成，并在電路內(nèi)部獨(dú)立完成測試工作，脫離了對昂貴的自動測試設(shè)備的依賴。但是由于很多IP核沒有預(yù)先設(shè)計測試向量生成器，若考慮內(nèi)建自測試，則需插入電路重新設(shè)計，代價昂貴。（3）測試數(shù)據(jù)壓縮：主要采用無損壓縮的方法對測試數(shù)據(jù)進(jìn)行壓縮，得到較小體量的數(shù)據(jù)后再傳輸?shù)阶詣訙y試設(shè)備中，同時設(shè)計解壓電路，還原出與原始測試向量一一對應(yīng)的數(shù)據(jù)。該技術(shù)降低了對測試設(shè)備的要求，也能很好地保護(hù)知識產(chǎn)權(quán)。無損的編碼壓縮方案是測試數(shù)據(jù)壓縮領(lǐng)域的研究熱點(diǎn)，經(jīng)典的編碼壓縮方法有Golomb碼[3]、FDR碼[4]、交替連續(xù)長度碼[5]、Variable-Tail碼[6]、混合定變長碼[7]等，這些方案的優(yōu)點(diǎn)是壓縮效率較高且解壓結(jié)構(gòu)簡單。根據(jù)游程出現(xiàn)的規(guī)律，本文提出一種混合分?jǐn)?shù)與FDR碼的測試數(shù)據(jù)壓縮方法，使編碼更加靈活，減少了需要編碼的數(shù)據(jù)量，同時也節(jié)省了測試時間。

1 混合分?jǐn)?shù)與FDR碼的壓縮方法

1.1 分?jǐn)?shù)存儲游程規(guī)律的方法

（1）數(shù)據(jù)預(yù)處理。待測電路生成的測試數(shù)據(jù)由0，1和無關(guān)位X組成，其中X可以被任意填充為0或1，不影響測試數(shù)據(jù)的故障覆蓋率，因此，在測試之前首先選擇適應(yīng)性填充的方法來填充無關(guān)位X，使得到的游程序列能更符合分?jǐn)?shù)存儲規(guī)律。

（2）統(tǒng)計游程并轉(zhuǎn)化為浮點(diǎn)數(shù)。將預(yù)處理后的測試數(shù)據(jù)按照0類型游程劃分，當(dāng)游程長度超過了十進(jìn)制能表達(dá)的最大值9時，即將長游程切分為多個短游程。依此可將測試數(shù)據(jù)表示為一段整數(shù)序列，默認(rèn)在第一個整數(shù)后添加小數(shù)點(diǎn)，其余整數(shù)依次連接作為小數(shù)部分，則游程長度序列轉(zhuǎn)化為浮點(diǎn)數(shù)。

（3）轉(zhuǎn)化為分?jǐn)?shù)。利用Stern-Brocot Tree生成所有分母小于100的真分?jǐn)?shù)，建立分?jǐn)?shù)字典。在字典中輸入浮點(diǎn)數(shù)，查找與浮點(diǎn)數(shù)相等的分?jǐn)?shù)并輸出分子和分母，最后將測試數(shù)據(jù)存儲為分子、分母和原始測試數(shù)據(jù)的長度。下面以36 位測試數(shù)據(jù)100010 0X0000 XXX010 0011XX 001000 100XX1 為例展示分?jǐn)?shù)存儲游程規(guī)律的過程。首先，將無關(guān)位X全部填充為0，統(tǒng)計游程長度對應(yīng)的整數(shù)序列為0，3，9，1，3，0，4，3，4，在第一位整數(shù)后添加小數(shù)點(diǎn)，其余整數(shù)依次連接作為小數(shù)部分，得到浮點(diǎn)數(shù)0.391 304 34。接下來，查找分?jǐn)?shù)字典有9/23 ≈0.391304 34，于是將上述測試數(shù)據(jù)存儲為9、23和36三個整數(shù)。

1.2 混合分?jǐn)?shù)與FDR編碼的原理

FDR編碼是一種基于0游程的編碼壓縮方法，對長游程測試數(shù)據(jù)的壓縮非常有效，然而它對短游程數(shù)據(jù)的壓縮效果較差，有可能出現(xiàn)負(fù)壓縮的情況。因此，本方法不再直接存儲游程長度，而是根據(jù)游程出現(xiàn)的規(guī)律將其存儲方式分為兩類：（1）若根據(jù)測試數(shù)據(jù)中0和1出現(xiàn)的規(guī)律，可以把游程長度的整數(shù)序列轉(zhuǎn)化為浮點(diǎn)數(shù)，且能在分?jǐn)?shù)字典中找出與浮點(diǎn)數(shù)對應(yīng)的分?jǐn)?shù)，則只需存儲分子、分母和原始測試數(shù)據(jù)長度，再對其進(jìn)行FDR編碼即可。（2）若字典中不存在與浮點(diǎn)數(shù)對應(yīng)的分?jǐn)?shù)，則游程序列不符合轉(zhuǎn)化為分?jǐn)?shù)的規(guī)律，此時直接使用FDR編碼。混合分?jǐn)?shù)與FDR碼測試數(shù)據(jù)壓縮方法的具體流程如下。

步驟1級聯(lián)測試集中的全部向量記作TD；

步驟2讀取一個測試向量，自適應(yīng)填充無關(guān)位X，使用十進(jìn)制的游程長度表示法將待測數(shù)據(jù)轉(zhuǎn)換成若干個整數(shù)序列，每段序列的原始數(shù)據(jù)長度記為l；

步驟3遍歷整數(shù)序列，在第一位整數(shù)后添加小數(shù)點(diǎn)，其余整數(shù)作為小數(shù)部分，則整數(shù)序列轉(zhuǎn)換為浮點(diǎn)數(shù)f，若字典中存在與浮點(diǎn)數(shù)對應(yīng)的分?jǐn)?shù)，且使得n/m≈f，則存儲n，m，l三個整數(shù)；若不存在與浮點(diǎn)數(shù)對應(yīng)的分?jǐn)?shù)，則直接存儲整數(shù)序列；

步驟4使用FDR編碼步驟3中的所有整數(shù)；

步驟5重復(fù)執(zhí)行步驟2至步驟4，直至測試數(shù)據(jù)集為空編碼時結(jié)束并計算壓縮率。

為了更好說明本方案的編碼過程，列舉一個測試集進(jìn)行分?jǐn)?shù)編碼，如圖1所示，而圖2展示了直接使用FDR編碼和本方案編碼的結(jié)果。從圖1可以看出，本文壓縮方法將原始測試集存儲為7、23和64三位整數(shù)，再使用FDR 對三位整數(shù)編碼，對應(yīng)的編碼結(jié)果為110001 11101001 111110000010，將64 位測試集壓縮為26位，與原始測試集相比減少了38位，壓縮率為59.37%。由圖2可知，本文方法只需編碼7、23和64三位整數(shù)，編碼數(shù)據(jù)量遠(yuǎn)小于直接使用FDR編碼的數(shù)據(jù)量，并產(chǎn)生了更高的壓縮率。

圖1 編碼實(shí)例

圖2 編碼壓縮結(jié)果比較

2 解壓電路

解壓結(jié)構(gòu)由一個有限狀態(tài)機(jī)FSM、兩個M位寄存器、一個k位計數(shù)器、一個log2k位計數(shù)器和一個快速浮點(diǎn)除法器實(shí)現(xiàn)，如圖3所示。

圖3 解壓結(jié)構(gòu)

圖中，bit_in是FSM的輸入，信號（en）用于輸入編碼數(shù)據(jù)。counter_in作為FSM的輸出，用于將代碼字的前綴或后綴移位到k位計數(shù)器中，shift信號用于將數(shù)據(jù)移位。log2k位計數(shù)器用來計算前綴和后綴的長度，從而識別代碼字組別。dec1信號用于控制計數(shù)器遞減，rs1和rs2是計數(shù)器的復(fù)位信號，用來表示計數(shù)器完成計數(shù)。M位寄存器分別存儲n，m和l的值，快速浮點(diǎn)除法器用于將分?jǐn)?shù)轉(zhuǎn)化為對應(yīng)浮點(diǎn)數(shù)的整數(shù)序列。解壓過程如下：

（1）FSM 控制bit_in 向k位計數(shù)器提供前綴，當(dāng)bit_in 輸入0 時前綴輸入結(jié)束，將計數(shù)器的值存入M位寄存器1；計數(shù)器重置為0后向k位計數(shù)器提供后綴，再將計數(shù)器的值加在M位寄存器1中，記寄存器1的數(shù)值為n；

（2）再次執(zhí)行步驟（1），將計數(shù)器的值分別存入M位寄存器1（記為m）和M位寄存器2（記為l）中；

（3）將n和m移入快速浮點(diǎn)除法器中，計算對應(yīng)的浮點(diǎn)數(shù)并輸出整數(shù)序列；

（4）根據(jù)整數(shù)序列以及原始數(shù)據(jù)長度l輸出0 s，解碼結(jié)束時在0 s后跟1；

（5）重復(fù)以上步驟直至解壓完畢。

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

為驗(yàn)證本文壓縮方法的有效性，選取MintestATPG生成的測試向量集，分別對ISCAS89標(biāo)準(zhǔn)電路中的7個時序電路進(jìn)行實(shí)驗(yàn)，壓縮效果如表1所示。為了進(jìn)一步驗(yàn)證可行性，表2給出了本方案與國內(nèi)外其他編碼方案壓縮結(jié)果的對比情況。

由表1可以看出，本文壓縮方法對ISCAS89標(biāo)準(zhǔn)電路中大多數(shù)電路的壓縮效果較好，壓縮率相對穩(wěn)定，變化范圍為45.9%～75.3%，平均壓縮率為61.0%。其中對s5378和s9234兩個電路的壓縮率較低，原因是該電路中的短游程數(shù)據(jù)較多，數(shù)據(jù)規(guī)律性較差，不易使用分?jǐn)?shù)存儲。由表2看出，對于同樣的測試數(shù)據(jù)，本文方法的平均壓縮率為61.0%，相較于FDR碼提高了11.9%，相較于Golomb碼提高了17.6%，與二分算法壓縮方案相比提高了16.9%。實(shí)驗(yàn)表明本文壓縮方法能提高測試數(shù)據(jù)壓縮率、減少測試時間和硬件開銷。

表1 本方案的壓縮效果

表2 本方案與其他編碼方案壓縮率的比較

4 總結(jié)

集成電路測試是工業(yè)生產(chǎn)中必不可少的一步，為降低測試成本，本文提出了一種混合分?jǐn)?shù)與FDR碼的測試數(shù)據(jù)壓縮方法。首先，將游程出現(xiàn)的規(guī)律存儲為分?jǐn)?shù)，分別編碼分子、分母和原始測試數(shù)據(jù)的長度，突破了短游程測試數(shù)據(jù)對編碼壓縮效果的限制，同時減少了需要編碼的數(shù)據(jù)量；再對不能轉(zhuǎn)換為分?jǐn)?shù)的游程直接進(jìn)行FDR編碼，該方法使編碼更加靈活且能進(jìn)一步減少編碼數(shù)據(jù)量。實(shí)驗(yàn)結(jié)果表明，該方法對ISCAS89 標(biāo)準(zhǔn)電路的平均壓縮率為61.0%，能有效壓縮測試數(shù)據(jù)量，降低芯片的測試成本，并且解壓電路簡單，無需引入額外的硬件開銷。因此，本文提出的混合分?jǐn)?shù)與FDR碼測試數(shù)據(jù)壓縮方法在系統(tǒng)芯片測試領(lǐng)域中具有一定的應(yīng)用前景。