基于劃分組參考數(shù)的差值編碼壓縮方法

程一飛，吳心竹，吳海峰，鄧博文

（安慶師范大學(xué) 計算機與信息學(xué)院，安徽 安慶 246133）

關(guān)鍵字：測試數(shù)據(jù)壓縮；差值編碼；外建自測試；解碼

目前，集成電路產(chǎn)業(yè)仍在持續(xù)發(fā)展且勢頭不減，估計在未來五年仍將保持熱度。預(yù)計2025年我國芯片規(guī)模將達到1.2萬億元[1]。移動智能終端及芯片的爆發(fā)式增長導(dǎo)致了諸多難題，尤其是芯片測試方面。本文主要針對呈指數(shù)增加的測試數(shù)據(jù)量與有限的ATE（Automatic Test Equipment，自動測試設(shè)備）傳輸帶寬之間的矛盾這一問題，提出一種解決方案。為了解決測試數(shù)據(jù)量劇增的問題，現(xiàn)在普遍使用測試數(shù)據(jù)壓縮技術(shù)。外建自測試技術(shù)是測試數(shù)據(jù)壓縮的一種方法，其特點是無損壓縮，把測試集壓縮成更短的數(shù)據(jù)集并存儲到ATE 上，再通過芯片上的額外解碼電路解壓，使之還原成與原始數(shù)據(jù)集確定位一致的數(shù)據(jù)。傳統(tǒng)的游程編碼[2]是直接針對每段0、1游程長度進行編碼。國外學(xué)者提出了一些基于游程編碼的測試數(shù)據(jù)壓縮的經(jīng)典方法，如Golomb碼[3]和FDR碼[4]。近二十年來，人們陸續(xù)提出了許多新的游程編碼方案，例如，國外學(xué)者提出的混合編碼[5]、AFDR碼[6]、MFDR碼[7]、EFDR碼[8]、交替的等游程長度編碼[9]等。近幾年，國內(nèi)學(xué)者也提出過許多有效的方案，例如，基于三態(tài)信號的改進游程編碼壓縮方法[10]、基于連續(xù)和交替序列的編碼[11]、混合前綴編碼[12]、最大近似相容的分組測試向量相容壓縮方法[13]、基于一位標(biāo)識的混合編碼壓縮方法[14]、最小游程切換點標(biāo)記編碼壓縮方法[15]、應(yīng)用二分算法壓縮測試數(shù)據(jù)[16]、快速查找最佳有理漸近分?jǐn)?shù)的測試數(shù)據(jù)壓縮方法[17]等。但是這些方案僅僅是針對游程長度進行的無損編碼，忽略了每段游程長度之間可能存在的關(guān)聯(lián)性。

本文使用了統(tǒng)計學(xué)中較為經(jīng)典的集中趨勢分析方法[18]，合理考慮了游程長度之間的相關(guān)性。將電路的測試數(shù)據(jù)按游程劃分，并平均分成若干組，且對每一組進行集中趨勢分析，選出該組游程長度中有代表性的值作為參考數(shù)，通常為該組的游程長度平均值、眾數(shù)、中位數(shù)等。將組內(nèi)每段游程的長度與該組參考數(shù)作差，再針對差值進行編碼，可在不增加游程數(shù)量的情況下，有效增加待編碼數(shù)據(jù)中短游程的個數(shù)，減少待編碼的測試數(shù)據(jù)長度，因此編碼后可以得到比使用原始數(shù)據(jù)編碼時更短的代碼字，且可取得很好的壓縮效果。

1 編碼方案

在編碼前，首先將測試數(shù)據(jù)按照雙游程的劃分方法劃分成若干個0游程和1游程。一些經(jīng)典的游程編碼都是采用雙游程劃分，如EFDR編碼[8]、混合前綴編碼[14]、基于一位標(biāo)識的測試數(shù)據(jù)壓縮[14]等，對測試數(shù)據(jù)雙游程劃分能很好地減少用于編碼的游程個數(shù)。采用的編碼方式如表1所示。

表1 差值長度編碼方案

由于差值有正負，因此將編碼的第一位設(shè)定為一個正負標(biāo)識位，用于記錄當(dāng)前游程與參考數(shù)差值的正負類型，如果差值為0或者為正值，則將正負標(biāo)識位設(shè)置為0，以表示當(dāng)前游程的長度大于或等于參考數(shù)的值；同樣地，如果差值為負值，則將正負標(biāo)識位設(shè)置為1，以表示當(dāng)前游程的長度小于參考數(shù)的值。第二位設(shè)定一個游程類型標(biāo)識位，用于記錄當(dāng)前游程類型，若當(dāng)前游程類型為0游程，則游程類型標(biāo)識位記為0；若當(dāng)前游程類型為1游程，則游程類型標(biāo)識位記為1。

