王康誼

(中北大學(xué)信息與通信工程學(xué)院，山西太原030051)

在數(shù)字集成電路測(cè)試領(lǐng)域，早期的方法除了需要借助一些常規(guī)的普通工具外，最主要還是依靠工程技術(shù)人員自身的經(jīng)驗(yàn)和理論知識(shí)，并采取窮舉功能的手段來完成測(cè)試.這不僅要求技術(shù)人員具有較高的業(yè)務(wù)素質(zhì)，而且還存在測(cè)試速度慢、容易出錯(cuò)、查錯(cuò)麻煩、不宜改動(dòng)、可移植性差等問題［1-2］.隨著集成電路的規(guī)模和結(jié)構(gòu)的日益復(fù)雜化，現(xiàn)有測(cè)試方法所帶來的弊端也越來越突出，因此必須尋求新的技術(shù)手段來實(shí)現(xiàn)對(duì)數(shù)字集成電路的可靠性測(cè)試.近年來興起的自動(dòng)測(cè)試向量生成(Automatic Test Pattern Generation，ATPG)、內(nèi)建自測(cè)試(Build-In Self-Test，BIST)、邊界掃描測(cè)試(Boundary Scan Test，BST)和可測(cè)性設(shè)計(jì)(Design For Test，DFT)等先進(jìn)的測(cè)試技術(shù)和方法是這方面研究的突出代表［3-5］.其中，自動(dòng)測(cè)試向量生成技術(shù)(ATPG)依據(jù)一定的測(cè)試生成算法，利用計(jì)算機(jī)對(duì)被測(cè)電路進(jìn)行處理，自動(dòng)生成測(cè)試向量，自動(dòng)加載測(cè)試激勵(lì)并回收輸出響應(yīng)，自動(dòng)給出故障征兆指示并孤立故障［6］，是對(duì)數(shù)字邏輯電路進(jìn)行的一種結(jié)構(gòu)級(jí)測(cè)試方法.

測(cè)試生成算法的執(zhí)行時(shí)間與邏輯電路中門的個(gè)數(shù)的平方成正比，隨著集成電路規(guī)模的增大，測(cè)試生成算法會(huì)越來越復(fù)雜，因此研究人員提出了一些迭代算法，常用的如D算法、PODEM算法、FAN 算法和SOCRATES 算法等［3，7］.基于這些算法開發(fā)的測(cè)試生成軟件，比較著名的有美國(guó)泰瑞達(dá)公司的LASER軟件(人們習(xí)慣上稱為數(shù)字電路故障仿真軟件)，Mentor Graphics公司的TestKompress和 Synopsys 公司的 TetraMAX［8］，上述軟件都是基于UNIX操作系統(tǒng)的付費(fèi)軟件，需要在大型服務(wù)器上運(yùn)行，極大地限制了一般研究人員的使用.因此，根據(jù)我國(guó)國(guó)情和實(shí)際需求，開發(fā)基于Windows操作平臺(tái)的“數(shù)字集成電路測(cè)試生成平臺(tái)”，在當(dāng)前具有很重要的現(xiàn)實(shí)意義.國(guó)內(nèi)的南京航天航空大學(xué)、華中科技大學(xué)、華中師范大學(xué)等單位都在開展這方面的工作，在測(cè)試生成的理論、測(cè)試方法學(xué)、可測(cè)性設(shè)計(jì)、容錯(cuò)等方向開展了有益的嘗試和探索［9-12］.

