黃貴林，張正金，江家寶，吳其林，王洪海

(巢湖學(xué)院 信息工程學(xué)院，安徽 巢湖 238024)

0 引言

“芯片內(nèi)集成的晶體管數(shù)目每18個(gè)月將增加一倍”，同時(shí)，系統(tǒng)級(jí)芯片和系統(tǒng)級(jí)封裝的產(chǎn)品，也稱片上系統(tǒng)(system-on-chip，縮寫為SoC)，已成為半導(dǎo)體產(chǎn)業(yè)的主要驅(qū)動(dòng)力。單個(gè)芯片上集成的晶體管越來越多，給芯片測(cè)試帶來了一系列新的挑戰(zhàn)。其中，不斷增長(zhǎng)的數(shù)據(jù)量測(cè)試是芯片測(cè)試必須面臨的挑戰(zhàn)[1]，在有限的ATE存儲(chǔ)空間和I/O帶寬方面，存儲(chǔ)和傳輸大量的測(cè)試數(shù)據(jù)，測(cè)試成本會(huì)升高，測(cè)試時(shí)間變長(zhǎng)。測(cè)試數(shù)據(jù)壓縮技術(shù)一直致力于解決這個(gè)難題。

目前，測(cè)試數(shù)據(jù)壓縮技術(shù)分為三類[2]：基于LFSR結(jié)構(gòu)的壓縮方法[3]、基于廣播掃描的壓縮方法[4]、編碼壓縮方法[5]。其中，編碼壓縮是一種十分受歡迎的測(cè)試數(shù)據(jù)壓縮方法，根據(jù)碼字的對(duì)應(yīng)關(guān)系對(duì)數(shù)據(jù)塊進(jìn)行編碼壓縮，如： GOLOMB、FDR、ALT-FDR、EFDR、9C、BM、RL-HC、SHC、VIHC，它們都是一些非常經(jīng)典優(yōu)秀的方案[6]。目前其能達(dá)到的壓縮效果還是非常理想的，但在測(cè)試應(yīng)用時(shí)間上很難被接受，它以數(shù)據(jù)塊為單位產(chǎn)生測(cè)試數(shù)據(jù)，不能快速產(chǎn)生整條測(cè)試向量。為此，有通過加法器生成后續(xù)測(cè)試向量進(jìn)行編碼壓縮的[7]。為考慮測(cè)試應(yīng)用時(shí)間及壓縮率等問題，在測(cè)試向量層面，本文提出一種利用循環(huán)掃描鏈的測(cè)試向量編碼方法。該方法對(duì)所有測(cè)試向量進(jìn)行順時(shí)針循環(huán)移位遍歷，找到所有間接相容的測(cè)試向量，并將其構(gòu)造成線性生成圖。根據(jù)循環(huán)移動(dòng)位置對(duì)測(cè)試向量進(jìn)行編碼，編碼替換測(cè)試向量進(jìn)行存儲(chǔ)，實(shí)現(xiàn)無損壓縮，達(dá)到測(cè)試數(shù)據(jù)壓縮的目的。本文貢獻(xiàn)：⑴解壓電路結(jié)構(gòu)簡(jiǎn)單。除了需要常規(guī)的FSM和計(jì)數(shù)器之外，只需要一個(gè)通道MUX即可。⑵測(cè)試數(shù)據(jù)壓縮率顯著提高。⑶測(cè)試應(yīng)用時(shí)間大幅度降低。⑷算法簡(jiǎn)單。

1 設(shè)計(jì)方案

1.1 循環(huán)掃描鏈

定義1：對(duì)于單掃描鏈而言，芯片測(cè)試外殼當(dāng)中的所有掃描鏈?zhǔn)菃畏较虻?，是以串的形式連接在一起的。Input為時(shí)序電路的功能輸入(外部輸入)端，即測(cè)試向量的部分測(cè)試數(shù)據(jù)的輸入端，Output為時(shí)序電路的功能輸出(外部輸出)端，即測(cè)試響應(yīng)的部分?jǐn)?shù)據(jù)輸出端。每個(gè)觸發(fā)器的Q連接到時(shí)序電路當(dāng)中組合電路的輸入端，也連接到下一級(jí)觸發(fā)器單元的Q′。

