陳 田，周 洋，任福繼，3，安 鑫，趙滬隱

（1.合肥工業(yè)大學計算機與信息學院，合肥 230009；2.合肥工業(yè)大學情感計算與先進智能機器安徽省重點實驗室，合肥 230009；3.德島大學工學部，日本德島770-8506）

0 概述

隨著集成電路技術(shù)的發(fā)展，晶體管的特征尺寸不斷縮小，芯片集成度與頻率日益提高，使得集成電路芯片設(shè)計對數(shù)據(jù)測試的要求越來越嚴格，并對自動測試設(shè)備（Automatic Test Equipment，ATE）的I/O通道數(shù)及ATE數(shù)據(jù)傳輸率提出了更高要求［1］。然而，由于大量的測試數(shù)據(jù)增加了測試時間和功耗，因此測試數(shù)據(jù)壓縮技術(shù)［2-3］應(yīng)運而生。

測試數(shù)據(jù)壓縮方法主要分為基于線性解壓［4］、廣播掃描［5］和編碼［6］的壓縮方法3類?；诰€性解壓的測試數(shù)據(jù)壓縮方法是先將測試數(shù)據(jù)壓縮成較小的種子集，測試時將種子集傳輸?shù)骄€性解壓器中擴展成測試向量進行測試。該方法壓縮率較高，但只有當其原始測試集中包含很少的確定位時，才能生成合適的種子?；趶V播掃描的測試數(shù)據(jù)壓縮方法通過一個共同的輸出結(jié)構(gòu)將相同的測試數(shù)據(jù)扇出到不同的掃描鏈中［7］。該方法較簡單，但是每一次數(shù)據(jù)扇出時都需要單獨連線，并要求原始測試數(shù)據(jù)具有較高的相容性?；诰幋a的測試數(shù)據(jù)壓縮方法利用壓縮算法對原始測試數(shù)據(jù)集進行高度壓縮，將壓縮后相對較小的測試集存入ATE，測試時利用芯片上的解壓電路進行無損解壓得到測試數(shù)據(jù)。該方法具有良好的適應(yīng)性，但壓縮率較低。近年來，研究人員陸續(xù)提出基于Golomb編碼［8］、FDR編碼［9］、EFDR編碼［10］、FRPRL編碼［11］等的測試數(shù)據(jù)壓縮方法。傳統(tǒng)基于編碼的測試數(shù)據(jù)壓縮方法使用二值邏輯“0”和“1”進行編碼，文獻［12］指出ATE可支持高阻態(tài)（Hi-Z）信號的傳輸，“0”、“1”和“Hi-Z”被稱為三態(tài)信號，因此文獻［13］提出基于字典的三態(tài)信號編碼壓縮方案。本文受此啟發(fā)，提出一種基于三態(tài)信號的改進游程編碼壓縮方法，先對測試集進行預(yù)處理，降低測試集中確定位的比例，再根據(jù)游程長度進行變長分段編碼壓縮，并使用三態(tài)信號編碼標志位。

1 基于三態(tài)信號的游程編碼壓縮方法

為減少測試數(shù)據(jù)量，本文提出一種基于三態(tài)信號的游程編碼壓縮方法，整體流程如圖1所示。首先對原始測試集進行預(yù)處理；其次填充測試集的無關(guān)位；然后利用基于三態(tài)信號的改進游程編碼壓縮方法對填充后的測試集進行編碼壓縮，并將編碼壓縮后的測試集存入ATE；最后通過設(shè)計解壓電路對ATE中存儲的壓縮數(shù)據(jù)進行無損解壓。

圖1 基于三態(tài)信號的游程編碼壓縮流程Fig.1 Procedure of run length coding compression based on tri-state signal

1.1 三態(tài)信號檢測

本文方法的研究重點為通過片上解壓電路檢測三態(tài)信號并將三態(tài)信號轉(zhuǎn)化為二值邏輯信號用于數(shù)據(jù)測試。文獻［14］提出一種三態(tài)信號檢測電路，如圖2所示，其中VDD為電源工作電壓。該電路由6個晶體管組成，硬件結(jié)構(gòu)簡單、開銷小且操作便捷。

圖2 三態(tài)信號檢測電路Fig.2 Tri-state signal detection circuit

