應用二分算法壓縮測試數據的方案

張振林，詹文法

（安慶師范大學計算機與信息學院，安徽安慶246133）

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

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

游程[3-4]長度，是指在一個由任意個0、1組成的數據流中，連續0或者連續1的個數。傳統的雙游程[5]測試編碼方法是通過對測試向量進行游程處理，通過設計編碼表計算對應游程長度的測試向量，并且通過巧妙的標記位，實現游程之間的轉換，從而達到壓縮原始測試數據的目的。與傳統的雙游程編碼不同，本文在處理游程編碼[6]這一環節，采用的是進制處理法。該方法主要是采用一定進制，對超過一定進制長度集中的測試向量0、1 進行切分。 以10 進制為例，假設原始的測試集為00000000000001111110000000111111111111111，傳統的游程劃分可分為14，5，6和15，這種游程在進行編碼表編碼時需要增加標記位區分測試向量在具體位置進行游程切換，以進行編碼；采用本文的進制編碼方法，可將游程劃分為9，4，6，7，9和6，只需考慮游程為9時，后續游程是否小于進制大小，若小于進制大小，則與前一游程為同一游程，否則為交替后的游程[7-9]，即前一游程為0游程，則后續游程為1游程。需要注意的特殊情況是，當游程結束剛好為9時，增加一位0以區分此特殊情況。在原始測試集變為單個游程時，將這些游程組合起來，作為一個小數計算。

2 二分壓縮方案

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

圖1 壓縮方法流程圖

測試數據壓縮方法流程如下：

（1）根據待測試集成電路的電路結構生成若干故障的故障列表。

（2）選擇任一故障，運行自動測試向量生成工具，以此生成該故障的測試向量，同時將該故障點從故障列表中刪除，最終形成級聯后原始測試數據即測試向量序列S，記長度為T0。

（3）游程長度統計。統計級聯后原始測試數據的長度K1，K2，…，Kn，其中，Kn表示為第n個測試向量的游程長度，n為正整數。將該測試向量按0和1類型游程統計長度，采取交替游程[10-11]統計方法，選擇合適的進制N，對于游程長度超過N的采用切分統計，對于游程剛好為N的交替情況，在N后面補0來區分交替情況。

（4）轉化為整數，根據步驟（3）所統計的游程長度依次組成所需小數，記為m。

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

（7）上述步驟（4）中小數m在步驟（5）中初始時，原始編碼為空。重復上述步驟（6），可得到最終的m編碼情況，記長度為Tm。

不失一般性，記級聯后原始測試數據為00000000 1111 000 1111111 00000，對于該測試向量，取10進制為例，運用上述步驟過程，最終m的編碼為1101，由此可以看出原始測試數據由37位壓縮到4位。

3 解壓電路

3.1 硬件解壓

硬件解壓的關鍵在于運用有限狀態機，將壓縮后的編碼實現先進先出的狀態傳輸至CPU，同時利用CPU的二分計算將傳輸的編碼狀態還原為原始的游程長度，其間K位計數器和時鐘控制器起到一定的輔助作用。本文方法的解壓電路結構如圖2所示，其中包含一個有限狀態機（FSM）、兩個特殊的K位計數器、一個時鐘控制器T，同時利用了SOC中的CPU模塊，將解壓電路嵌入芯片中，該電路規模小且結構簡單，成本較低。

圖2 硬件解壓圖

解壓電路的工作過程如下：

步驟1有限狀態機發出信號使數據讀入，由K位計數器不斷累加計數，且時鐘控制器T記錄下讀入“1”的時間節點，每累加一次“1”記錄，同時由第一個K位計數器和時鐘控制器將傳輸記錄傳入FSM和CPU。

步驟2FSM不斷讀取編碼數據直至每組測試向量讀寫完畢，同時K位計數器和時鐘控制器T將讀取后的狀態傳輸至CPU。

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

步驟4由CPU 計算后的結果，依次賦值每位小數的數值到K 位計數器，并輸出相應位數的“0”和“1”的個數。

3.2 軟件解壓

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

圖3 軟件解壓圖

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

步驟1將控制計算機編碼計算出的1101由ATE傳輸至被測芯片，通過解壓和控制電路中CPU模塊轉換編碼規律進行解壓。

步驟2當前以0為下限m0，1為上限m1，做模2操作得到的值為t=0.5，當讀取第一位編碼規律為1時，即向右查找，令t=m0，初始化t，繼續讀取第二位編碼規律為1，繼續向右查找；如此循環，直至編碼規律讀取結束。

步驟3將解壓后的小數，進行分位，通過不斷賦值給控制電路中的K 位計數器，交替輸出K 位的“0”和“1”到被測電路中。

步驟4將測試結果與期望值進行比較，若結果一致，測試通過；否則，測試未通過。

4 實驗分析

為了證明本實驗的有效性，采用MinTest產生的測試向量集，對ISCAS 89標準電路中部分規模較大的時序電路分別進行了實驗，得出實驗結果如表1所示。

表1 本方案壓縮率

從實驗結果來看，本二分編碼方案對s5378 和s9234 兩個規模較小的電路壓縮率較低，原因是其測試數據在游程編碼時較短且集中，游程位數較多，本方案對該類電路壓縮效果不是很好；針對電路中存在較長游程和比較規律的電路s13207、電路s35932有較好的壓縮率。實際上，在測試芯片的大規模集成電路中，無關位較多，本文的方案能夠起到很好的壓縮效果。

表2給出本方案與國內兩種方案壓縮率對比情況。由表2可以看出，相對國內另兩種壓縮方案，本二分編碼方案具有一定的壓縮率、較好的穩定性，同Golomb 碼對比，本方案的壓縮率平均值優于其0.7%；同時本方案在s35932電路中的壓縮率皆高于另外兩種編碼方案。

表2 本方案與國內兩種方案壓縮率對比表

5 總 結

傳統的編碼方法多為基于FDR/EFDR編碼表的方法壓縮代碼字，壓縮方式復雜且成本較高。本文提出一種新的基于二分編碼壓縮的方法，其主要特點：（1）采用一定進制的編碼方法，實現雙游程無標記位交替編碼。（2）通過運用二分編碼算法，實現測試向量壓縮。（3）硬件解壓電路簡單，不會給測試增加多余成本。因此，本方案的編碼方法，不但節省代碼字的長度，而且減少了硬件開銷，為縮減原始測試數據、降低測試所需成本提供了一種有效的方法，具有一定的實用價值。