范海波

摘要:該文提出了一種基于折疊關(guān)系壓縮方案，該方案是利用折疊技術(shù),將SOC芯片中芯核的測試數(shù)據(jù)整體進(jìn)行折疊關(guān)系的判斷,并且能夠根據(jù)是否存在折疊關(guān)系把原測試數(shù)據(jù)分為兩段,在此基礎(chǔ)之上并分別對有折疊關(guān)系的測試數(shù)據(jù)進(jìn)行折疊壓縮，對沒有折疊關(guān)系的測試數(shù)據(jù)使用相容壓縮。目前，減少測試應(yīng)用時間和測試數(shù)據(jù)容量是測試領(lǐng)域的努力方向。該文提出的這種方法可以有效的減少存儲容量和降低測試時間從而有效的降低了測試成本。與類似的純編碼壓縮方法相比，如：Golomb碼，統(tǒng)計(jì)碼，基于字典的編碼等壓縮方法，其壓縮效果更為顯著。

關(guān)鍵詞：內(nèi)建自測試；折疊計(jì)數(shù)器；測試數(shù)據(jù)壓縮；相容壓縮

中圖分類號：TP311文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)15-3494-03

Data Compression Method Realization Based on the Folding Method

FAN Hai-bo

（Anhui Nari Jiyuan Software CO.,LTD., Hefei 230088, China）

Abstract：In this paper, a relationship based on folding compression programme, which is to use folding technology, SMIC chip SOC nu clear test data to the overall collapse of relations between the judgement and can collapse under the existence of relations between the origi nal test data is divided into two sections, On this basis and were to have folded the fold test data compression, in order to obtain a higher compression ratio, the collapse did not use the compatibility test data compression. At present, to reduce test application time and test data capacity is to test the field of direction. The proposed this approach can effectively reduce the storage capacity and reduced testing time, thus effectively reducing the cost of test. And a similar-encoding method, such as: Golomb code, code statistics, based on the coding dic tionaries, such as compression method, the compression effect more significant.

Key words: BIST(built-inself-test);folding counter;testing data compression;compatible compression

隨著芯片集成度的提高，大量的知識產(chǎn)權(quán)（IP）核被用于系統(tǒng)芯片（SOC）的設(shè)計(jì)，這導(dǎo)致了測試數(shù)據(jù)量和測試時間的快速增加，以及測試芯核難以進(jìn)入。它使得傳統(tǒng)的離線測試越來越不適應(yīng)IC的發(fā)展。

最近提出的一些有效的壓縮和解壓方法主要有以下幾類：一類是將預(yù)先計(jì)算的測試集TD分成固定長度的b位塊，將這些定長位塊作為研究的對象。例如，統(tǒng)計(jì)碼就是統(tǒng)計(jì)這些定長位塊在測試集中出現(xiàn)的頻率，并用哈夫曼碼編碼這些定長位塊?？紤]到長度為b的位塊可能出現(xiàn)的組合情況有2種，若用全哈夫曼碼進(jìn)行編碼，碼樹龐大，相應(yīng)的硬件開銷就會非常巨大，所以統(tǒng)計(jì)碼（又稱有選擇的哈夫曼碼）僅對頻率出現(xiàn)最高的幾個位塊進(jìn)行編碼，用小于b位的碼字代替它們，其余塊不變。另一類方法是用特征位的長度代替特征位本身，通過對長度值進(jìn)行編碼來達(dá)到壓縮的目的。這種方法基于對測試集特征的觀察，即測試集的測試模式之間不同位（變化位）較少，通過測試模式之間的異或運(yùn)算，形成一個差分向量序列，序列中的連續(xù)“0”很多，通過編碼連續(xù)“0”序列的長度，可以有效地壓縮測試數(shù)據(jù)，在解壓時，使用一個循環(huán)掃描移位寄存器（CSR）就可以還原出原測試集。

1相容壓縮技術(shù)

1.1相容技術(shù)的理論背景

相容壓縮技術(shù)是一種使用廣泛的數(shù)據(jù)壓縮技術(shù)，它是利用數(shù)據(jù)間的相容關(guān)系進(jìn)行數(shù)據(jù)的壓縮。所謂相容關(guān)系，指的是當(dāng)兩個向量是相容的當(dāng)且僅當(dāng)對任意位置，兩個向量中的對應(yīng)位是相同的或者至少有一個為無關(guān)位。

1.2完整的綜合過程

