結合TRC和Golomb編碼的二維測試數據壓縮

高紫俊， 許 晶

( 1. 哈爾濱理工大學 榮成學院，山東 榮成 264300； 2. 大慶電力集團 油田熱電廠，黑龍江 大慶 163314 )

0 引言

隨著深亞微米技術的發展，集成電路進入片上系統(SoC)時代.復雜的SoC設計導致測試變得越來越復雜.傳統的基于ATE的測試方法很難滿足測試成本方面的需求.內建自測試(Built-in Self-Test，BIST)是一種極具吸引力的解決SoC測試問題的測試方法[1-5].BIST通過將測試向量生成器(Test Pattern Generator，TPG)、測試響應分析器(Output Response Analyzer，ORA)和測試控制邏輯(Test Control Logic，TCL)設計在被測電路(Circuit Under Test，CUT)上，從而擺脫對ATE的依賴[1-2].依據測試向量生成方法的不同，BIST被分為偽隨機BIST和確定性BIST.偽隨機BIST通常采用偽隨機測試向量電路，如線性反饋移位寄存器(Linear-Feedback Shift-Register，LFSR)和細胞自動機(Cellular Automaton，CA)等，生成測試向量.采用偽隨機測試向量方案具有電路結構簡單、硬件開銷小等優點，但也存在測試序列長、某些故障難以測試等不足.在確定性BIST方案中，一般將由ATPG生成的測試集存儲在被測電路(Circuit under Test，CUT)的ROM中，測試時通過控制邏輯再加載到被測電路上.確定性BIST方案具有測試時間短、故障覆蓋率高等優點，也具有測試數據大、測試控制邏輯復雜等缺點[3-6].

周彬等[6]采用“壓縮-存儲-生成”方案降低測試數據，測試數據的壓縮方式可分為水平壓縮和垂直壓縮.水平壓縮是減少測試集中每個測試向量的位數的方法，主要包括輸入精簡壓縮技術和編碼壓縮技術.輸入精簡壓縮技術通過分析被測電路的各個輸入端的相容性，并將相容的輸入端合并，從而達到壓縮測試數據的目的[7-8]，該方法的優點是壓縮效率高；缺點是必須重新設計掃描鏈結構，進而干擾傳統的設計流程.編碼壓縮技術包括統計碼[9]、FDR碼[10]、Golomb碼[11]、VIHC碼[12]、LFSR編碼[13]等.垂直壓縮是減少測試集中測試向量個數的方法，主要包括相容測試向量的合并技術和測試集嵌入技術.相容測試向量的合并技術通過分析測試集中測試向量的相容性，并將相容進行合并，從而達到減少測試向量個數的目的.測試集嵌入技術通常是利用重播種技術改變測試向量產生器的狀態，進而將確定性的測試向量嵌入在定制計數器或LFSR生成的一個長序列中，如基于折疊計數器的確定性測試集的嵌入技術[3-5]和基于扭環計數器(Twisting Ring Counter，TRC)的測試集嵌入技術[14-18].

筆者給出一種基于扭環計數器(TRC)和Golomb編碼相結合的二維測試數據壓縮方案.首先，采用基于TRC的測試集嵌入技術對由ATPG工具生成的測試集進行垂直壓縮；其次，利用TRC種子可以任意移位的特性對所得到種子集進行有效的Golomb編碼壓縮；最后，使用很少的種子位將這個確定測試集嵌入到扭環計數器所有生成的向量中，并獲得100%的故障覆蓋率.由于無需調整任何掃描鏈,該方案完全與標準設計流相容.另外，對于不同的被測試電路，提出方案的測試控制邏輯都是相同的，不需要進行專門的硬件設計.

1 垂直壓縮

采用與文獻[6]相似的種子選擇算法對測試集進行垂直壓縮.在算法中，除定義相容百分數(Percentage of Compatibility，PC)外，還定義一個最大確定位個數Max_SB控制種子中確定位的個數，使后續的基于Golomb編碼的水平壓縮獲得更大的壓縮效率.

種子選擇算法步驟：

(1)計算測試集中每個測試向量中含有無關項X的數量，并且根據無關項的數量，對測試集中的測試向量由小到大進行排序.

(2)在經排序后的測試集中，第1個測試向量集將被選作為算法的候選種子(初始種子)，并且根據TRC的特性，利用該候選種子生成2n2+n個TRC狀態，該候選種子中包含有無關項X.

(3)在經排序后的測試集中，取出一個測試向量Tj(除種子向量之外)，如果在長為2n2+n的TRC狀態中，找到某一個狀態TRCi，使得在XORNEW(TRCi，Tj)的結果中，不存在 ‘1’，并且‘0’的個數大于等于相容數(NCSB(Tj))時，根據Tj指定候選種子中相應的無關項，如果指定之后的候選種子所含確定位的個數小于Max—SB，將Tj從原確定性測試集中刪除，否則恢復候選種子到未指定之前的狀態；然后再在經排序后的測試集中選取下一個測試向量Tj+1，直至所有測試向量都被遍歷為止.XORNEW函數是原始異或函數的擴展，功能與原始異或函數類似，唯一的區別在于XORNEW函數可以對包含無關項X的操作數進行處理，如XORNEW(10x，001)等于10x.

