應(yīng)用二分算法壓縮測(cè)試數(shù)據(jù)的方案

張振林，詹文法

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

隨著集成電路制造工藝水平的提高，集成電路已經(jīng)進(jìn)入納米量級(jí)尺寸，根據(jù)摩爾定律，未來(lái)單個(gè)芯片上晶體管的集成數(shù)量依然會(huì)呈現(xiàn)指數(shù)性增長(zhǎng)，由此帶來(lái)測(cè)試數(shù)據(jù)量的急劇增加，使得測(cè)試問(wèn)題將變得更加困難。測(cè)試數(shù)據(jù)壓縮技術(shù)大多都是通過(guò)編碼方法[1-2]壓縮原始測(cè)試向量，減少測(cè)試數(shù)據(jù)量，通過(guò)自動(dòng)測(cè)試設(shè)備（ATE）的存儲(chǔ)，在被測(cè)電路以硬件解碼的方式還原原始測(cè)試向量，加載到待測(cè)電路，實(shí)現(xiàn)完整的測(cè)試流程。該方法能夠有效解決測(cè)試數(shù)據(jù)量大的問(wèn)題，降低測(cè)試所需成本。目前，國(guó)內(nèi)外研究測(cè)試數(shù)據(jù)壓縮技術(shù)主要分為兩種：內(nèi)建自測(cè)試（BIST）和外建自測(cè)試（BOST）。內(nèi)建自測(cè)試技術(shù)主要針傳統(tǒng)測(cè)試方法的復(fù)雜度高、故障覆蓋率低、測(cè)試時(shí)間較長(zhǎng)等因素導(dǎo)致測(cè)試所需成本較高的缺點(diǎn)，提出在電路內(nèi)部建立測(cè)試生成、加載、分析和測(cè)試控制結(jié)構(gòu)的方法，使得電路能夠測(cè)試自身，以此來(lái)降低測(cè)試所需成本。外建自測(cè)試主要是通過(guò)壓縮的形式把核的測(cè)試向量存儲(chǔ)在測(cè)試裝置中，然后把壓縮后的向量輸入到芯片中，并通過(guò)一個(gè)需要很小代價(jià)的硬件結(jié)構(gòu)執(zhí)行數(shù)據(jù)的轉(zhuǎn)化。由于內(nèi)建自測(cè)試技術(shù)需要滿足高故障覆蓋率的要求，在芯片設(shè)計(jì)階段就必須考慮使用BIST，但目前市場(chǎng)上大部分核不具備BIST的特征，因此外建自測(cè)試技術(shù)應(yīng)用更為普遍。本文提出的基于二分法的測(cè)試數(shù)據(jù)壓縮方法，正是基于外建自測(cè)試技術(shù)的測(cè)試數(shù)據(jù)壓縮方法。

1 二分算法編碼壓縮的主要思想

游程[3-4]長(zhǎng)度，是指在一個(gè)由任意個(gè)0、1組成的數(shù)據(jù)流中，連續(xù)0或者連續(xù)1的個(gè)數(shù)。傳統(tǒng)的雙游程[5]測(cè)試編碼方法是通過(guò)對(duì)測(cè)試向量進(jìn)行游程處理，通過(guò)設(shè)計(jì)編碼表計(jì)算對(duì)應(yīng)游程長(zhǎng)度的測(cè)試向量，并且通過(guò)巧妙的標(biāo)記位，實(shí)現(xiàn)游程之間的轉(zhuǎn)換，從而達(dá)到壓縮原始測(cè)試數(shù)據(jù)的目的。與傳統(tǒng)的雙游程編碼不同，本文在處理游程編碼[6]這一環(huán)節(jié)，采用的是進(jìn)制處理法。該方法主要是采用一定進(jìn)制，對(duì)超過(guò)一定進(jìn)制長(zhǎng)度集中的測(cè)試向量0、1 進(jìn)行切分。 以10 進(jìn)制為例，假設(shè)原始的測(cè)試集為00000000000001111110000000111111111111111，傳統(tǒng)的游程劃分可分為14，5，6和15，這種游程在進(jìn)行編碼表編碼時(shí)需要增加標(biāo)記位區(qū)分測(cè)試向量在具體位置進(jìn)行游程切換，以進(jìn)行編碼；采用本文的進(jìn)制編碼方法，可將游程劃分為9，4，6，7，9和6，只需考慮游程為9時(shí)，后續(xù)游程是否小于進(jìn)制大小，若小于進(jìn)制大小，則與前一游程為同一游程，否則為交替后的游程[7-9]，即前一游程為0游程，則后續(xù)游程為1游程。需要注意的特殊情況是，當(dāng)游程結(jié)束剛好為9時(shí)，增加一位0以區(qū)分此特殊情況。在原始測(cè)試集變?yōu)閱蝹€(gè)游程時(shí)，將這些游程組合起來(lái)，作為一個(gè)小數(shù)計(jì)算。