在“數(shù)字集成電路測(cè)試生成平臺(tái)”開發(fā)過程中，讓計(jì)算機(jī)識(shí)別被測(cè)電路是重要的一個(gè)步驟.在測(cè)試領(lǐng)域，描述被測(cè)電路常用的文件有bench，Verilog，VHDL等幾種格式，其中bench是官方標(biāo)準(zhǔn)，也是最常用的一種格式.而要用計(jì)算機(jī)進(jìn)行結(jié)構(gòu)測(cè)試，需要一個(gè)統(tǒng)一的格式來描述電路，這就需要把各種格式的電路文件轉(zhuǎn)換成計(jì)算機(jī)可以識(shí)別的網(wǎng)表文件，目前轉(zhuǎn)換成網(wǎng)表文件的方法及網(wǎng)表文件的格式?jīng)]有官方標(biāo)準(zhǔn)，LASER，Mentor，TetraMax這些著名軟件廠商也都有自己的轉(zhuǎn)換方法，并生成一定格式的網(wǎng)表文件，但都未對(duì)外公布.通過仔細(xì)研究組合邏輯電路自動(dòng)測(cè)試向量生成的典型算法，本課題組發(fā)現(xiàn)這些算法都需要知道被測(cè)電路中每個(gè)節(jié)點(diǎn)的屬性、級(jí)數(shù)、扇入數(shù)目及具體信息、扇出數(shù)目及具體信息、可觀測(cè)性、0可控制性、1可控制性等，因此提出了下面要介紹的一種網(wǎng)表結(jié)構(gòu)，并命名為lev格式.

本文以bench格式描述的基準(zhǔn)電路作為研究對(duì)象，探討把描述組合邏輯電路的bench文件轉(zhuǎn)化為lev格式文件的一些關(guān)鍵技術(shù).

1 問題描述

1.1 bench 文件簡(jiǎn)介

基準(zhǔn)電路是研究測(cè)試向量生成算法的模型電路，是由IEEE Circuits and Systems Society推薦使用的標(biāo)準(zhǔn)電路，業(yè)內(nèi)稱為 ISCAS(International Symposium on Circuits and Systems)電路，分為組合邏輯電路ISCAS85和時(shí)序邏輯電路ISCAS89兩大類［3］.基準(zhǔn)電路的描述形式不是唯一的，目前常見的有 bench，Verilog，edif，VHDL等多種格式，其中bench格式采用簡(jiǎn)單的邏輯符號(hào)定義基本邏輯門單元，是一種描述門級(jí)電路結(jié)構(gòu)的常用方式.

在bench格式所描述的電路中，INPUT代表原始輸入，OUTPUT代表原始輸出，基本的邏輯門單元?jiǎng)t定義為:與門－AND;非門－NOT;NAND－與非門;或門－OR;異或門－XOR;或非門－NOR;異或非門－XNOR;緩沖門－BUF;D觸發(fā)器－DFF.

下面以最簡(jiǎn)單的的組合邏輯電路C17為例來介紹bench文件格式.C17中的C表示組合邏輯電路，17表示有17根線，是一個(gè)由6個(gè)與非門構(gòu)成的電路，5個(gè)輸入，2個(gè)輸出，共有22個(gè)單固定故障.其電路示意圖如圖1所示［3］.

圖1 C17電路Fig.1 C17 circuit

c17電路的bench格式描述如下:

其中#為注釋部分，記錄本電路所有的邏輯門電路的個(gè)數(shù).后面為所有輸入端和輸出端的編號(hào)和對(duì)每個(gè)門電路的描述，如INPUT(1)代表1號(hào)端為輸入端，11=NAND(3，6)代表一個(gè)與非門其輸入端為3和6，輸出端為11.

1.2 lev 文件簡(jiǎn)介

lev文件是一個(gè)電路網(wǎng)表文件，通過剖析bench格式所描述的電路而生成，并按一定的順序排列，文件格式如圖2所示［9］.

圖2 lev文件格式說明Fig.2 Illustration of lev file format

圖2的示例中各參數(shù)的意義如下:

1)節(jié)點(diǎn)編號(hào):電路中的各個(gè)邏輯門單元、原始輸入和原始輸出都被定義為電路節(jié)點(diǎn)，并有唯一的編號(hào)，每個(gè)節(jié)點(diǎn)編號(hào)在讀入 bench文件時(shí)安排.

2)節(jié)點(diǎn)屬性:即節(jié)點(diǎn)的類型，用數(shù)字來表示，1－INPUT;2－OUTPUT;3－XOR;4－XNOR;6－AND;7－NAND;8－OR;9－NOR;10－NOT;11－BUF.