雖然ATE能存儲三態(tài)信號，但由于被測電路不能識別三態(tài)信號，因此本文在ATE輸出后增加了一個三態(tài)信號識別電路。該三態(tài)信號識別電路的真值表如表1中“轉(zhuǎn)換前”部分所示，可以看出：data2為“1”時，輸入信號是“0”；data2為“0”時，輸入信號是“1”或者“Hi-Z”。為了能僅讀取1位數(shù)據(jù)就知道該輸入信號為高阻態(tài)，本文在解壓結(jié)構(gòu)和有限狀態(tài)機（Finite State Machine，F(xiàn)SM）之間增加了一個轉(zhuǎn)換電路，使得data2’為“0”時，輸入信號一定為“Hi-Z”，真值表如表1中“轉(zhuǎn)換后”部分所示。在本文方法中，將含有三態(tài)信號的壓縮向量從ATE輸出到片上三態(tài)信號檢測電路中，并將三態(tài)信號轉(zhuǎn)化成二值信號，同時通過解碼器生成與原始測試向量相容的測試模式，最終將解碼后的測試向量輸入掃描鏈中進行測試。

表1 三態(tài)信號解壓輸出轉(zhuǎn)換前后的真值表Table 1 True value table of tri-state signal decompression output before and after conversion

1.2 測試數(shù)據(jù)預(yù)處理

原始測試集包含“0”、“1”和“X”，其中：“0”和“1”為確定位；“X”對測試結(jié)果不產(chǎn)生影響，被稱為無關(guān)位。在將其輸入掃描鏈時，無關(guān)位可根據(jù)需要設(shè)置成“0”或“1”。根據(jù)測試向量中確定位的不同，兩個測試向量之間的關(guān)系分為相容、反相相容和不相容3種。在兩個測試向量中：如果對應(yīng)位的位置都為“0”（“1”），或者一個為“0”（“1”），另一個為“X”，那么稱這兩個向量相容；如果對應(yīng)位的位置一個為“0”（“1”），另一個為“1”（“0”）或者“X”，那么稱這兩個向量反相相容；如果兩個測試向量中既存在相容又存在反相相容，那么稱這兩個向量不相容。

為降低測試集中確定位的比例，本文使用部分輸入精簡技術(shù)［15］對原始數(shù)據(jù)集進行預(yù)處理。部分輸入精簡技術(shù)將相容（反相相容）的測試向量合并成一個測試向量，測試時進行一個扇出處理，并保留全是無關(guān)位的測試向量，但不作任何處理，其主要原因為將測試集相容或者反相相容的測試向量合并成一個向量可減少確定位，從而降低測試集中確定位的比例。

1.3 游程編碼壓縮方法

1.3.1 游程選取

若字符串中確定位“1”后面有多個“0”，或者確定位“0”后面有多個“1”，則稱具有該特性的字符串為游程，可抽象地表示為0n1或1n0，其中，0n表示n個“0”，1n表示n個“1”，n為該游程長度，即兩個相同確定位之間的距離。為更直觀地展示確定位“0”和“1”在原始測試集中的分布，本文對ISCAS-89基準電路中的s5378電路測試集繪制更直觀的“0”、“1”和“X”分布圖，如圖3所示，測試集中的“0”用黑色表示，“1”用白色表示，無關(guān)位“X”用灰色表示。

圖3 s5378原始測試數(shù)據(jù)位置分布Fig.3 Position distribution of the original test data about s5378

從圖3可以看出，兩個相同的確定位不是集中在一起，就是兩兩相隔很遠，而且很多確定位之間的距離相同。利用該特性，本文設(shè)計一種基于確定位距離（游程長度）的編碼壓縮方法。由于測試集中確定位一般非常稀少，且其在測試集中所占比例為1%～5%［16］，如果僅統(tǒng)計在測試集中所占比例小于5%的確定位的游程長度，則將減少存儲信息量，而如果完整存儲“0”和“1”的游程長度，則將浪費很多存儲空間，因此為進一步減少存儲位數(shù)，本文只存儲“0”或“1”一種確定位的游程長度。一般的游程編碼方法是對固定的一種確定位或者同時對兩種確定位的游程進行編碼，但會在一定程度上增加游程長度的種類數(shù)，因此本文對需要編碼的確定位采取靈活的選取方式，并將該確定位稱為參考位，具體定義如下：

定義1令A(yù)=(S0，S2，…，Sn-1)為某一測試集，其中Sn表示測試向量中的第n個測試向量，集合T（A）為測試集A中所有確定位的集合。若T（A）中“1”的數(shù)量小于“0”，則令參考位為“1”；若T（A）中“0”的數(shù)量小于“1”，則令參考位為“0”。

