基于EFDR編碼壓縮的非確定位填充算法＊

郭東升，唐 敏，吳鐵彬，劉衡竹

（國(guó)防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院，湖南 長(zhǎng)沙 410073）

1 引言

隨著集成電路制造工藝的進(jìn)步和芯片集成規(guī)模的急劇增加，芯片測(cè)試數(shù)據(jù)猛增，導(dǎo)致測(cè)試成本急劇上升，如何降低測(cè)試數(shù)據(jù)的存儲(chǔ)開銷并縮短測(cè)試時(shí)間是當(dāng)前學(xué)術(shù)界研究的熱點(diǎn)。

減少測(cè)試數(shù)據(jù)的存儲(chǔ)開銷可以通過BIST（Build－In Self－Test）結(jié) 構(gòu)［1］和 測(cè) 試 數(shù) 據(jù) 壓 縮 技 術(shù)來實(shí)現(xiàn)［2］。BIST結(jié)構(gòu)需要嵌入到芯片中，常常和片上的測(cè)試數(shù)據(jù)產(chǎn)生模塊聯(lián)合使用。雖然BIST結(jié)構(gòu)可以大幅度地減少需要存儲(chǔ)的測(cè)試數(shù)據(jù)數(shù)量，不過利用BIST結(jié)構(gòu)的測(cè)試時(shí)間會(huì)增加，而且BIST結(jié)構(gòu)會(huì)改變測(cè)試電路的物理結(jié)構(gòu)，增加約束條件，這些都限制了BIST結(jié)構(gòu)的使用。而測(cè)試數(shù)據(jù)壓縮技術(shù)則不需要對(duì)電路結(jié)構(gòu)進(jìn)行改變，可以獨(dú)立于測(cè)試電路對(duì)測(cè)試數(shù)據(jù)進(jìn)行壓縮，從而減少測(cè)試數(shù)據(jù)的存儲(chǔ)開銷。

EFDR算法［3］是一種典型的基于編碼壓縮的測(cè)試數(shù)據(jù)壓縮算法。EFDR算法考慮對(duì)連續(xù)0游程和連續(xù)1游程分別編碼，具有算法簡(jiǎn)單、壓縮解壓縮結(jié)構(gòu)小、壓縮效率高等特點(diǎn)。

除了編碼壓縮算法的研究，針對(duì)非確定位填充的研究也很重要。由于測(cè)試數(shù)據(jù)中的非確定位數(shù)量極大［4］，合理地對(duì)非確定位填充會(huì)提高壓縮算法的壓縮效率。

本文以EFDR算法為基礎(chǔ)，研究EFDR算法的非確定位填充要求，提出了針對(duì)EFDR編碼壓縮算法優(yōu)化的非確定位填充算法ESA（EFDR－Suited X－filling Algorithm）。基于ISCAS’89標(biāo)準(zhǔn)電路［5］的實(shí)驗(yàn)結(jié)果表明，該算法在不提高測(cè)試功耗的前提下，提高了EFDR算法的壓縮效率，縮短了測(cè)試時(shí)間。

2 優(yōu)化的EFDR算法的非確定位填充技術(shù)

2.1 非確定位填充算法介紹

測(cè)試數(shù)據(jù)中的非確定位是非常多的，常常占測(cè)試數(shù)據(jù)總數(shù)的70%以上，更有些測(cè)試數(shù)據(jù)中的非確定位數(shù)占到測(cè)試數(shù)據(jù)的90%以上（見表1），所以合理填充非確定位可能會(huì)對(duì)測(cè)試數(shù)據(jù)壓縮效果有所提高。

Table 1 Ratio of X in test data表1 非確定位在測(cè)試數(shù)據(jù)中所占的比例

傳統(tǒng)的非確定位填充技術(shù)主要包括全0填充和全1填充，即分別對(duì)非確定位全部填充0或者全部填充1，除此之外還有一些改進(jìn)的非確定位填充算法，如：最少傳輸跳變填充算法MT－filling（Minimum－Transition－fill）［6］、鄰 近 位 相 同 填 充 算 法Adjacent－filling［7］。MT－filling填 充 算 法 在 填 充時(shí)，如果非確定位序列兩邊的確定位相同，非確定位填充值為相同確定位的值，否則隨機(jī)填充0或者1；在Adjacent－filling算法中，非確定位的填充與傳輸方向上的臨近確定位相同。

對(duì)于測(cè)試數(shù)據(jù)0XXX1X0X1XXX1X0

全0填充為：000010001000100