3)節(jié)點(diǎn)級(jí)數(shù):規(guī)定相鄰兩級(jí)的差為5，即每過一個(gè)門電路，節(jié)點(diǎn)級(jí)數(shù)加5.

4)節(jié)點(diǎn)扇入數(shù):電路節(jié)點(diǎn)的輸入端個(gè)數(shù).

5)扇入節(jié)點(diǎn)列表:與節(jié)點(diǎn)扇入數(shù)相對(duì)應(yīng).當(dāng)節(jié)點(diǎn)扇入數(shù)為0時(shí)，扇入列表不存在;如果不為0，扇入列表會(huì)緊跟著出現(xiàn)，并按照可控制性值從小到大排列.為了方便程序讀入處理，扇入列表會(huì)重復(fù)兩次.

6)節(jié)點(diǎn)扇出數(shù):電路節(jié)點(diǎn)的輸出端個(gè)數(shù).

7)扇出節(jié)點(diǎn)列表:與節(jié)點(diǎn)扇出數(shù)對(duì)應(yīng)，扇出數(shù)為0時(shí)不存在扇出列表.

8)節(jié)點(diǎn)CC0:原始輸入節(jié)點(diǎn)的0可控制性，默認(rèn)1.

9)節(jié)點(diǎn)CC1:原始輸入節(jié)點(diǎn)的1可控制性，默認(rèn)1.

10)節(jié)點(diǎn)CO:原始輸出節(jié)點(diǎn)的可觀測(cè)性，默認(rèn)0.

2 Bench文件轉(zhuǎn)化為lev文件的算法實(shí)現(xiàn)

2.1 基本數(shù)據(jù)結(jié)構(gòu)

netlist［］［］:是一個(gè)二維數(shù)組結(jié)構(gòu)，稱為電路網(wǎng)表數(shù)組.其中第一維代表電路節(jié)點(diǎn)，大小為電路節(jié)點(diǎn)的總數(shù);第二維定義了電路節(jié)點(diǎn)的邏輯值和各種屬性值，包括圖2中規(guī)定的Lev文件各個(gè)參數(shù).特別地，netlist［n］［4］和 netlist［n］［6］指明了節(jié)點(diǎn)扇入列表和扇出列表的起始指針.

faninlist［］和 fanoutlist［］:定義了節(jié)點(diǎn)扇入列表和節(jié)點(diǎn)扇出列表，其起始指針在netlist［］［］中給出，通過尋址就能找到節(jié)點(diǎn)n的所有扇入節(jié)點(diǎn)和扇出節(jié)點(diǎn).

2.2 算法實(shí)現(xiàn)

2.2.1 Bench 轉(zhuǎn)化為 lev的算法

轉(zhuǎn)化算法的基本流程是:逐條讀入bench文件的信息，按照Lev格式的規(guī)范進(jìn)行解析，最后生成Lev文件.流程圖如圖3所示.

圖3 Bench轉(zhuǎn)化為lev的算法流程圖Fig.3 Algorithm flow chart of bench to lev

2.2.2 電路級(jí)數(shù)算法

邏輯門的級(jí)數(shù)涉及到了電路的可測(cè)性，定義為從原始輸入到達(dá)它的各個(gè)輸入的最大邏輯門距離［13］，本文規(guī)定相鄰兩級(jí)之間的差為5，這是為了以后編寫生成測(cè)試向量程序所做的人為規(guī)定，從lev文件表示電路級(jí)數(shù)的數(shù)組中讀到0，表示為第一級(jí)門，讀到5即為第二級(jí)門，依次類推.當(dāng)然也可以采取其它間隔，如10或者15等，甚至間隔為1，只要在程序中設(shè)置好即可.流程圖如圖4所示.

2.2.3 電路可測(cè)性算法