掃描鏈當(dāng)中的第一個(gè)觸發(fā)器和最后一個(gè)觸發(fā)器連接起來，即最后一個(gè)觸發(fā)器的Q也作為第一個(gè)觸發(fā)器的輸入TD，如圖1所示，圖中虛線電路為本文添加的電路結(jié)構(gòu)，與原有的觸發(fā)器連線，將所有觸發(fā)器連接形成一個(gè)環(huán)形的掃描鏈。測(cè)試向量可以在掃描鏈當(dāng)中順時(shí)針循環(huán)移動(dòng)，因此稱為循環(huán)掃描鏈。

圖1 循環(huán)掃描鏈

定義2：物理上形成的循環(huán)掃描鏈，測(cè)試向量可在循環(huán)掃描鏈當(dāng)中順時(shí)針循環(huán)移動(dòng)。邏輯上，就形成了環(huán)形的循環(huán)測(cè)試向量。測(cè)試向量1：A0、A1、A2、…、An，測(cè)試向量2：B0、B1、B2、…、Bn，測(cè)試向量1和2的對(duì)應(yīng)位A0和B0、A1和B1、A2和B2、…、An和Bn等對(duì)應(yīng)位全部相容，則稱測(cè)試向量1和測(cè)試向量2直接相容。

圖2 測(cè)試向量1在掃描鏈中循環(huán)右移1位

如圖2所示，測(cè)試向量x0011在循環(huán)掃描鏈當(dāng)中順時(shí)針循環(huán)移動(dòng)1位，得到測(cè)試向量1x001。測(cè)試向量1x001與圖3當(dāng)中的測(cè)試向量2(1xx01)相容，則稱測(cè)試向量1與測(cè)試向量2間接相容。下劃線所示的兩個(gè)測(cè)試位1和1，是新形成的對(duì)應(yīng)位。

圖3 測(cè)試向量2

1.2 線性生成圖

在邏輯上，每個(gè)測(cè)試向量都是循環(huán)測(cè)試向量。先探索構(gòu)造環(huán)形生成圖，節(jié)點(diǎn)是測(cè)試向量，所有節(jié)點(diǎn)的出度和入度都為1，N個(gè)節(jié)點(diǎn)共有N條邊。再繼續(xù)構(gòu)造線性生成圖，首節(jié)點(diǎn)的出度為1，尾節(jié)點(diǎn)的入度為1，其余每個(gè)節(jié)點(diǎn)的出度和入度都為1，N個(gè)節(jié)點(diǎn)共有N-1條邊。節(jié)點(diǎn)之間間接相容，循環(huán)右移的位數(shù)為權(quán)值。測(cè)試向量長(zhǎng)度為L(zhǎng)。

⑴列表List1的初始狀態(tài)是空集，列表List2的初始狀態(tài)包含整個(gè)測(cè)試集，即被測(cè)電路的所有測(cè)試向量。

⑵第0個(gè)測(cè)試向量T(0)從List2進(jìn)入List1，List2中沒有T(0)。在(3)到(7)中，List1和List2的并集是被測(cè)電路的整個(gè)測(cè)試集，即被測(cè)電路的所有測(cè)試向量。

⑶測(cè)試向量的長(zhǎng)度為L(zhǎng)，測(cè)試向量T(1)順時(shí)針循環(huán)移動(dòng)n位，然后第n位，第(n+1)位，…，第(L-1)位、第0位、第1位、…以及循環(huán)測(cè)試向量T(1)的第(n-1)位，分別與循環(huán)測(cè)試向量T(0)的第0位、第1位、第2位、…、第(L-2)位、第(L-1)位形成新的對(duì)應(yīng)位關(guān)系，對(duì)T(0)和T(1)之間不相容的位數(shù)進(jìn)行計(jì)數(shù)。n的范圍在0和L-1之間。根據(jù)不同的n，統(tǒng)計(jì)L次T(0)和T(1)之間不相容的位數(shù)。在這個(gè)統(tǒng)計(jì)過程中，如果不相容位的最小個(gè)數(shù)為0，說明T(0)和T(1)之間間接相容，那么T(1)從List2進(jìn)入List1。

⑷重復(fù)這個(gè)過程，即List1中的任意一個(gè)測(cè)試向量T(i)和List2中的某個(gè)測(cè)試向量T(j)之間相容性分析的過程。如果T(i)與T(j)間接相容，那么T(j)從List2進(jìn)入List1。

