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

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

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

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

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

1 編碼方案

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

表1 差值長(zhǎng)度編碼方案

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

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

假設(shè)給出一組測(cè)試數(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個(gè)游程序列），編碼后的數(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個(gè)游程序列）。

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

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

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

2 解壓設(shè)計(jì)

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

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

圖1 解碼框

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

表2 解碼器信號(hào)及其對(duì)應(yīng)功能

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

圖2 解碼流程圖

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

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

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

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

表4 本文方法的壓縮效果

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

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

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

4 結(jié)論

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