每段游程的正負標(biāo)識位、游程類型標(biāo)識位和差值長度的編碼共同組成其游程編碼。而每一組編碼不僅包括當(dāng)前組的參考數(shù)編碼，還包括游程個數(shù)編碼和每段游程編碼。為了達到無損解壓以及進一步精簡解壓電路，將每組參考數(shù)的編碼設(shè)置為一個固定位長度p的二進制編碼（通常將p值設(shè)為5），同樣的，每組游程個數(shù)設(shè)置為一個固定長度為q位的二進制編碼（通常將q的值設(shè)為8）。

假設(shè)給出一組測試數(shù)據(jù)TD=000000000000111111110000000011111111100000000001（48 bit），如果采用經(jīng)典的FDR編碼，經(jīng)過游程劃分后

TD=0000000000001 1 1 1 1 1 1 1 000000001 1 1 1 1 1 1 1 1 00000000001（18個游程序列），編碼后的數(shù)據(jù)

TE=110110 00 00 00 00 00 00 00 110010 00 00 00 00 00 00 00 00 110100（45 bit），如果采用本文方案，采用雙游程劃分后

TD=0000000000001 11111110 00000001 111111110 0000000001（5個游程序列）。

可以得出，劃分后的每段游程長度分別為12、7、7、8、9。若選擇游程長度的眾數(shù)7作為參考數(shù)，可得出每段游程與參考數(shù)的差值分別為5、0、0、1、2。此時可以將參考數(shù)的二進制編碼位數(shù)p值設(shè)為3，即得出當(dāng)前組的參考數(shù)——7的二進制編碼為111；同理，將游程個數(shù)的二進制編碼位數(shù)q值設(shè)為3，即得出當(dāng)前組內(nèi)的游程個數(shù)——5的二進制編碼為101。將編碼后的參考數(shù)二進制、游程個數(shù)二進制以及各段游程的差值編碼相連接，即得出編碼后的數(shù)據(jù)TE=111 101 001011 0100 0000 0101 001000（30 bit）。

若選擇游程長度的中位數(shù)8作為參考數(shù)，即可得出每段游程與參考數(shù)的差值分別為4、-1、-1、0、1。此時可以將參考數(shù)的二進制編碼位數(shù)p值設(shè)為4，即得出當(dāng)前組的參考數(shù)——8的二進制編碼為1000；同理，將游程個數(shù)的二進制編碼位數(shù)q值設(shè)為3，即得出當(dāng)前組內(nèi)的游程個數(shù)——5 的二進制編碼為101。將編碼后的參考數(shù)二進制、游程個數(shù)二進制以及各段游程的差值編碼相連接，即得出編碼后的數(shù)據(jù)TE=1000 101 001010 1101 1001 0100 0001（29 bit）。

可以看出，選擇不同的參考數(shù)，將對測試數(shù)據(jù)產(chǎn)生不同的壓縮效率。當(dāng)選擇眾數(shù)7為參考數(shù)時，較原始數(shù)據(jù)減少了18位，比FDR編碼減少了15位；當(dāng)選擇中位數(shù)8為參考數(shù)時，較原始數(shù)據(jù)減少了19位，比FDR編碼減少了16位。

2 解壓設(shè)計

由壓縮編碼方案可知，差值編碼的第一位為正負標(biāo)識位，表示當(dāng)前游程長度比參考數(shù)大或?。痪幋a的第二位為游程類型，即當(dāng)前游程類型為0游程或1游程，余下部分為差值長度的編碼。假設(shè)一組游程序列以5作為參考數(shù)，差值編碼為1101，根據(jù)編碼規(guī)則可以得出，壓縮前的游程是一個長度短于參考數(shù)的游程序列，且游程類型為1，與原始游程長度差值為1，即原游程是一個長度為4的1游程，因此可還原出原測試數(shù)據(jù)為11110。

解碼可以通過電路實現(xiàn)，在設(shè)計電路時，要記錄每組的參考數(shù)和游程個數(shù)，以及差值編碼部分。本文在EFDR的解壓電路[8]基礎(chǔ)上，增加兩個m位寄存器，用于存儲參考數(shù)的編碼以及每組的游程個數(shù)，并對存儲的數(shù)據(jù)在處理后完成解壓。因此最終設(shè)計的解壓電路是由兩個k位計數(shù)器、一個log2k位計數(shù)器、一個FSM（Finite State Machine，有限狀態(tài)機）、一個異或門，以及兩個m位寄存器構(gòu)成的解碼器。該解碼器獨立于被測電路且大小可變，由于該電路規(guī)模較小，在減少硬件成本上有一定優(yōu)勢，圖1為解碼框。

圖1 解碼框

解碼器信號及其對應(yīng)功能如表2所示。根據(jù)前述方法和編碼表可知，壓縮后數(shù)據(jù)包實際包含若干個組。在每個組的代碼字中，前p位為該組的參考數(shù)二進制編碼，余下編碼的前q位為當(dāng)前組的游程個數(shù)二進制編碼，以上為本組公共部分；余下為若干小組的差值長度編碼數(shù)據(jù)，所述小組內(nèi)編碼依次包括：當(dāng)前游程長度與參考數(shù)的差值正負標(biāo)識位、游程類型、差值長度編碼。接下來對圖1解碼框的主要工作原理做出說明。