⑸如果List1中的任何測(cè)試向量與List2中的任何測(cè)試向量不間接相容，則選擇List1中的任何測(cè)試向量T(k)以循環(huán)向右移位。當(dāng)T(k)每次向右移位一位時(shí)，判斷是否間接相容其他測(cè)試向量。如果首先發(fā)現(xiàn)T(m)與T(k)間接相容，那么將T(m)設(shè)為T(k)的鄰節(jié)點(diǎn)。T(m)將從List1中刪除。

圖4 環(huán)形生成圖

圖5 線性生成圖

⑹重復(fù)(5)直到List1是一個(gè)空集。最后一個(gè)測(cè)試向量T(n)成為T(k)的相鄰節(jié)點(diǎn)，形成與表1對(duì)應(yīng)的環(huán)形生成圖，如圖4所示。

⑺刪除權(quán)重最大的邊，構(gòu)造有向線性生成圖，如圖5所示。在測(cè)試過程中，會(huì)按照有向線性生成圖的順序生成測(cè)試向量，種子測(cè)試向量T7會(huì)生成測(cè)試向量T1，T1會(huì)生成T3，以此類推，直到生成T5，所有的測(cè)試向量都會(huì)生成。

1.3 編碼實(shí)例

現(xiàn)有9個(gè)測(cè)試向量，每個(gè)測(cè)試向量為40位，9個(gè)測(cè)試向量之間全部間接相容。第一個(gè)測(cè)試向量T1每次循環(huán)右移1位，查找是否存在測(cè)試向量與其間接相容，如圖4所示。

表1 測(cè)試向量相容性分析

在T1循環(huán)右移2位時(shí)發(fā)現(xiàn)，新形成的測(cè)試向量與T3最先相容，T1與T3間接相容。因此，T3編碼為10010。

T3繼續(xù)循環(huán)右移，當(dāng)循環(huán)右移3位時(shí)發(fā)現(xiàn)，新形成的測(cè)試向量與T8最先相容，T3與T8間接相容。因此，T8編碼為10011。

以此類推，T6、T9、T2、T4、T5、T1分別編碼為10001、10100、10110、11000、10101 和 10010，如表1所示。刪除權(quán)值最大的邊，得到圖5，將測(cè)試向量T7作為種子測(cè)試向量。在測(cè)試過程中，將按照?qǐng)D5所示順序生成后續(xù)測(cè)試向量。

按照?qǐng)D5所示線性生成圖的順序，T7循環(huán)右移產(chǎn)生T1，T1產(chǎn)生T3，直至產(chǎn)生T5，循環(huán)右移位數(shù)之和為31，即如圖5所示權(quán)值之和為31，小于測(cè)試向量長(zhǎng)度。總的來說，生成圖所有測(cè)試向量的測(cè)試應(yīng)用時(shí)間長(zhǎng)度與單個(gè)測(cè)試向量長(zhǎng)度值相當(dāng)，單個(gè)測(cè)試向量的測(cè)試應(yīng)用時(shí)間長(zhǎng)度遠(yuǎn)小于測(cè)試向量長(zhǎng)度值。

2 解碼體系結(jié)構(gòu)

本方案的解壓體系結(jié)構(gòu)主要是由FSM、計(jì)數(shù)器1、計(jì)數(shù)器2、計(jì)數(shù)器3和MUX構(gòu)成。如圖6所示，‘en’和‘bit_in’分別是輸入使能和位輸入信號(hào)?！甪lag’為MUX通道選擇信號(hào)，‘data_in1’和‘data_in2’連接MUX兩個(gè)輸入端，MUX輸入端‘data_in2’連接掃描鏈的末端，MUX輸出端‘out’連接掃描鏈的頭部。MUX控制掃描鏈觸發(fā)器當(dāng)中的測(cè)試數(shù)據(jù)在掃描鏈內(nèi)部順時(shí)針循環(huán)移動(dòng)，得到新的測(cè)試數(shù)據(jù)，即產(chǎn)生下一個(gè)測(cè)試向量。

圖6 解壓結(jié)構(gòu)