數(shù)字電路的可測(cè)性分析包含兩層意思:一個(gè)是可控制性，一個(gè)是可觀測(cè)性［14］.可控制性定義為設(shè)置特定邏輯信號(hào)為0或者1的難度，實(shí)際操作中可控制性是指設(shè)置輸出為0和1的難度，其范圍在1和∞ 之間，值越大控制越困難.可觀測(cè)性定義為觀察邏輯信號(hào)狀態(tài)的難度，實(shí)際操作中是指輸入端的可觀測(cè)性，其范圍在0和∞之間，值越大觀測(cè)越困難.Goldstein提出了SCOAP可測(cè)性度量的概念，規(guī)定電路中的每個(gè)節(jié)點(diǎn)由6個(gè)參量來描述［11］:① 組合0可控制性 CC0(Combination Controllability);②組合1可控制性CC1;③組合可觀測(cè)性CO(Combination Observability);④時(shí)序0可控制性SC0(Sequence Controllability);⑤時(shí)序1可控制性SC1;⑥ 時(shí)序可觀測(cè)性SO(Sequence Observability).

圖4 電路級(jí)數(shù)算法流程圖Fig.4 Algorithm flow chart of circuit progression

計(jì)算可控制性的方法為:首先設(shè)置每個(gè)原始輸入的CC0和CC1均為1，然后逐級(jí)向前通過電路;每經(jīng)過一個(gè)邏輯門，表示邏輯深度增加1，可控制性就加1;如果只設(shè)置一個(gè)輸入就可以生成輸出，則輸出可控制性等于其中最小的輸入可控制性加1;如果需要設(shè)置所有的輸入才能產(chǎn)生輸出，則輸出可控制性等于所有輸入可控制性之和再加1;如果輸出被多個(gè)輸入集所控制，輸出可控制性就等于最小的輸入集可控制性加1.根據(jù)這個(gè)算法，表1列出了全部數(shù)字邏輯門的輸出節(jié)點(diǎn)的可控制性計(jì)算公式［9］.

計(jì)算出全部輸出的可控制性之后，再逆向(從原始輸出到原始輸入)計(jì)算每個(gè)輸入端的可觀測(cè)性.首先設(shè)置每個(gè)原始輸出的CO為0，然后選定一個(gè)原始輸入，計(jì)算設(shè)置其它輸入為非控制值的難度，加上輸出的可觀測(cè)性，再加邏輯深度1，就是該輸入的觀測(cè)難度.依照上述算法，表2給出了全部輸入端的可觀測(cè)性計(jì)算公式［9］.

表1 全部數(shù)字邏輯門輸出節(jié)點(diǎn)的可控制性計(jì)算公式Tab.1 Calculauion formula of combination controllability of output node of all digital logic gate

表2 全部數(shù)字邏輯門輸入端的可觀測(cè)性計(jì)算公式Tab.2 Calculation formula of combination observability of input node of all digital logic gate

由計(jì)算方式可知，CC0，CC1和CO這3個(gè)組合度量值之間是遞歸定義的，所以可以采用遞歸的方式來求解，但是如果電路的個(gè)數(shù)太多，則效率會(huì)大大降低，所以要加入記憶功能，采用記憶化搜索.

電路可控制性和可觀測(cè)性的算法流程圖如圖5所示.

圖5 電路可控制性和可觀測(cè)性計(jì)算流程圖Fig.5 Algorithm flow chart of combination controllability and combination observability

3 算法驗(yàn)證及結(jié)果分析

利用上述算法開發(fā)了軟件平臺(tái)，經(jīng)過測(cè)試C17，C432，C499，C880，C1355，C1908，C2670，C3540，C5315，C6288，C7552這11個(gè)組合邏輯電路，均可以生成正確的lev格式文件.仍以C17電路為例，所生成的lev文件描述及與bench文件的對(duì)應(yīng)關(guān)系為:

3.1 1可控制性、0可控制性、可觀測(cè)性的算法驗(yàn)證

從前面得到的C17電路的lev文件中得到了各個(gè)節(jié)點(diǎn)的1可控制性CC1，0可控制性CC0，可觀測(cè)性CO值，如表3所示.

表3 C17電路的節(jié)點(diǎn)1可控制性、0可控制性、可觀測(cè)性值Tab.3 Value of CC1，CC0，CO of C17 circuit

