李 瑞，吳 瓊

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

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

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

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

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

（2）統(tǒng)計(jì)游程并轉(zhuǎn)化為浮點(diǎn)數(shù)。將預(yù)處理后的測(cè)試數(shù)據(jù)按照0類型游程劃分，當(dāng)游程長(zhǎng)度超過(guò)了十進(jìn)制能表達(dá)的最大值9時(shí)，即將長(zhǎng)游程切分為多個(gè)短游程。依此可將測(cè)試數(shù)據(jù)表示為一段整數(shù)序列，默認(rèn)在第一個(gè)整數(shù)后添加小數(shù)點(diǎn)，其余整數(shù)依次連接作為小數(shù)部分，則游程長(zhǎng)度序列轉(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ù)并輸出分子和分母，最后將測(cè)試數(shù)據(jù)存儲(chǔ)為分子、分母和原始測(cè)試數(shù)據(jù)的長(zhǎng)度。下面以36 位測(cè)試數(shù)據(jù)100010 0X0000 XXX010 0011XX 001000 100XX1 為例展示分?jǐn)?shù)存儲(chǔ)游程規(guī)律的過(guò)程。首先，將無(wú)關(guān)位X全部填充為0，統(tǒng)計(jì)游程長(zhǎng)度對(duì)應(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。接下來(lái)，查找分?jǐn)?shù)字典有9/23 ≈0.391304 34，于是將上述測(cè)試數(shù)據(jù)存儲(chǔ)為9、23和36三個(gè)整數(shù)。

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

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

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

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

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

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

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

為了更好說(shuō)明本方案的編碼過(guò)程，列舉一個(gè)測(cè)試集進(jìn)行分?jǐn)?shù)編碼，如圖1所示，而圖2展示了直接使用FDR編碼和本方案編碼的結(jié)果。從圖1可以看出，本文壓縮方法將原始測(cè)試集存儲(chǔ)為7、23和64三位整數(shù)，再使用FDR 對(duì)三位整數(shù)編碼，對(duì)應(yīng)的編碼結(jié)果為110001 11101001 111110000010，將64 位測(cè)試集壓縮為26位，與原始測(cè)試集相比減少了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)由一個(gè)有限狀態(tài)機(jī)FSM、兩個(gè)M位寄存器、一個(gè)k位計(jì)數(shù)器、一個(gè)log2k位計(jì)數(shù)器和一個(gè)快速浮點(diǎn)除法器實(shí)現(xiàn)，如圖3所示。

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

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

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

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

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

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

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

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

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

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

表1 本方案的壓縮效果

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

4 總結(jié)

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