計(jì)數(shù)器1用于測(cè)試向量移入掃描鏈計(jì)數(shù)?！甦ec1’用于計(jì)數(shù)器1減1，‘rs1’用于指示計(jì)數(shù)器1的復(fù)位0狀態(tài)，計(jì)數(shù)器1的長(zhǎng)度為┌l(fā)og2(L)┐。計(jì)數(shù)器2用于編碼code移入暫存器計(jì)數(shù)?！甦ec2’用于計(jì)數(shù)器2減1，‘rs2’用于指示計(jì)數(shù)器2的復(fù)位0狀態(tài)，計(jì)數(shù)器2的長(zhǎng)度為┌l(fā)og2(code_L)┐，code_L為編碼長(zhǎng)度。

計(jì)數(shù)器3用于順時(shí)針循環(huán)移位時(shí)鐘周期數(shù)計(jì)數(shù)，即為循環(huán)移位位數(shù)計(jì)數(shù)?！甦ec3’用于計(jì)數(shù)器3減1，‘Dec3’用于指示將暫存器中的編碼重置至計(jì)數(shù)器3，‘rs3’用于指示計(jì)數(shù)器3的復(fù)位0狀態(tài)，┌l(fā)og2(code_L)┐為計(jì)數(shù)器3的長(zhǎng)度。暫存器里存放的是編碼，‘dec’用于使能暫存器，‘data_in’用于將編碼code移入暫存器。

3 編碼分析

N個(gè)測(cè)試向量構(gòu)造線性生成圖，構(gòu)造環(huán)形生成圖的時(shí)間復(fù)雜度T(L)=O(N×L)，構(gòu)造線性生成圖的時(shí)間復(fù)雜度T(L)=O(L)，則整個(gè)算法時(shí)間復(fù)雜度為O(L)，算法簡(jiǎn)單。壓縮率為：

很顯然，對(duì)于環(huán)形生成圖，權(quán)值之和為L(zhǎng)，對(duì)于線性生成圖，權(quán)值之和小于L。除種子測(cè)試向量，線性生成圖上的測(cè)試向量測(cè)試應(yīng)用時(shí)間時(shí)鐘周期數(shù)為t。

4 實(shí)驗(yàn)結(jié)果

為證明本方案在壓縮率上的有效性，給出了基于國(guó)際公認(rèn)的ISCAS89標(biāo)準(zhǔn)電路的實(shí)驗(yàn)結(jié)果。在實(shí)驗(yàn)過程中，測(cè)試向量被連續(xù)注入編碼算法。圖7至圖12是不同情況下的壓縮率變化曲線，橫坐標(biāo)表示注入算法的測(cè)試向量X的數(shù)量，縱坐標(biāo)表示壓縮比Y。由測(cè)試圖可知，在測(cè)試向量注入過程中，壓縮率波動(dòng)，但是總體壓縮率保持上升趨勢(shì)。因此，本文提出的測(cè)試數(shù)據(jù)壓縮方案具有魯棒性，符合公式⑵的預(yù)期。

為進(jìn)一步證明本方案的有效性和科學(xué)性，計(jì)算標(biāo)準(zhǔn)電路測(cè)試向量的總體壓縮率，如表2所示。最后一列為本文所提方案的壓縮率，壓縮率優(yōu)于其他的大部分方案，平均壓縮率都優(yōu)于其他方案，說明本文所提方案適應(yīng)性較好。

表2 實(shí)驗(yàn)結(jié)果

圖7 S5378壓縮率變化曲線

圖8 S9234壓縮率變化曲線

圖9 S13207壓縮率變化曲線

圖10 S15850壓縮率變化曲線

圖11 S38417壓縮率變化曲線

圖12 S38584壓縮率變化曲線

5 結(jié)論

本文主要是探索測(cè)試向量之間的相容性，通過順時(shí)針循環(huán)右移掃描鏈當(dāng)中的測(cè)試向量錯(cuò)開對(duì)應(yīng)位，原對(duì)應(yīng)位之間的位置關(guān)系已經(jīng)不再對(duì)應(yīng)了。測(cè)試向量當(dāng)中存在大量無關(guān)位，新形成的所有對(duì)應(yīng)位存在全部相容的可能性，使得不同的測(cè)試向量之間存在間接相容的關(guān)系，消除了這種原對(duì)應(yīng)位不相容的問題，為測(cè)試數(shù)據(jù)壓縮提供了依據(jù)，有效降低測(cè)試應(yīng)用時(shí)間。