在本文中，把測試結(jié)合轉(zhuǎn)化為多掃描鏈的形式是做相容壓縮的前提。通過識別相容掃描鏈來減少存儲的測試數(shù)據(jù)量，這些掃描鏈對其他掃描鏈來講，能夠提供相似信息或測試數(shù)據(jù)的線形結(jié)合。通過相容壓縮一方面可以減少測試數(shù)據(jù)量，提高壓縮率；另一方面相容壓縮可以減少測試向量的寬度，從而減少了所需的循環(huán)移位掃描寄存器（CSR）的長度。而在相容壓縮前，首先需要把測試集按照多掃描鏈的形式進(jìn)行排列。例如，預(yù)先計(jì)算的測試集Td是由n個測試模式t1,t2,t3,…,tn組成，被測電路的掃描單元被分為m條掃描鏈（0,1,2,…,m-1）,那么每個測試模式被分成m個子向量，且每個子向量的長度相同，記為d，在長度不足d的子向量的尾部填充無關(guān)位，且在測試向量轉(zhuǎn)化后不足m條掃描鏈時，在剩余的掃描鏈上用無關(guān)位填充（即當(dāng)width % m>d，width為測試向量的寬度）。

如圖1，其中，測試向量的寬度width=20,測試模式個數(shù)即行數(shù)n=4,取掃描鏈的條數(shù)m=5,那么子向量的長度d=4。(x表示無關(guān)位)

圖1將原始測試集轉(zhuǎn)化為多掃描鏈形式

圖1中，第0行，第3行和第4行是相容的，所以可以合并成一個向量，第1行，第2行無與之相容的，故單獨(dú)作為一個向量，不合并，由此可以得到相容壓縮后的測試集。最終實(shí)現(xiàn)了多掃描鏈的相容壓縮。

因此，由圖2得知，通過基于多掃描鏈的結(jié)構(gòu)的第一次的相容壓縮，測試集的無關(guān)位減少了，也就是減少測試數(shù)據(jù)量和移入掃描鏈的時間，提高了壓縮效率和降低了測試成本。同時，相容壓縮也減少了測試向量的寬度，從而減小了CSR的長度。而對相容壓縮這部分的解壓，只需要通過從合并項(xiàng)中引入幾條扇出線就可以實(shí)現(xiàn)了，解壓的硬件非常簡單，使得軟硬件開銷達(dá)到最小。這是第一次壓縮的重要意義所在，為以后的測試數(shù)據(jù)壓縮方法提供了一種新的思想。

圖2將排列后的測試集進(jìn)行相容壓縮

2基于折疊關(guān)系的數(shù)據(jù)壓縮方案

2.1折疊技術(shù)的基本思想

根據(jù)上述理論知識可以將算法分解成異或運(yùn)算、折疊關(guān)系判斷、一致性判斷、生成折疊關(guān)系集合、生成種子并根據(jù)折疊關(guān)系段分測試集合。根據(jù)分析可以看出要達(dá)到理想的壓縮效率生成盡量少的種子，以這些種子來翻轉(zhuǎn)后生成的向量集合可以含蓋原來的測試集合，而要達(dá)到這個目的關(guān)鍵是要找到一個最大的折疊集合，而找到最大的折疊集合的關(guān)鍵是找到一個與盡量多的向量有相同的折疊距離的向量e。要找到使得生成種子數(shù)目最少的向量e的算法比較難，在這里我采用了一種沒有經(jīng)過優(yōu)化的簡單算法來實(shí)現(xiàn)折疊種子的生成。

首先每次選取還沒有被處理的向量集合中的第一個向量作為向量e，然后從1到n循環(huán)的選取折疊距離，每選取一個折疊距離將e與所有剩下的向量進(jìn)行異或運(yùn)算，再對運(yùn)算結(jié)果進(jìn)行判斷以此來確定e與相應(yīng)的向量是不是有折疊關(guān)系。就記錄下與他折疊關(guān)系的向量和向量的個數(shù)，循環(huán)結(jié)束后就進(jìn)行判斷，當(dāng)折疊距離為幾時向量e所包含的折疊集合的數(shù)目最多，并選取這個折疊距離和相應(yīng)的折疊集合，然后通過一致性判斷將折疊集合中有沖突的向量剔除出去。最后根據(jù)向量e和相應(yīng)的折疊距離來生成這個折疊集的折疊種子。

2.2相容技術(shù)的基本思想