(4)當測試集中仍包含有測試向量時，算法就再次跳轉到第2步；當測試集中不包含有測試向量時，算法結束.

由種子選擇算法的步驟可知，通過引入最大確定位個數Max—SB，算法所得到種子中包含有大量的無關項，為實現高效的基于Golomb編碼的水平壓縮提供便利條件.

2 水平壓縮

表1 Golomb編碼實例(m=4)

選用Golomb碼對種子集進行編碼，其原因為Golomb碼屬于無失真編碼,不僅具有較高的編碼效率,而且易于用硬件解碼.m=4時所對應的Golomb編碼見表1.其中：m為分組的大小，第1列表示編碼的分組信息，第2列為0游程的長度，第3列為編碼前綴，第4列為編碼尾綴，最后一列為對應的編碼碼字.如待壓縮序列Sd為001001001000000001時，編碼后的序列Se為01001001011000.當待壓縮序列Sd給定時，隨著Golomb編碼參數m值的不同，所得的壓縮增益是不同的，因此參數m的選取非常關鍵.采用實驗方法確定最佳的m值.

3 測試結構

基于Golomb編碼和扭環計數器的重播種結構見圖1.其中，在被測電路的原始輸入端上增加一個掃描觸發器，并與被測電路內部的掃描鏈構成一個長的掃描鏈，稱之為輸入寄存器.測試時，通過該輸入寄存器對被測電路進行激勵的加載.ROM中存儲的是重播種所需要的種子差分向量序列經過Golomb編碼之后的測試數據.整個電路的工作過程：首先，被測電路的輸入寄存器形成一個移位寄存器，在n個時鐘周期內，通過種子差分向量與移位寄存器中上一個種子向量的結束向量相異或，產生一個TRC種子向量；利用該TRC種子向量，在2n2+n時鐘周期內產生2n2+nTRC狀態，并加載至被測電路的輸入端，同時在被測電路的輸出端得到相應的響應；接著，ROM計數器加1，下一個TRC種子被裝載到輸入寄存器中，并產生測試向量序列，重復進行上述過程，直到測試完成.

圖1 基于Golomb編碼和扭環計數器的播種結構

BIST控制邏輯結構見圖1被虛線包圍的區域.提出方案的BIST控制邏輯主要包含具有3個狀態的有限狀態機、2個計數器和組合控制邏輯電路.其中，移位計數器是用來計數每個TRC種子所需要的n次移位操作，在測試生成的過程中，每當2n+1個時鐘周期之后，內容自動加1，同時輸入寄存器的內容執行一次循環移位操作；扭環計數器被用來對TRC種子的加載操作和TRC種子生成測試向量進行計數.

4 實驗結果與分析

基于提出的二維測試數據壓縮方案，針對ISCAS’89實驗電路進行研究.在實驗中，ISCAS’89實驗電路的所有輸入和其內部的觸發器構成被測電路的輸入掃描寄存器，采用ATALANTA ATPG工具為被測電路生成測試集.為了提高所生成的確定性測試集中無關項X的含量，在實驗中關閉了ATALANTA ATPG工具壓縮機制.

提出基于扭環計數器(TRC)和Golomb編碼相結合的二維測試數據壓縮方案，與其他先進的BIST方案[16,18]在測試數據方面的比較結果見表2.其中：第2、3欄分別描述提出BIST方案所需要的種子個數以及最終的測試數據位數ROM1；第4、5欄分別列出基于TRC的確定性BIST方案[16]所需要測試數據位數ROM2，以及基于LFSR的確定性BIST方案[18]所需要測試數據位數ROM3；最后2欄是文中提出二維測試數據壓縮BIST方案與文獻[16，18]的比較結果.與文獻[16]比較，提出的二維測試數據壓縮BIST方案具有更高的壓縮倍數，在存儲位數方面減少近30%.

表2 二維測試數據壓縮方案與其他方案存儲位數(ROM)的比較

5 結束語

提出一種結合扭環計數器(TRC)和Golomb編碼的二維測試數據壓縮的內建自測試方案.首先，利用扭環計數器實現對測試集進行垂直壓縮；然后，對經過垂直壓縮之后的扭換計數器種子再進行基于Golomb編碼的水平壓縮.根據實驗結果顯示，所提出二維測試數據壓縮BIST方案在測試數據方面有一定的提高，而且在減少測試數據的同時，不會顯著增加測試時間，存儲位數減少30%，是一種具有潛力的確定性BIST方案.