對于測試集中的無關(guān)位，本文進行與參考位相反的確定位填充。經(jīng)統(tǒng)計，s5378電路的測試集中“0”有2 968位，“1”有3 537位，因此，s5378的參考位是“0”，同時將所有的無關(guān)位填充為非參考位“1”。最終s5378測試集只需要存儲2 968個“0”的游程長度，占整個測試集的12.49%，從而明顯減少了所需存儲的信息量。圖4為對s5378測試集中無關(guān)位填充“1”后的分布圖，可以直觀看出“0”所占的比例很小。

圖4 s5378填充測試數(shù)據(jù)位置分布Fig.4 Position distribution of the filling test data about s5378

1.3.2 游程編碼表的編碼規(guī)則

傳統(tǒng)游程編碼表是根據(jù)游程長度依次進行編碼，游程長度越長，排序越靠后，碼字也越長。然而，編碼時雖然有些游程長度并不存在，但也會在編碼表中占用相應(yīng)的碼字，這就可能會增加其后面的碼字長度。因此，傳統(tǒng)游程編碼方式未能充分利用短碼字的優(yōu)勢，而且不能有效利用所有的二進制集合。

圖5是s5378測試集中參考位“0”的游程長度出現(xiàn)頻率分布圖，橫坐標為“0”的游程長度，縱坐標為該游程長度的出現(xiàn)次數(shù)?？梢钥闯觯纬涕L度的出現(xiàn)次數(shù)均集中于1～10，其中游程長度為1出現(xiàn)了1 033次，游程長度為2出現(xiàn)了473次。根據(jù)游程長度的出現(xiàn)頻率分布，本文重新設(shè)計了三態(tài)信號游程編碼表。新編碼表中的碼字為不同長度的二進制全排列，長度從0開始，直到能表示完游程長度的所有種類數(shù)時為止。因為碼字長度不統(tǒng)一，所以本文使用三態(tài)信號作為標志位，每個碼字都以“Hi-Z”作為后綴，為方便后文的敘述，將“Hi-Z”簡記為“Z”，最終碼字依次為｛Z，0Z，1Z，00Z，01Z，…｝。根據(jù)以上規(guī)則可得出新的s5378編碼表，如表2所示。

圖5 s5378游程長度的出現(xiàn)頻率分布Fig.5 Occurrence frequency distribution of the run length about s5378

表2 s5378編碼表Table 2 Coding table about s5378

傳統(tǒng)游程編碼方式根據(jù)游程長度依次對應(yīng)相應(yīng)碼字，而本文為充分利用碼字，分別使出現(xiàn)頻率高和低的游程長度對應(yīng)采用短和長的碼字，并對不曾出現(xiàn)過的游程長度不設(shè)置碼字，從而保證高頻設(shè)短碼、低頻設(shè)長碼、零頻不設(shè)碼的原則。

通過觀察s5378編碼表發(fā)現(xiàn)，游程長度從36到140都只出現(xiàn)了1次，其在編碼過程中出現(xiàn)次數(shù)少，編碼字段長，利用率低，占用空間多，對于編碼壓縮非常不利。為進一步提高編碼表中碼字的利用率，本文為整個測試向量設(shè)計一種變長分段壓縮方法。變長分段壓縮就是先從整個測試向量中劃分出一個給定長度的測試向量，并記錄該子向量中所有參考位的游程長度。如果測試向量最后的測試數(shù)據(jù)不是參考位，例如對于從測試集中劃分出的子向量S=｛101XXX｝，其最后一位為無關(guān)位，該無關(guān)位將被填充為非參考位。由于本文只對參考位進行編碼，因此最后的3位無關(guān)位無法被編碼。如果最后一位無法被編碼，那么就將離該位最近的參考位的下一位作為起始位，重新設(shè)定給定長度的向量為子向量并進行重新編碼。如果子向量全是非參考位，即最近的參考位不存在，那么設(shè)定該子向量游程長度為給定長度。在整個測試集編碼完成后，將每個子向量的游程長度合并成一個編碼表，根據(jù)所有游程長度的出現(xiàn)頻率設(shè)置編碼表，并對該編碼表進行存儲。