全1填充為：011111011111110

MT－filling為：000011001111100

Adjacent－filling為：000011001111110

2.2 EFDR算法的非確定位填充方法

EFDR編碼壓縮算法的非確定位填充算法和這些算法不同，EFDR在填充非確定位時(shí)，考慮了EFDR算法的特點(diǎn)，其編碼字見表2。EFDR編碼壓縮算法對(duì)以1結(jié)尾的0游程或以0結(jié)尾的1游程進(jìn)行編碼，按照游程的長(zhǎng)度范圍將游程劃分到不同的組中，編碼字隨分組編號(hào)的增加而遞增，組編號(hào)小的編碼字短，組編號(hào)大的編碼字長(zhǎng)，增幅為兩位。

Table 2 Code word of EFDR code表2 EFDR編碼算法編碼字表

由表2可知，測(cè)試數(shù)據(jù)游程越長(zhǎng)，編碼效率越高。故EFDR算法的非確定位填充規(guī)則如下：

（1）當(dāng)非確定位游程兩邊的確定位相同時(shí)，非確定位填充值為該確定位值。

（2）當(dāng)非確定位游程兩邊的確定位不相同時(shí)，沿測(cè)試數(shù)據(jù)的傳輸方向：

①當(dāng)非確定位游程前的確定位游程長(zhǎng)度大于1時(shí)，非確定位的填充值與前邊的確定位值相同；

②當(dāng)非確定位游程前的確定位游程長(zhǎng)度為1時(shí)，非確定位填充值與后邊的確定位值相同。

依據(jù)上述填充規(guī)則，對(duì)于測(cè)試數(shù)據(jù)：

1XXXX1 11XXXXX0XXXX1 1XXX0 0XXXX1XX0XXXX01

EFDR算法的填充結(jié)果為：111111 11111110 11111 11110 000001 000000001

2.3 EFDR填充算法的缺陷

EFDR算法對(duì)非確定位的填充已經(jīng)考慮到了其算法的編碼特點(diǎn)，不過由于每個(gè)分組都包含一定的游程長(zhǎng)度，所以對(duì)于包含非確定位的測(cè)試數(shù)據(jù)段，不同的非確定位填充方法，得到的編碼游程分組可能不同。

例如，對(duì)于測(cè)試數(shù)據(jù)序列：

11111XXX00XXXXXXXXXXX1

使用EFDR算法的填充為：

111111110 0000000000001

所屬編碼分組都為A3，需要的編碼字長(zhǎng)為14位。

考慮第一個(gè)非確定位游程，由表2可知，如果將第一個(gè)非確定位游程的前一個(gè)非確定位填充為1，后兩個(gè)確定位填充為0，這樣填充之后得到的測(cè)試數(shù)據(jù)可以劃分為一個(gè)屬于A2組的連續(xù)1游程和一個(gè)屬于A3組的連續(xù)0游程，即：

1111110 000000000000001

壓縮該測(cè)試數(shù)據(jù)段需要的壓縮編碼總長(zhǎng)為12位，相對(duì)于EFDR算法的填充方法少了2位。

2.4 優(yōu)化的非確定位填充算法

本文提出的非確定位填充算法按照以下的填充規(guī)則填充：

規(guī)則1 當(dāng)非確定位兩邊為1時(shí)，即測(cè)試數(shù)據(jù)序列形如：1XXXX1時(shí)，非確定位填充為1；

規(guī)則2 當(dāng)非確定位兩邊為0時(shí)，即測(cè)試數(shù)據(jù)序列形如：0XXXX0時(shí)，非確定位填充為0；

規(guī)則3 當(dāng)非確定位兩邊的確定位不同時(shí)，即測(cè)試數(shù)據(jù)形如：1XXXXX0或0XXXXX1時(shí)，考慮兩邊確定位的情況進(jìn)行填充。

本文提出的非確定位（ESA）填充算法可以分為三步：首先對(duì)滿足規(guī)則1和規(guī)則2情形的非確定位進(jìn)行填充；之后將待填測(cè)試數(shù)據(jù)進(jìn)行預(yù)處理，得到測(cè)試數(shù)據(jù)游程類型數(shù)組T＝｛ti｝，確定游程長(zhǎng)度數(shù)組L＝｛li｝以及非確定位游程長(zhǎng)度數(shù)組M＝｛mi｝；最后利用數(shù)組T、L、M對(duì)非確定位游程進(jìn)行劃分和填充，得到待壓縮測(cè)試數(shù)據(jù)游程長(zhǎng)度數(shù)組S＝｛si｝。

