基于折疊方法的數(shù)據(jù)壓縮方法實(shí)現(xiàn)

范海波

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

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

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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

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

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

1相容壓縮技術(shù)

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

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

1.2完整的綜合過程

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3方案的總體流程

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

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

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

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

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

4總結(jié)與展望

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

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

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

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

參考文獻(xiàn)：

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

[2]梁華國(guó)，蔣翠云.使用雙重種子壓縮的混合模式自測(cè)試[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).