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

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

（國防科學技術大學計算機學院，湖南 長沙 410073）

1 引言

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

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

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

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

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

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

2.1 非確定位填充算法介紹

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

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

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

對于測試數(shù)據(jù)0XXX1X0X1XXX1X0

全0填充為：000010001000100

全1填充為：011111011111110

MT－filling為：000011001111100

Adjacent－filling為：000011001111110

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

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

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

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

（1）當非確定位游程兩邊的確定位相同時，非確定位填充值為該確定位值。

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

①當非確定位游程前的確定位游程長度大于1時，非確定位的填充值與前邊的確定位值相同；

②當非確定位游程前的確定位游程長度為1時，非確定位填充值與后邊的確定位值相同。

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

1XXXX1 11XXXXX0XXXX1 1XXX0 0XXXX1XX0XXXX01

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

2.3 EFDR填充算法的缺陷

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

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

11111XXX00XXXXXXXXXXX1

使用EFDR算法的填充為：

111111110 0000000000001

所屬編碼分組都為A3，需要的編碼字長為14位。

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

1111110 000000000000001

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實驗結果與分析

3.1 壓縮效率分析

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

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

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

3.2 功耗分析

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

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

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

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

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

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

3.3 時間開銷分析

本節(jié)分析ESA填充算法對測試時間開銷的影響，按照文獻［9］的方法，測試時間可以通過以下方法計算：

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

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

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

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

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

Table 5 Comparison of test time表5 不同填充算法測試時間開銷比較

4 結束語

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