例如，對(duì)于測(cè)試數(shù)據(jù)：11XXX000XXX110，預(yù)處理得到的數(shù)組T＝｛1，0，1，0｝，L＝｛2，3，2，1｝，M＝｛3，3，0，0｝；之后將M中的每一個(gè)元素mi分割成ai與bi之和，mi＝ai＋bi，其中，非確定位游程中的前ai個(gè)非確定位填充和ti相同，后bi個(gè)非確定位填充和ti＋1相同；最終得到的待壓縮測(cè)試數(shù)據(jù)游程長(zhǎng)度數(shù)組S＝｛si｝，si＝bi－1＋li＋ai。

由以上討論可知，對(duì)非確定位游程長(zhǎng)度mi的劃分是ESA填充算法的核心，考慮EFDR算法的非確定位填充要求，根據(jù)測(cè)試數(shù)據(jù)的特征數(shù)組T、L，非確定位游程長(zhǎng)度mi的劃分方法見表3。

Table 3 Segmentation of mi表3 算法中mi的劃分方法

非確定位填充算法的主要步驟如下：

利用ESA填充算法對(duì)非確定位填充，可以得到更短的壓縮字，例如，對(duì)于如下長(zhǎng)度為60位的測(cè)試數(shù)據(jù)段：

利用EFDR算法的填充算法得到的壓縮后的需要存儲(chǔ)的測(cè)試數(shù)據(jù)為（共46位）：

利用ESA填充算法得到的壓縮后的需要存儲(chǔ)的測(cè)試數(shù)據(jù)為（共40位）：

相對(duì)于利用EFDR算法的填充方案，ESA填充算法可以減少壓縮數(shù)據(jù)的長(zhǎng)度，提高壓縮效率。

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

3.1 壓縮效率分析

為了驗(yàn)證填充算法ESA的有效性，本文使用Matlab實(shí)現(xiàn)該算法，基于ISCAS’89基準(zhǔn)測(cè)試電路，Mintest ATPG［8］產(chǎn) 生 的 測(cè) 試 向 量 集，使 用ESA填充算法填充測(cè)試數(shù)據(jù)中的非確定位；再利用EFDR算法壓縮測(cè)試數(shù)據(jù)，得到的測(cè)試數(shù)據(jù)壓縮效率與原EFDR算法的壓縮效率比較見表4。假設(shè)TD是原始的測(cè)試數(shù)據(jù)總位數(shù)，TE是壓縮后的編碼字的總位數(shù)，壓縮效率CR可以表示如下：

Table 4 Comparison of compression ratio between EFDR and EFDR＋ESA表4 改進(jìn)填充算法壓縮效率比較

表4中，TD代表原始測(cè)試數(shù)據(jù)量，EFDR代表使用EFDR的填充算法得到的壓縮后的測(cè)試數(shù)據(jù)數(shù)量TE和壓縮效率CR，EFDR＋ESA表示使用ESA填充算法得到的壓縮后的測(cè)試數(shù)據(jù)數(shù)量TE和壓縮效率CR。由Improvement的數(shù)據(jù)可知，利用ESA填充算法時(shí)，EFDR編碼壓縮的壓縮效率提高1.14%，證明ESA填充算法是有效的。其中，對(duì)于電路S9234和電路S38417的提高相對(duì)較高，這說明，ESA所針對(duì)的特征非確定位在這兩個(gè)電路中占的比例較大。

3.2 功耗分析

由于本文僅對(duì)填充算法進(jìn)行了優(yōu)化，并未對(duì)壓縮和解壓縮結(jié)構(gòu)做任何改變，所以本節(jié)只考慮可能會(huì)受到填充算法改變而影響到的測(cè)試數(shù)據(jù)的翻轉(zhuǎn)功耗。

由前文可知，本文提出的算法只針對(duì)非確定位兩邊確定位不相同的情形，即0XXXX1或1XXXX0這兩種情形，對(duì)于這種情形的填充方法，由表3可知，可以分為以下幾種情況：

非確定位與前邊確定位相同；

非確定位與后邊確定位相同；

非確定位前一部分與前邊確定位相同，后一部分與后邊確定位相同。

例如，對(duì)于0XXXXX1，本文得到的填充方案只有：00000001、01111111、00011111這三種情況，而這三種情況都不會(huì)增加該序列的01和10的翻轉(zhuǎn)數(shù)，故本文提出的填充算法不會(huì)增加測(cè)試數(shù)據(jù)的翻轉(zhuǎn)率。