為找出變長分段壓縮的最優(yōu)段長，本文從段長為1一直遍歷到測試集長度為止，從中找出最優(yōu)的子向量段長進行編碼壓縮。由于尋找最優(yōu)段長是測試前的準備工作，因此不會增加測試時間。圖6為變長分段編碼壓縮流程。經(jīng)過測試可知，s5378的最優(yōu)段長為43，此時字典位數(shù)為283，相比不進行變長分段壓縮的字典位數(shù)（940）約減少了70%，而且游程長度也更集中地出現(xiàn)在多個固定游程長度上，使得壓縮率由整體壓縮的66.629%提升到68.085%。

圖6 變長分段編碼壓縮流程Fig.6 Procedure of variable length segment coding compression

1.3.3 編碼流程

本文首先統(tǒng)計出測試集中游程長度出現(xiàn)次數(shù)較少的確定位，記為參考位，進行非參考位填充；然后從段長為1開始進行變長分段編碼，直到段長為測試集長度時停止，找出其中的最優(yōu)段長，并統(tǒng)計在該最優(yōu)段長下進行變長分段編碼中所有參考位的游程長度出現(xiàn)次數(shù)，根據(jù)游程長度出現(xiàn)頻率高低進行排序并生成編碼表；最后根據(jù)編碼表進行編碼。

下文以測試集S為例進行說明，如圖7（a）所示。假設(shè)經(jīng)過遍歷后測試集中最優(yōu)段長為8，以段長為8進行編碼，整個編碼過程中將不涉及變長分段的編碼過程。因為測試集中“0”的個數(shù)為8，“1”的個數(shù)為4，所以參考位為“1”，首先進行非參考位填充，將無關(guān)位“X”填充為非參考位“0”，然后從該測試集中劃分出一個段長為8的子測試向量S0。該測試集被分成新的子向量S0和剩下的測試集S，如圖7（b）所示。該子向量中第1個、第2個、第3個參考位的游程長度依次為0、2、1。編碼到第1個子測試向量的最后一位“0”時，因為該位不是參考位，所以退到最近的一個參考位的下一個非參考位，即S0中倒數(shù)第2個“0”，然后以該位作為起始位重新劃分段長為8的下一個子向量S1，如圖7（c）所示。因為該子向量是8個“0”，所以第4個“1”的游程長度為8，然后將剩下的測試集劃分為第3個子測試向量S2，如圖7（d）所示，因此第5個、第6個“1”的游程長度為0、6。

圖7 編碼示例Fig.7 Coding example

統(tǒng)計出這些游程長度的出現(xiàn)次數(shù)，并對游程長度按照出現(xiàn)頻率高低設(shè)計編碼表，最終的示例編碼表如表3所示。編碼后的結(jié)果為｛Z0Z00Z1ZZ01Z｝，壓縮后的測試數(shù)據(jù)共有12位。為便于對比，本文使用游程編碼重新對該測試集進行一次壓縮，因為該測試集中有較多的短游程且沒有連續(xù)的“1”游程，所以本文選FDR碼進行編碼。該測試集根據(jù)“1”游程可劃分為001、021、011、081、061，所以按照FDR編碼表編碼為00100001110010110000，共20位?？梢钥闯?，本文方法的壓縮效果優(yōu)于FDR碼，主要原因為本文不僅設(shè)計了根據(jù)游程長度的出現(xiàn)頻率來編碼的三態(tài)碼字，而且采用變長分段壓縮編碼方法使游程長度進一步集中于出現(xiàn)頻率高的碼字。

表3 示例編碼表Table 3 Example coding table

2 解壓結(jié)構(gòu)

圖8為本文方法的解壓結(jié)構(gòu)，壓縮過的測試集存儲在ATE中，其中，ATE_clk、SCK為時鐘信號，SE為使能信號，SI為輸入數(shù)據(jù)。測試時數(shù)據(jù)由ATE通過測試數(shù)據(jù)輸入（Test Data Input，TDI）端口輸出到解壓結(jié)構(gòu)進行解壓，然后將解壓后的數(shù)據(jù)（即原始數(shù)據(jù)）輸出到掃描鏈上進行掃描測試。

圖8 解壓結(jié)構(gòu)Fig.8 Decompression structure

解壓過程主要分成以下兩個步驟：

1）三態(tài)信號轉(zhuǎn)換為二值信號。ATE將包含高阻態(tài)信號的壓縮后的測試數(shù)據(jù)輸出到三態(tài)檢測電路中，三態(tài)檢測電路將“Hi-Z”進行轉(zhuǎn)換輸出，輸出信號經(jīng)過轉(zhuǎn)換電路轉(zhuǎn)換成data1’、data2’并將其輸入到FSM中。