首先來驗(yàn)證1可控制性CC1，0可控制性CC0的正確性.由2.2.3的敘述可知，1可控制性CC1，0可控制性CC0在實(shí)際操作中是指設(shè)置輸出為1和0的難度，值越大控制越困難.從表3中的第3列和第4列數(shù)據(jù)可以得到:

1)節(jié)點(diǎn)離輸入端越遠(yuǎn)越難控制，即節(jié)點(diǎn)離原始輸入端越遠(yuǎn)，CC1和CCO應(yīng)該越大.由C17的電路圖可知，表3中節(jié)點(diǎn)由上到下的排列順序正好就是按離原始輸入遠(yuǎn)近排列的，表3的第3列和第4列數(shù)值符合這個(gè)規(guī)律.

2)lev文件中節(jié)點(diǎn)6和節(jié)點(diǎn)7以及節(jié)點(diǎn)8和節(jié)點(diǎn)9的可控制值完全相同，這個(gè)結(jié)果也完全正確，節(jié)點(diǎn)6和節(jié)點(diǎn)7對(duì)應(yīng)C17中的標(biāo)號(hào)10和11，節(jié)點(diǎn)8和9對(duì)應(yīng)C17中的標(biāo)號(hào)16和19，從C17電路圖可以看出，標(biāo)號(hào)10和11以及標(biāo)號(hào)16和19處的故障測(cè)試難度相同.

3)C17電路全部為與非門，對(duì)于與非門，設(shè)置輸出為1的難度比設(shè)置輸出為0的難度小，因此對(duì)于同一個(gè)節(jié)點(diǎn)，CC1的值比CC0的值小.表3中第三列和第四數(shù)據(jù)符合這個(gè)規(guī)律.

接著來看節(jié)點(diǎn)的可觀測(cè)性數(shù)據(jù)CO的正確性.由2.2.3中的敘述可知，可觀測(cè)性在實(shí)際操作中是指輸入端的可觀測(cè)性，值越大觀測(cè)越困難.從表3的第5列數(shù)據(jù)可以得到:

1)節(jié)點(diǎn)離原始輸出越遠(yuǎn)，節(jié)點(diǎn)的可觀測(cè)值CO越大，表3中節(jié)點(diǎn)由下到上的排列順序正好就是按離原始輸出遠(yuǎn)近排列的，表3第5列的數(shù)據(jù)基本符合這一規(guī)律，不完全符合是因?yàn)檫€有接下來2)中的原因.

2)lev文件中節(jié)點(diǎn)4的可觀測(cè)值最大，為7，這個(gè)結(jié)果也是必然的.從圖1可以看出，從原始輸出到標(biāo)號(hào)為6處經(jīng)過的門的個(gè)數(shù)最多.

3)lev文件中節(jié)點(diǎn)2和節(jié)點(diǎn)5的可觀測(cè)值CO相同，為6;節(jié)點(diǎn)1，節(jié)點(diǎn)3，節(jié)點(diǎn)7的可觀測(cè)值CO相同，為5;節(jié)點(diǎn)6，節(jié)點(diǎn)8，節(jié)點(diǎn)9的可觀測(cè)值CO相同，為3.這個(gè)結(jié)果也是必然，節(jié)點(diǎn)2和節(jié)點(diǎn)5對(duì)應(yīng)圖1中的標(biāo)號(hào)2和標(biāo)號(hào)7;節(jié)點(diǎn)1，節(jié)點(diǎn)3，節(jié)點(diǎn)7對(duì)應(yīng)圖 1中的標(biāo)號(hào)1，3，11;節(jié)點(diǎn)6，8，9對(duì)應(yīng)圖1中的標(biāo)號(hào)10，16，19.從圖1中可以看出，這些節(jié)點(diǎn)的可觀測(cè)難度應(yīng)該一致.

以上結(jié)果說明本文的可觀測(cè)性和可控制性算法及程序是正確的.

3.2 其它算法的驗(yàn)證