通過上面對折疊技術(shù)思想的分析可以看出，在對一個測試集合進(jìn)行折疊種子生成時，不是每一個測試向量都存在與之有折疊關(guān)系的向量的，也就是說，如果一個測試集合中的所有測試子集合都不彼此都不存在折疊關(guān)系，那么通過折疊壓縮生成的種子集合會接近測試集合本身的大小，所以，在生成測試集合折疊種子的過程中，可以考慮通過折疊算法將原測試集合分為兩個部分，既具有折疊關(guān)系的測試集合和不具有折疊關(guān)系的集合分開放置，在對具有折疊關(guān)系的集合進(jìn)行折疊壓縮，不具備折疊關(guān)系的測試集合采用其他方式壓縮，這樣就會在折疊壓縮的理論基礎(chǔ)上更進(jìn)一步的減少種子的位數(shù)，達(dá)到提高壓縮率的目的。

在這里，使用基于多掃描鏈的相容關(guān)系來對相互之間不具備折疊關(guān)系的測試集合進(jìn)行相容壓縮，已達(dá)到更高的壓縮率。

2.3方案的總體流程

綜合上面分析過程，為了得到更高的壓縮效率?？梢詫y試數(shù)據(jù)當(dāng)作一個測試集合，用折疊種子生成算法來生成相應(yīng)的折疊種子。在第二步生成折疊種子的過程中，記錄存在折疊關(guān)系的測試集的序號以及不存在折疊關(guān)系的測試集合的序號。這一點(diǎn)對提高壓縮效率是至關(guān)重要的，因?yàn)閷]有折疊關(guān)系的測試向量使用折疊壓縮是不能得到理想的壓縮率的。但對于存在折疊關(guān)系的測試向量使用折疊壓縮要比使用其他壓縮方法要好的多。所以根據(jù)折疊關(guān)系的存在與否將測試向量分為兩段，以保證可以得到更好的壓縮效果。第三步，根據(jù)第二步所得到的兩段測試向量，分別進(jìn)行相宜的壓縮，并記錄壓縮率。

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

在本文建議方案中，我們先通過存儲折疊距離來控制確定的測試模式生成，表1給出了全部通過折疊壓縮來生成測試種子方案和本文中采取折疊壓縮有折疊關(guān)系的測試向量和相容壓縮(取掃描鏈長度為50)時各自需要存儲的種子的位數(shù)，以及使用本文方法所減少的種子存儲比例。

表1減少的存儲位數(shù)

由表中可見，采用本文中使用的方法對于大部分的測試集合都可以減少生成種子的存儲量，也證明這中方法是有效果的。

4總結(jié)與展望

本文提出了基于折疊關(guān)系的數(shù)據(jù)壓縮的實(shí)現(xiàn)方法。通過折疊關(guān)系將原測試集合劃分為兩段，分別對每段使用合適的壓縮方法，以達(dá)到更好的壓縮效果，同時我還發(fā)現(xiàn)在實(shí)現(xiàn)壓縮的時候，可以根據(jù)折疊關(guān)系的特點(diǎn)降低功耗，并且根據(jù)測試集合的大小選擇合適的掃描鏈的長度來近一步提高書記壓縮率，這些方法在理論上是可以實(shí)現(xiàn)的，目前，我正基于這兩個方面對程序做進(jìn)一步的改進(jìn)，希望可以得到更高的壓縮率，減少更多的壓縮時間。

下面是我對降低功耗的一些設(shè)想：降低功耗我們采取了以下兩種措施，

1）我們先刪除冗余向量，使得這些冗余向量不需要被生成，測試，因此可降低功耗。

2）再對折疊計(jì)數(shù)器序列生成次序加以控制，使所需的翻轉(zhuǎn)次數(shù)減少,從而降低功耗。

參考文獻(xiàn)：

[1]梁華國, Hellebrand S,Wunderlich H J.一種基于折疊計(jì)數(shù)器重新播種的確定自測試方案[J].計(jì)算機(jī)研究與發(fā)展,2001,38(8).

[2]梁華國，蔣翠云.使用雙重種子壓縮的混合模式自測試[J].計(jì)算機(jī)研究與發(fā)展,2004,41(1).

[3] Abramovici M,Breuer M,Friedman A.Digital Systems testing and Testable Design[M].New York:Computer Science Press,1990.

[4] Hellebrand S,Rajski J,Tarnick S,et,al.Built-in Test for Circuits with scan Based on Reseeding of Multiple-Polynomial Linear Feedback Shift Registers[J].IEEE Trans. On Comp.,1995,44(2).