基于三態信號的改進游程編碼壓縮方法

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

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

0 概述

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

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

1 基于三態信號的游程編碼壓縮方法

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

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

1.1 三態信號檢測

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

圖2 三態信號檢測電路Fig.2 Tri-state signal detection circuit

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

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

1.2 測試數據預處理

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

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

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”用白色表示，無關位“X”用灰色表示。

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

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

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

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

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

1.3.2 游程編碼表的編碼規則

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

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

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

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

傳統游程編碼方式根據游程長度依次對應相應碼字，而本文為充分利用碼字，分別使出現頻率高和低的游程長度對應采用短和長的碼字，并對不曾出現過的游程長度不設置碼字，從而保證高頻設短碼、低頻設長碼、零頻不設碼的原則。

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

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

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

1.3.3 編碼流程

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

下文以測試集S為例進行說明，如圖7（a）所示。假設經過遍歷后測試集中最優段長為8，以段長為8進行編碼，整個編碼過程中將不涉及變長分段的編碼過程。因為測試集中“0”的個數為8，“1”的個數為4，所以參考位為“1”，首先進行非參考位填充，將無關位“X”填充為非參考位“0”，然后從該測試集中劃分出一個段長為8的子測試向量S0。該測試集被分成新的子向量S0和剩下的測試集S，如圖7（b）所示。該子向量中第1個、第2個、第3個參考位的游程長度依次為0、2、1。編碼到第1個子測試向量的最后一位“0”時，因為該位不是參考位，所以退到最近的一個參考位的下一個非參考位，即S0中倒數第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

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

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

2 解壓結構

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

圖8 解壓結構Fig.8 Decompression structure

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

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

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

3 實驗結果與分析

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

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

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

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

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

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

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

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

4 結束語

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