利用本論文的算法編寫程序?qū)η懊嫣岬降?1個(gè)組合邏輯電路進(jìn)行測(cè)試，得到的lev文件應(yīng)用于后續(xù)自動(dòng)測(cè)試向量生成中，與IEEE Circuits and Systems Society提供的測(cè)試向量生成結(jié)果完全一致［13，15］，進(jìn)一步說明了其它算法的正確性.圖6所示為測(cè)試生成平臺(tái)的運(yùn)行界面，并展示出了對(duì)C432電路的測(cè)試結(jié)果.由于篇幅關(guān)系，對(duì)上述其它10個(gè)文件未能全部展示.

圖6 測(cè)試生成平臺(tái)界面Fig.6 Interface of test generation platform

4 結(jié)論

算法驗(yàn)證及結(jié)果分析表明，本文所提出的電路描述文件轉(zhuǎn)換方法是有效的，測(cè)試結(jié)果也證明了算法及程序的正確性.不足之處在于目前所編寫的程序還沒來得及考慮程序的健壯性問題，這也是下一步需要改進(jìn)和提高的地方.

［1］薛月菊，王紅，楊士元，等.數(shù)字電路的層次化測(cè)試生成新趨勢(shì)［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2003，36(11):1281-1284.Xue Yueju，Wang Hong，Yang Shiyuan，et al.New tendency of hierarchical test generation for digital circuit［J］.Journal of Harbin Institute of Technology，2003，36(11):1281-1284.(in Chinese)

［2］成本茂，王紅，邢建輝，等.數(shù)字電路的高層測(cè)試技術(shù)及其發(fā)展［J］.微電子學(xué)，2006，36(2):187-191.Cheng Benmao，Wang Hong，Xing Jianhui，et al.High level testing of digital VLSI circuits and its developing trend［J］.Microelectronics，2006，36(2):187-191.(in Chinese)

［3］Michael L B，Vishwani D A.超大規(guī)模集成電路測(cè)試——數(shù)字、存儲(chǔ)器和混合信號(hào)系統(tǒng)［M］.蔣安平，馮建華，王新安，譯.北京:電子工業(yè)出版社，2005.

［4］Michail M，Naghmeh K.Instruction-level impact comparison of RT-vs.gate-level faults in a modern microprocessor controller［C］.USA:27th IEEE VLSI Test Symposium，2009.

［5］劉觀生，葛海通，陳偕雄.門級(jí)電路自動(dòng)測(cè)試向量生成技術(shù)原理［J］.浙江大學(xué)學(xué)報(bào)(理學(xué)版)，2006，33(1):52-56.Liu Guansheng，Ge Haitong，Chen Xiexiong.Principles of gated circuit automation test pattern generation［J］.Journal of Zhejiang University(Science Edition)，2006，33(1):52-56.(in Chinese)

［6］Michail M，Naghmeh K.Instruction-level impact analysis of low-level faults in a modern microprocessor controller［C］.USA:IEEE Transactions on Computers，2011.

［7］白玉媛，楊士元，王紅.數(shù)字電路自動(dòng)測(cè)試生成實(shí)用化軟件［J］.計(jì)算機(jī)應(yīng)用研究，2006(1):174-177.Bai Yuyuan，Yang Shiyuan，Wang Hong.Practical automat ic test generation software for digital circuits［J］.Application Research of Computers，2006(1):174-177.(in Chinese)

［8］鄧禹丹.數(shù)字電路測(cè)試生成平臺(tái)研究與可測(cè)性設(shè)計(jì)的應(yīng)用［D］.南京:南京航空航天大學(xué)，2007.

［9］劉歆.數(shù)字電路的故障測(cè)試模式生成方法研究［D］.武漢:華中科技大學(xué)，2004.

［10］羅濤.復(fù)雜數(shù)字電路板的可測(cè)性研究［D］.江蘇科技大學(xué)，2011.

［11］雷紹充，邵志標(biāo)，梁峰.VLSI測(cè)試方法學(xué)和可測(cè)性設(shè)計(jì)［M］.北京:電子工業(yè)出版社，2005.