3.3 時(shí)間開銷分析

本節(jié)分析ESA填充算法對(duì)測(cè)試時(shí)間開銷的影響，按照文獻(xiàn)［9］的方法，測(cè)試時(shí)間可以通過以下方法計(jì)算：

假設(shè)頻率比率α＝fCUT／fATE，fCUT是被測(cè)試電路的工作頻率，fATE是測(cè)試設(shè)備的時(shí)鐘頻率。假設(shè)測(cè)試集有N個(gè)編碼字C1～CN，每個(gè)編碼字的長(zhǎng)度為Wi，則αmax［9］為：

其中，Hi－1為Ci－1解壓縮得到的測(cè)試數(shù)據(jù)的長(zhǎng)度。

如果α＜αmax，由于解壓縮一個(gè)編碼字用的時(shí)間比從自動(dòng)測(cè)試設(shè)備ATE（Automatic Test Equipment）傳輸一個(gè)編碼字到被測(cè)電路CUT（Circuit Under Test）所用的時(shí)間長(zhǎng)，這時(shí)ATE會(huì)等CUT幾個(gè)時(shí)鐘周期，則測(cè)試時(shí)間TAT［9］為：

如果α＞αmax，可以得到為：

表5給出了使用ESA填充算法時(shí)的時(shí)間開銷和使用EFDR算法的填充算法的時(shí)間開銷對(duì)比，頻率比率α從4～10，表格的第三列為使用EFDR算法填充的時(shí)間開銷，第四列是使用ESA填充算法時(shí)的時(shí)間開銷，最后一列Improvement表示使用ESA填充算法相對(duì)于使用EFDR填充算法的時(shí)間開銷的節(jié)省幅度。由表5中數(shù)據(jù)可知，相對(duì)于EFDR的填充算法，ESA填充算法可以適當(dāng)減少時(shí)間開銷，減少幅度大都在1%～2%，當(dāng)頻率比率α增大時(shí)，提升幅度相應(yīng)也會(huì)提高。

Table 5 Comparison of test time表5 不同填充算法測(cè)試時(shí)間開銷比較

4 結(jié)束語

本文提出了一種新的基于EFDR編碼壓縮算法的非確定位填充算法，該算法針對(duì)測(cè)試向量中可能出現(xiàn)的一些特定情況進(jìn)行優(yōu)化改善。針對(duì)ISCAS’89基準(zhǔn)測(cè)試電路的實(shí)驗(yàn)結(jié)果表明，在使用本文提出的填充算法對(duì)非確定位進(jìn)行填充時(shí)，壓縮效率相對(duì)于原始EFDR算法提高了1.14%，時(shí)間開銷相對(duì)減少了2%左右，并且本算法不會(huì)增加測(cè)試向量的翻轉(zhuǎn)率，即不會(huì)引入額外的測(cè)試功耗，同時(shí)硬件開銷與原有EFDR算法一致。

［1］ McCluskey E J.Built－in－self－test structures［J］.IEEE Design ＆Test of Computers，1985，2（2）：29－33.

［2］ Touba N A.Survey of test vector compression techniques［J］.IEEE Design ＆Test of Computers，2006，23（4）：294－303.

［3］ EL－Maleh A H.Test data compression for system－on－a－chip using extended frequency－directed run－length code［J］.IET Computer Digital Technology，2008，2（3）：155－163.

［4］ Miyase K，Kajihara S.Don’t care identification of test patterns for combinational circuits［J］.IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems，2004，23（2）：321－326.

［5］ Bglez F，Bryan D，Kozminski K.Combinational profiles of sequential benchmark circuits［C］∥Proc of International Symposium on Circuits and Systems，1989：1924－1934.

［6］ Sankaralingam R，Touba N.Multi－phase shifting to reducing instantaneous peak power during scan［C］∥Proc of the 4th IEEE Latin American Test Workshop，2003：78－83.

［7］ Girard P，Nicolici N，Wen X.Power－aware testing and test strategies for low power devices［M］.New York：Springer，2009.

［8］ Hamzaoglu I，Patel J H.Test set compaction algorithms for combinational circuits［C］∥Proc of IEEE International Conference on Computer－Aided Design，1998：283－289.

［9］ Gonciari P T，Al－Hashimi B M，Nicolici N.Improving compression ratio，area overhead，and test application time for system－on－a－chip test data compression／decompression［C］∥Proc of Design，Automation and Test in Europe Conference and Exhibition，2002：604－611.