表2 解碼器信號及其對應(yīng)功能

首先通過b_in1接收p位數(shù)據(jù)，并向m位寄存器一存入一個游程長度為lp的0游程，該寄存器一用于解壓縮中間值；其次再連續(xù)接收b_in1的q位數(shù)據(jù)，得到二進制形式的當(dāng)前組游程個數(shù)，并存入m位寄存器二作為循環(huán)標(biāo)志；然后按順序繼續(xù)接收2位數(shù)據(jù)，將第一位賦值給ope以作為正負標(biāo)記、第二位賦值給flag 以作為游程類型；接著通過log2k計數(shù)器依次讀取前綴和后綴，在后綴最高位添一位1，將新獲得的二進制轉(zhuǎn)換為十進制后減2，即為原游程長度與參考游程長度的差值絕對值。根據(jù)ope 的正負類型對m位寄存器一中的游程向高位或低位移動，將游程與flag進行異或操作，可獲得解壓后游程；重復(fù)以上所有流程，直至傳入的數(shù)據(jù)全部解壓，解碼流程如圖2所示。

圖2 解碼流程圖

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

為了驗證方法有效性，將本文方法應(yīng)用到ISCAS 89 六個標(biāo)準(zhǔn)電路上，并采用MinTest ATPG 預(yù)先計算的測試集進行實驗。表3 列出了本文方法的測試集縮短效果。第一列為各測試電路名稱，第二列為原測試集長度，第三列為與參考數(shù)作差后實際用于編碼的測試集長度，最后一列為測試集長度的減少率。以傳統(tǒng)游程編碼方法為例，編碼長度不包括每段游程的終止符，實際用于編碼的測試數(shù)據(jù)占比[19]92%～95%。本文采用了相對游程[20]的方法，對每段游程都進行了差值編碼，更大程度的減少了數(shù)據(jù)長度，每個電路長度的減少率都在20%～45%。

表3 數(shù)據(jù)集減少效果

表4列出了本文方法的壓縮效果，第一列為測試電路名稱，第二列為各電路選擇的參考數(shù)類型，第三列為每個電路的平均劃分組數(shù)，第四列為各電路的壓縮率。本文的編碼具有靈活性，在編碼時使用了統(tǒng)計分析[18]的方法，并針對每個電路不同的游程分布情況，規(guī)劃了最優(yōu)選擇的參考數(shù)類型。實驗結(jié)果顯示，對測試數(shù)據(jù)差值編碼后，電路壓縮率高達63.48%。

表4 本文方法的壓縮效果

以測試電路s15850f為例，對實驗壓縮效果作出分析。該電路平均劃分為20個組，第一組參考數(shù)為26。根據(jù)游程編碼規(guī)則可知，該組游程長度在13及以上的，與參考數(shù)作差后編碼長度較原始數(shù)據(jù)直接編碼短，因此差值越大壓縮效果越好。據(jù)統(tǒng)計，在該組182個游程中，有132個游程的序列長度超過13，占比為該組的73%。由此延伸到整個s15850f電路，該電路中測試數(shù)據(jù)長游程較多，作差后的編碼長度能有效減少，測試數(shù)據(jù)的壓縮率與FDR編碼、EFDR編碼相比有了很好地提升，約14.7%。同樣地，實驗電路s5378f中存在較多的短游程，且具分布相對集中，在每段游程長度與參考數(shù)作差后，差值編碼代碼字并不會有較大減少，因此壓縮效果不明顯。

表5 列出了一些經(jīng)典編碼方案與本文方法的壓縮效果，第一列為測試電路名稱，第二至第五列分別為Golomb 編碼[3]、FDR 編碼[4]、EFDR編碼[8]，以及本文編碼方法的壓縮效果，可以看出，本文方案可使得用于編碼的數(shù)據(jù)集長度有效減少，且在編碼時合理考慮了游程的相關(guān)性。將本文方案應(yīng)用到幾個標(biāo)準(zhǔn)測試電路時，發(fā)現(xiàn)本文方法的壓縮率再優(yōu)于其他方法，且平均壓縮效果有明顯提高。

表5 本文編碼方法與其它方法的壓縮效果比較

4 結(jié)論

本文提出了一種基于相對游程的分組參考數(shù)差值編碼壓縮與解壓縮方案，考慮了游程之間的相關(guān)性，將游程與參考數(shù)作差后用于編碼的游程長度變短，有效減少了測試數(shù)據(jù)量。實驗結(jié)果發(fā)現(xiàn)，利用差值編碼對測試數(shù)據(jù)量處理，壓縮率高達44.18%，且6個電路的平均壓縮率要優(yōu)于一些基于游程的經(jīng)典編碼方案。本方法適用于長游程分布較多且游程分布較平均的電路，具體方法是將劃分后的游程序列平均分成若干組，在每組中選擇合適的游程長度作為參考數(shù)，將劃分后的游程長度與參考數(shù)作差并進行編碼。