2 二分壓縮方案

本方案主要在于運(yùn)用二分法查找測(cè)試算法，通過(guò)將原始測(cè)試集的測(cè)試數(shù)據(jù)編碼后的游程做小數(shù)處理，通過(guò)不斷的二分查找，存儲(chǔ)該二分查找的規(guī)律即可存儲(chǔ)該若干個(gè)測(cè)試向量甚至整個(gè)測(cè)試集。壓縮方法流程如圖1所示。

圖1 壓縮方法流程圖

測(cè)試數(shù)據(jù)壓縮方法流程如下：

（1）根據(jù)待測(cè)試集成電路的電路結(jié)構(gòu)生成若干故障的故障列表。

（2）選擇任一故障，運(yùn)行自動(dòng)測(cè)試向量生成工具，以此生成該故障的測(cè)試向量，同時(shí)將該故障點(diǎn)從故障列表中刪除，最終形成級(jí)聯(lián)后原始測(cè)試數(shù)據(jù)即測(cè)試向量序列S，記長(zhǎng)度為T(mén)0。

（3）游程長(zhǎng)度統(tǒng)計(jì)。統(tǒng)計(jì)級(jí)聯(lián)后原始測(cè)試數(shù)據(jù)的長(zhǎng)度K1，K2，…，Kn，其中，Kn表示為第n個(gè)測(cè)試向量的游程長(zhǎng)度，n為正整數(shù)。將該測(cè)試向量按0和1類型游程統(tǒng)計(jì)長(zhǎng)度，采取交替游程[10-11]統(tǒng)計(jì)方法，選擇合適的進(jìn)制N，對(duì)于游程長(zhǎng)度超過(guò)N的采用切分統(tǒng)計(jì)，對(duì)于游程剛好為N的交替情況，在N后面補(bǔ)0來(lái)區(qū)分交替情況。

（4）轉(zhuǎn)化為整數(shù)，根據(jù)步驟（3）所統(tǒng)計(jì)的游程長(zhǎng)度依次組成所需小數(shù)，記為m。

（5）初始化區(qū)間和原始編碼，原始編碼為空。

（7）上述步驟（4）中小數(shù)m在步驟（5）中初始時(shí)，原始編碼為空。重復(fù)上述步驟（6），可得到最終的m編碼情況，記長(zhǎng)度為T(mén)m。

不失一般性，記級(jí)聯(lián)后原始測(cè)試數(shù)據(jù)為00000000 1111 000 1111111 00000，對(duì)于該測(cè)試向量，取10進(jìn)制為例，運(yùn)用上述步驟過(guò)程，最終m的編碼為1101，由此可以看出原始測(cè)試數(shù)據(jù)由37位壓縮到4位。

3 解壓電路

3.1 硬件解壓

硬件解壓的關(guān)鍵在于運(yùn)用有限狀態(tài)機(jī)，將壓縮后的編碼實(shí)現(xiàn)先進(jìn)先出的狀態(tài)傳輸至CPU，同時(shí)利用CPU的二分計(jì)算將傳輸?shù)木幋a狀態(tài)還原為原始的游程長(zhǎng)度，其間K位計(jì)數(shù)器和時(shí)鐘控制器起到一定的輔助作用。本文方法的解壓電路結(jié)構(gòu)如圖2所示，其中包含一個(gè)有限狀態(tài)機(jī)（FSM）、兩個(gè)特殊的K位計(jì)數(shù)器、一個(gè)時(shí)鐘控制器T，同時(shí)利用了SOC中的CPU模塊，將解壓電路嵌入芯片中，該電路規(guī)模小且結(jié)構(gòu)簡(jiǎn)單，成本較低。

圖2 硬件解壓圖

解壓電路的工作過(guò)程如下：

步驟1有限狀態(tài)機(jī)發(fā)出信號(hào)使數(shù)據(jù)讀入，由K位計(jì)數(shù)器不斷累加計(jì)數(shù)，且時(shí)鐘控制器T記錄下讀入“1”的時(shí)間節(jié)點(diǎn)，每累加一次“1”記錄，同時(shí)由第一個(gè)K位計(jì)數(shù)器和時(shí)鐘控制器將傳輸記錄傳入FSM和CPU。

步驟2FSM不斷讀取編碼數(shù)據(jù)直至每組測(cè)試向量讀寫(xiě)完畢，同時(shí)K位計(jì)數(shù)器和時(shí)鐘控制器T將讀取后的狀態(tài)傳輸至CPU。

步驟3由FSM將讀取后的每位編碼傳送至CPU，并進(jìn)行上下限相加后的模2運(yùn)算，由K位計(jì)數(shù)器和時(shí)鐘控制器同時(shí)控制每次查找的狀態(tài)，并做自減運(yùn)算。