2）解壓數(shù)據(jù)并將其輸入到掃描鏈中進行測試。若FSM收到的data2’信號為“1”，則表示收到的是“0”或者“1”信號，說明正在讀入游程長度的值，直接將該信號輸入到移位寄存器中；若FSM收到的data2’信號為“0”，則表示收到的是“Hi-Z”信號，說明游程長度已經(jīng)讀取完畢，此時移位寄存器將游程長度輸入到編碼表存儲器中，找到編碼表中對應(yīng)的游程長度并輸出到計數(shù)器，由計數(shù)器將“0”或者“1”信號輸入到掃描鏈中進行測試。

3 實驗結(jié)果與分析

為驗證本文方法的有效性，采用Mintest集［17］對ISCAS-89基準電路中的6個電路進行實驗。表4為實驗電路的基本信息。本文方法的測試壓縮算法程序由Java實現(xiàn)，并在Core i7 3.4 GHz CPU、8 GB內(nèi)存的PC機上進行驗證。

表4 實驗電路信息Table 4 Experimental circuit information

壓縮率計算公式如式（1）所示。本文方法對Mintest集上壓縮結(jié)果如表5所示，其中，前4列為測試集經(jīng)過壓縮處理后的基本信息，第5列為使用本文方法的測試數(shù)據(jù)壓縮率。表6為本文方法與Golomb方法［8］、FDR方法［9］、EFDR方法［10］、FRPRL方法［11］、文獻［13］方法、文獻［18］方法、9C方法［19］、BM方法［20］和文獻［21］方法的測試數(shù)據(jù)壓縮率對比，其中，本文方法與文獻［13］方法均使用三態(tài)信號對測試集進行壓縮，其余方法均使用二值信號對測試集進行壓縮?？梢钥闯觯疚姆椒ǖ臏y試數(shù)據(jù)壓縮率要優(yōu)于其他方法，主要原因為其對測試集進行預(yù)處理能有效降低測試集中確定位的比例，為后續(xù)壓縮提供了良好的基礎(chǔ)條件，并且壓縮時使用三態(tài)信號作為標志位，將編碼字段由定長變?yōu)樽冮L，而且根據(jù)游程長度的出現(xiàn)頻率進行編碼，能更充分地利用編碼表。

表5 本文方法對Mintest集的壓縮結(jié)果Table 5 Compression results of the Mintest set by the proposed method

表6 10種方法的測試數(shù)據(jù)壓縮率比較Table 6 Comparison of test data compression rate of ten methods %

本文使用Synopsys公司的DC工具對解壓結(jié)構(gòu)及其對應(yīng)的基準電路進行綜合分析，得到硬件開銷的計算公式如式（2）所示：

表7為本文方法與Golomb方法［8］、FDR方法［9］、EFDR方法［10］、文獻［13］方法、9C方法［19］和BM方法［20］在解壓結(jié)構(gòu)的硬件開銷上的對比。由于本文方法的解壓結(jié)構(gòu)主要是增加了1個三態(tài)信號檢測電路以及1個編碼表存儲器，但三態(tài)信號檢測電路僅由6個晶體管組成，硬件開銷較少，因此其硬件開銷主要集中在編碼表的存儲器上。與同樣需要開辟額外存儲空間的9C和BM方法及同樣基于三態(tài)信號的文獻［13］方法相比，本文方法的硬件開銷更小。

表7 7種方法的硬件開銷比較Table 7 Comparison of hardware overhead of seven methods

4 結(jié)束語

本文提出一種基于三態(tài)信號的改進游程編碼壓縮方法。該方法對原始測試集進行部分輸入精簡處理，降低了測試集中確定位的比例并減少參考位的數(shù)量，且對經(jīng)過預(yù)處理的測試集根據(jù)游程長度進行變長分段處理，從而找出最優(yōu)段長，同時按照游程長度的出現(xiàn)頻率對最優(yōu)段長下的參考位設(shè)置編碼表進行編碼壓縮，提高了編碼表中碼字的利用率。實驗結(jié)果表明，本文方法相比同類壓縮方法具有更高的壓縮率，且硬件開銷沒有明顯增加。但由于本文方法僅針對二維芯片上的測試數(shù)據(jù)進行壓縮處理，因此下一步將在三維芯片的基礎(chǔ)上研究測試芯核的排布和測試數(shù)據(jù)的調(diào)度問題。