步驟4由CPU 計(jì)算后的結(jié)果，依次賦值每位小數(shù)的數(shù)值到K 位計(jì)數(shù)器，并輸出相應(yīng)位數(shù)的“0”和“1”的個(gè)數(shù)。

3.2 軟件解壓

軟件解壓方法的流程圖如圖3所示，其主要工作原理是由控制計(jì)算機(jī)將原始測(cè)試數(shù)據(jù)壓縮后的測(cè)試規(guī)律通過(guò)ATE傳輸至被測(cè)芯片，由解壓和控制電路將測(cè)試規(guī)律還原為原始測(cè)試數(shù)據(jù)傳送至被測(cè)電路，然后將測(cè)試結(jié)果返回至控制計(jì)算機(jī)。

圖3 軟件解壓圖

不失一般性，以10進(jìn)制舉例，假設(shè)原始測(cè)試集為00000000 1111 000 1111111 00000，可以通過(guò)二分編碼壓縮為1101，解壓步驟如下：

步驟1將控制計(jì)算機(jī)編碼計(jì)算出的1101由ATE傳輸至被測(cè)芯片，通過(guò)解壓和控制電路中CPU模塊轉(zhuǎn)換編碼規(guī)律進(jìn)行解壓。

步驟2當(dāng)前以0為下限m0，1為上限m1，做模2操作得到的值為t=0.5，當(dāng)讀取第一位編碼規(guī)律為1時(shí)，即向右查找，令t=m0，初始化t，繼續(xù)讀取第二位編碼規(guī)律為1，繼續(xù)向右查找；如此循環(huán)，直至編碼規(guī)律讀取結(jié)束。

步驟3將解壓后的小數(shù)，進(jìn)行分位，通過(guò)不斷賦值給控制電路中的K 位計(jì)數(shù)器，交替輸出K 位的“0”和“1”到被測(cè)電路中。

步驟4將測(cè)試結(jié)果與期望值進(jìn)行比較，若結(jié)果一致，測(cè)試通過(guò)；否則，測(cè)試未通過(guò)。

4 實(shí)驗(yàn)分析

為了證明本實(shí)驗(yàn)的有效性，采用MinTest產(chǎn)生的測(cè)試向量集，對(duì)ISCAS 89標(biāo)準(zhǔn)電路中部分規(guī)模較大的時(shí)序電路分別進(jìn)行了實(shí)驗(yàn)，得出實(shí)驗(yàn)結(jié)果如表1所示。

表1 本方案壓縮率

從實(shí)驗(yàn)結(jié)果來(lái)看，本二分編碼方案對(duì)s5378 和s9234 兩個(gè)規(guī)模較小的電路壓縮率較低，原因是其測(cè)試數(shù)據(jù)在游程編碼時(shí)較短且集中，游程位數(shù)較多，本方案對(duì)該類電路壓縮效果不是很好；針對(duì)電路中存在較長(zhǎng)游程和比較規(guī)律的電路s13207、電路s35932有較好的壓縮率。實(shí)際上，在測(cè)試芯片的大規(guī)模集成電路中，無(wú)關(guān)位較多，本文的方案能夠起到很好的壓縮效果。

表2給出本方案與國(guó)內(nèi)兩種方案壓縮率對(duì)比情況。由表2可以看出，相對(duì)國(guó)內(nèi)另兩種壓縮方案，本二分編碼方案具有一定的壓縮率、較好的穩(wěn)定性，同Golomb 碼對(duì)比，本方案的壓縮率平均值優(yōu)于其0.7%；同時(shí)本方案在s35932電路中的壓縮率皆高于另外兩種編碼方案。

表2 本方案與國(guó)內(nèi)兩種方案壓縮率對(duì)比表

5 總 結(jié)

傳統(tǒng)的編碼方法多為基于FDR/EFDR編碼表的方法壓縮代碼字，壓縮方式復(fù)雜且成本較高。本文提出一種新的基于二分編碼壓縮的方法，其主要特點(diǎn)：（1）采用一定進(jìn)制的編碼方法，實(shí)現(xiàn)雙游程無(wú)標(biāo)記位交替編碼。（2）通過(guò)運(yùn)用二分編碼算法，實(shí)現(xiàn)測(cè)試向量壓縮。（3）硬件解壓電路簡(jiǎn)單，不會(huì)給測(cè)試增加多余成本。因此，本方案的編碼方法，不但節(jié)省代碼字的長(zhǎng)度，而且減少了硬件開(kāi)銷，為縮減原始測(cè)試數(shù)據(jù)、降低測(cè)試所需成本提供了一種有效的方法，具有一定的實(shí)用價(jià)值。