蔡金燕， 張峻賓,2， 孟亞峰

(1. 軍械工程學(xué)院 電子與光學(xué)工程系， 石家莊 050003;2. 中國空氣動力研究與發(fā)展中心 超高速空氣動力研究所, 四川 綿陽 621000)

基于改進二分查找的VRC快速故障定位技術(shù)

蔡金燕1， 張峻賓1,2， 孟亞峰1

(1. 軍械工程學(xué)院 電子與光學(xué)工程系， 石家莊 050003;2. 中國空氣動力研究與發(fā)展中心 超高速空氣動力研究所, 四川 綿陽 621000)

針對虛擬可重構(gòu)電路(virtual reconfigurable circuits, VRC)故障定位難、傳統(tǒng)故障定位方法測試次數(shù)大等問題，提出一種基于改進二分查找的VRC快速故障定位技術(shù). 當(dāng)VRC規(guī)模不大于兩行(或兩列)時，直接逐行(逐列)定位故障. 當(dāng)VRC規(guī)模大于兩行和兩列時，首先執(zhí)行一次行測試和一次列測試，以確定可編程單元(programmable elements, PE)的故障可疑區(qū)域；然后比較故障可疑區(qū)域的行/列數(shù)量，以數(shù)量較少的作為故障測試方向；最后在測試方向上二分故障可疑區(qū)域，根據(jù)行/列測試原理配置電路并執(zhí)行“與”操作，根據(jù)輸出結(jié)果定位故障. 當(dāng)故障可疑區(qū)域無法二分時，可定位所有故障PE. 故障定位性能分析表明：和常規(guī)的VRC故障定位技術(shù)相比，本文提出的VRC快速故障定位技術(shù)能夠快速檢測并隔離連續(xù)分布的無故障PE，快速縮小測試區(qū)域，大幅度降低故障定位測試次數(shù)，且出現(xiàn)最大測試次數(shù)的概率遠小于前者，單故障和雙故障定位的平均測試次數(shù)縮減量超過50%. 基于改進二分查找的VRC快速故障定位技術(shù)的可行性和有效性得到驗證，具有一定的通用性和工程應(yīng)用價值.

硬件演化；故障定位；虛擬可重構(gòu)電路；可編程單元；二分查找

硬件演化(evolvable hardware, EHW)技術(shù)在上世紀90年代已被提出，其具有的自組織、自適應(yīng)和自修復(fù)能力在電路故障修復(fù)領(lǐng)域發(fā)揮了重要作用[1-4]. 目前常將現(xiàn)場可編程門陣列(field programming gate array, FPGA)作為實現(xiàn)EHW的硬件基礎(chǔ)，但由于FPGA生產(chǎn)商均為外企，對外實行技術(shù)封鎖，除Xilinx的Virtex2系列芯片外，學(xué)者不能夠自由的訪問/控制FPGA內(nèi)部邏輯單元和開關(guān)盒[5-8]，對EHW技術(shù)的發(fā)展造成一定影響. 因此虛擬可重構(gòu)電路(virtual reconfigurable circuits, VRC)應(yīng)運而生[9-11]，其能夠克服以上問題.

VRC與故障自修復(fù)領(lǐng)域中的胚胎電子細胞都是可編程陣列[12-14]，因而具有相似性；由于可編程單元(programmable elements, PE)內(nèi)部結(jié)構(gòu)和PE間互聯(lián)不同，又具有差異性. 雖然現(xiàn)有偽窮舉測試法、布爾差分法、D算法等故障定位方法[15-17]，但都針對具體電路，需輸入測試序列. 而VRC結(jié)構(gòu)具有特殊性，使得數(shù)字電路常用測試方法不適用. 常規(guī)的VRC故障定位方法主要進行逐行(列)測試，且需對PE的所有邏輯功能進行測試，因此VRC的行(列)數(shù)決定了測試的次數(shù)，容易造成測試次數(shù)大等問題. 一些文獻提出將可能存在故障的行(列)所有PE單獨連接至無故障的行(列)進行測試，在故障可能存在的行(列)較少時，且無故障行(列)較多和每行(列)的PE數(shù)量較少時才使用，否則將無足夠無故障行(列)供使用[18]. 另有很多文獻只研究VRC的使用，而回避VRC故障定位[9-10, 19].

本文提出一種基于改進二分查找的VRC快速故障定位技術(shù). 首先采用一次行測試和一次列測試確定故障可疑區(qū)域，然后根據(jù)故障可疑區(qū)域的規(guī)模確定測試方向，最后采用二分查找技術(shù)對故障可疑區(qū)域進行故障定位. 通過對本文提出的故障定位方法進行性能分析，所提方法的可行性和有效性得到驗證.

1 VRC平臺基本原理

EHW技術(shù)主要有內(nèi)部演化(intrinsic EHW)和外部演化(extrinsic EHW) 兩種方式. 而基于VRC的電路演化平臺，也包含內(nèi)部演化和外部演化兩種演化方式[1, 2, 4, 20].

VRC是一種基于FPGA中可編程邏輯單元重新封裝后的可重構(gòu)平臺[9-11, 19]，是由多個PE構(gòu)成陣列，也稱PE為function elements(FE)[9]. 每個PE可實現(xiàn)任意二輸入邏輯功能，其中包括與、或、非、異或、與或、同或、與非、或非、D觸發(fā)器共8種邏輯. 有些文獻設(shè)計的PE只包含8種邏輯中的部分邏輯. VRC構(gòu)成示意見圖1.

圖1 VRC構(gòu)成示意

圖1中的a和b為輸入信號，c為輸出信號，fFD為PE功能表達配置數(shù)據(jù)，clk為時鐘. VRC平臺中的PE還可具有圖2所示結(jié)構(gòu)[19]，同圖1(a)中的PE結(jié)構(gòu)具備相同功能. PE互聯(lián)網(wǎng)絡(luò)示意見圖3.

圖2 另一種PE內(nèi)部結(jié)構(gòu)示意

圖3 VRC互聯(lián)網(wǎng)絡(luò)示意

從圖3可看出，針對規(guī)模為M行N列的VRC，每個PE的輸出端均互聯(lián)至整個VRC，每個PE的每個輸入端均有一個M×N到一的多路選擇器(multiplexer, MUX)，將所有PE輸出端連接至具有M×N個輸入一個輸出的MUX，使得VRC中每個PE輸出端能夠接入任意PE的輸入端.

對MUX的M×N個輸入端進行二進制計算，對應(yīng)的位數(shù)為所有MUX控制信號的編碼長度. 假如M×N=60，其二進制編碼為111 100，控制MUX的信號編碼長度為6位.

2 基于改進二分查找的VRC快速故障定位技術(shù)

本文提出的基于改進二分查找的VRC快速故障定位技術(shù)的主要原理如下：首先實施一次行測試和一次列測試確定故障可疑區(qū)域，再采用二分查找技術(shù)對故障可疑區(qū)域進行故障定位.

對VRC實施行/列測試的PE連接/配置方法分別見圖4和圖5.

圖4 VRC行測試配置方法

圖5 VRC列測試配置方法

圖4和圖5中的yr1～yr5和yc1～yc6分別對應(yīng)行測試和列測試的每路輸出信號. 行/列測試時通過改變輸入端a和b的值，保證每個PE能將邏輯1順利輸出到端口. 比如在測試PE的邏輯“與”功能時，輸入信號a和b需同時輸入1，或同時輸入0. 如果輸入1時輸出為1，且輸入0時輸出為0，代表無故障，反之則有故障. 將經(jīng)過行測試和列測試后的交叉區(qū)域記為故障PE可疑區(qū)域見圖6.

圖6 VRC故障PE可疑區(qū)域

經(jīng)過行測試后，確定第2～4行存在故障；經(jīng)過列測試后，確定第2～5列存在故障. 此時的故障可疑區(qū)域不只一行和一列.

在基于行測試、列測試和故障可疑區(qū)域基礎(chǔ)之上，基于改進二分查找的VRC快速故障定位技術(shù)實現(xiàn)流程如下：

Step1首先進行行測試和列測試，確定故障可疑區(qū)域.

Step2判斷VRC故障可疑區(qū)域的大小，假設(shè)可疑區(qū)域規(guī)模為m行n列，且m≤n. 判斷VRC不在可疑區(qū)域內(nèi)的PE(即無故障PE)數(shù)量k，如果k≥n，轉(zhuǎn)入Step3；反之，則轉(zhuǎn)入Step6.

Step3采用二分查找法，將可疑區(qū)域每一列平分(偶數(shù)直接平分，奇數(shù)平分時一邊可多一個PE)，分別按圖5方式縱向連接，并將兩路信號送入此列無故障PE進行“與”操作. 如果此列沒有無故障PE，則選擇其它列多余的無故障PE進行“與”操作. 如果輸出值為1，判定上/下兩部分均存在故障，并轉(zhuǎn)入Step4；如果輸出值為0，判斷上/下部分中有一部分存在故障，并轉(zhuǎn)入Step5.

Step4當(dāng)平分后的上/下兩部分均存在故障時，對上部分進行再次平分，按照Step3的步驟進行故障定位. 在上部分故障定位完畢后，再對下部分故障定位. 依此進行，直到可疑區(qū)域的故障完全定位為止.

Step5當(dāng)平分后的上/下兩部分只有一部分存在故障時，首先測試上/下部分的任意部分. 如果測試出上部分(下部分)無故障，則下部分(上部分)必存在故障，此時測試次數(shù)將大大縮減.

Step6在Step2中確定可疑區(qū)域后，當(dāng)k

在上述測試流程中，如果VRC中故障PE只存在某一行或某一列，只需一次行測試和一次列測試即可定位故障. 詳細的二分法查找過程見圖7.

圖7 極端情形下二分查找故障定位過程

Fig.7 Binary search process of fault localization under extreme circumstances

圖7所示測試步驟包含極端情形下的測試次數(shù)，將可疑區(qū)域中的某一行分離出來單獨演示，包含7個PE，分別用字母D1～D7表示，測試點用f1～f10表示. 在非極端情形下，圖7中一些測試步驟可省略. 此時的極端情形主要指：在二分過程中且還未最小二分時，兩側(cè)測試始終顯示有故障；在最小二分時，兩側(cè)測試顯示無故障.

圖7中f1、f2屬于中間過程的二分，而f3、f5、f7和f8屬于最小二分，且以上均屬于節(jié)點測試，f4、f6、f9和f10屬于邏輯塊功能測試. 圖7中只要D7無故障，且D1和D2、D3和D4、D5和D6每對中只要有一個故障，將造成最大測試次數(shù). 即至少存在4個故障PE，相當(dāng)于至少4/7的PE出現(xiàn)故障，而4/7的PE出現(xiàn)故障的概率極小.

3 故障定位性能分析

故障定位性能分析，主要關(guān)注故障全部定位情況下的測試次數(shù)，通常情況下，測試次數(shù)越少越好. 常規(guī)測試方法需進行逐行(或逐列)測試. 在對比分析中，設(shè)定測試順序從上至下(從左至右). 針對VRC規(guī)模為M行N列，且M≤N，常規(guī)的故障定位方法最大測試次數(shù)為M次. 本文提出的基于改進二分查找的VRC快速定位技術(shù)，在極端情形下的最大測試次數(shù)為G(x)，其中x代表圖6中故障可疑區(qū)域的行數(shù)和列數(shù)的最小值，不是VRC中故障PE的數(shù)量(用h表示，h∈N+).

在故障定位過程中，確定故障可疑區(qū)域需要測試兩次. 當(dāng)PE數(shù)量取2的對數(shù)為整數(shù)時(即PE數(shù)量等于2x，x∈N+)，極端情形下需測試分界點，x個PE有x-1個分界點，需測試x-1次. 當(dāng)兩個PE為一組時，x個PE最后細分為0.5x等分. 對每個等分進行故障確認需測試1次，測試次數(shù)合計為1.5x+1. 在x個PE基礎(chǔ)上，每增加1個PE，測試次數(shù)將增加兩次(1次分界點測試，1次確認測試)；在x個PE基礎(chǔ)上增加的PE數(shù)量多余0.5x時，每增加1個PE將增加1次測試(分界點測試). 因此，G(x)為

G(x)=

(1)

相比傳統(tǒng)的故障定位方法，雖然本文提出的故障定位技術(shù)在極端情形下的測試次數(shù)最大增加約一半，但只存在于極端情況下，即整個VRC陣列均存在故障. 在當(dāng)VRC出現(xiàn)故障PE數(shù)量占VRC總PE數(shù)量≤50%時，本文提出的VRC快速故障定位技術(shù)將具有明顯的優(yōu)勢.

由于VRC陣列PE的結(jié)構(gòu)一樣，因此出現(xiàn)故障概率也一樣. 假設(shè)一個PE出現(xiàn)故障的概率為p，則k個PE出現(xiàn)故障的概率服從二項分布，且為

(2)

式中:X為PE總數(shù)，λ為失效率，t為工作時間，p=1-e-λt. 當(dāng)λ=1×10-5、t=24×365、λ分別為3個不同失效率值、故障PE概率累積量大于99%時，h與X的比值為phX見圖8.

圖8 概率累積量大于99%時故障PE數(shù)量占總數(shù)量百分比

Fig.8 Ratio of the number of fault PE of total number when probability cumulant is larger than 99%

圖8中，隨著VRC規(guī)模的增大，無論λ是0.8×10-5、1.0×10-5還是1.2×10-5，phX始終呈下降趨勢，且慢慢趨于穩(wěn)定. 當(dāng)X≤4時，故障PE數(shù)量占總PE數(shù)量的百分比才會超過50%.

當(dāng)X<4時，PE只能排成一行或一列，采用本文提出的故障定位技術(shù)，只需兩次測試. 當(dāng)X=4時，如果4個PE排成一行或一列，只需兩次測試. 但如果4個PE呈兩行兩列的陣列排列時，取消可疑區(qū)域測試，只進行二分查找測試，需測試兩次. 當(dāng)X>4時，X越大，不到50%的PE存在故障的概率為0.99，當(dāng)VRC規(guī)模大于200個時，少于20%的PE存在故障的概率為0.99. 此時，本文提出的故障快速定位技術(shù)將具有明顯優(yōu)勢.

對于規(guī)模為10×10的VRC，只有當(dāng)h>14時，且在特定故障布局下，才可能造成最大測試次數(shù)，見圖9.

(a) 示例一 (b) 示例二

圖9中只給出了兩種故障PE分布示意圖. 其中，深色方塊代表故障PE，白色方塊代表無故障PE. 造成最大測試次數(shù)的必要條件如下：一是有一列或一行中每隔一個PE必須存在故障，而間隔中的PE可有故障也可無故障. 二是除開當(dāng)前列(行)，剩余的故障PE不能出現(xiàn)在同一行或同一列. 圖10 展示了不同h值造成相同故障可疑區(qū)域的示例.

(a) 故障頒布一 (b) 故障頒布二 (c) 故障頒布三

Fig.10 Instances of the same fault PE shadiness area under different value ofh

造成最大測試次數(shù)單獨列出現(xiàn)的最少故障數(shù)量為H(x)

(3)

造成最大測試次數(shù)的可疑區(qū)域最小h值用為H1(x)

H1(x)=H(x)+x-1x∈N+.

(4)

深入研究規(guī)模為10×10的VRC，采用常規(guī)方法進行故障定位，當(dāng)從上至下定位時，只要最后一行出現(xiàn)故障，將造成最大測試次數(shù). 對應(yīng)不同h值造成最大測試次數(shù)的概率用P1(x)為

(5)

在采用本文提出的方法時，按照式(3)和式(4)的計算規(guī)則，故障PE可疑區(qū)域為10×10的最小h=13. 其不同h值造成最大測試次數(shù)的概率為P2(x)

(6)

式(6)中的P3(x)可表示為

(7)

從式(6)、(7)可看出，當(dāng)x∈[1,13],x∈N+時，式(6)屬于精確計算，當(dāng)x≥14,x∈N+時，式(6)屬于近似范圍計算. 當(dāng)計算的近似值比真值大時，造成最大測試次數(shù)概率遠遠低于常規(guī)方法造成最大測試次數(shù)的概率.

令每個PE的失效率λ=1.0×10-5，t=24×365，VRC不同數(shù)量PE出現(xiàn)故障的概率和對應(yīng)的概率累積量見圖11.

圖11 VRC不同數(shù)量故障PE故障出現(xiàn)概率及概率累積量

Fig.11 Fault probability and fault probability cumulant of VRC in different number of PEs

從圖11中可看出，當(dāng)VRC的故障PE概率累積量達到99.9%時，對應(yīng)有min(h)=18. 因此只計算最多18個PE出現(xiàn)故障，故障定位相關(guān)參數(shù)見表1，表1中造成最大測試次數(shù)的故障分布和故障隨機分布的比率用S表.

表1 VRC陣列(規(guī)模為10×10)故障定位相關(guān)參數(shù)

從表1可看出，常規(guī)故障定位方法最大測試次數(shù)始終為10次. 本文提出的故障定位方法最大測試次數(shù)，在h<7時明顯低于前者. 當(dāng)h≥7時大于前者，最大增加量約為一半. 但本文提出的方法造成最大測試次數(shù)的故障PE需特殊布局，且相同數(shù)量故障PE特殊布局所出現(xiàn)的概率. 在h=7時，常規(guī)方法是本文提出方法的118倍；h=10時是3.19×106倍；h=13是2.34×107倍；即使在近似計算h=18時，前者也為后者的5.03×103倍.

當(dāng)h值確定時，常規(guī)故障定位方法始終有S=0.1. 采用本文提出的方法，當(dāng)h≤6時，雖然S>0.1，但是此時的最大測試次數(shù)小于常規(guī)方法的測試次數(shù). 當(dāng)h>6時，雖然最大測試次數(shù)大于常規(guī)測試方法，但此時S遠小于0.1，之間差距從40倍到3.06×106倍不等.

排除極端情形下造成最大測試次數(shù)，當(dāng)實例中h≤6時，只要VRC最后一行存在故障PE，常規(guī)方法的測試次數(shù)大于本文提出的方法. 如果7個故障PE全在第一行，本文提出的故障定位方法將需兩次測試，而常規(guī)方法只需一次測試，但是7個故障全在第一行的概率只有7.50×10-8. 當(dāng)h>6時，需根據(jù)具體的故障PE分布分析故障測試次數(shù). 常規(guī)方法存在10%造成最大次數(shù)的概率，雖然本文提出的方法存在最大測試次數(shù)大于常規(guī)方法的可能性，但其概率低于1.94×10-4，甚至更小.

例如，當(dāng)VRC陣列只有1個故障時，常規(guī)方法檢測次數(shù)少于兩次的概率為20%，即80%的檢測次數(shù)都大于2次. 而采用本文提出的方法，測試次數(shù)只使用兩次. 對于雙故障，常規(guī)方法93.03%的檢測次數(shù)大于4次. 而采用本文提出方法的最大測試次數(shù)為4次(2次測試占3.64%，4次測試占96.36%).

當(dāng)h=7時，如圖12所示的故障分布. 由于每個故障分布在不同的行和列，常規(guī)測試方法需進行10次測試，才能將7個故障PE完全定位. 而采用本文方法只需進行8次測試，中間3行連續(xù)分布的無故障PE得到快速隔離.

圖12 VRC中7個故障PE分布

綜上所述，故障定位的測試次數(shù)和故障PE的分布密切相關(guān). 常規(guī)故障定位方法，無論某行/列是否存在故障PE，均需要測試一次. 本文提出的故障定位方法能夠?qū)o故障的行/列排除，只對故障可疑區(qū)域進行二分查找測試，從而降低故障測試次數(shù).

4 結(jié) 論

針對目前VRC陣列故障定位方法單一、故障定位難及定位測試次數(shù)大等問題，本文提出一種基于改進二分查找的VRC快速故障定位技術(shù).

和常規(guī)故障定位技術(shù)相比，本文提出的故障快速定位技術(shù)能夠避免對連續(xù)分布的無故障PE進行測試，縮小測試區(qū)域，且造成最大測試次數(shù)的概率遠小于前者，對單故障和雙故障定位時的測試次數(shù)縮減量超過50%.

通過故障定位性能分析，本文提出的基于改進二分查找的VRC快速故障定位技術(shù)的可行性和有效性得到驗證，具有一定通用性和工程應(yīng)用價值.

[1] PAULINE C H, ANDY M T. Challenges of evolvable hardware: past, present and the path to a promising future[J]. Genetic Programming and Evolvable Machines, 2011, 12(3): 183-215.

[2] HORNBY G S, LOHN J D, LINDEN D S. Computer- automated evolution of an x-band antenna for NASA's space technology 5 mission[J]. Evolutionary Computation, 2011, 19(1): 1-23.

[3] HIHUCHI T, IWATA M, KAJITANI I, et al. Evolvable hardware and its applications to pattern recognition and fault tolerant systems[J]. Lecture Notes in Computer Science, 1996, 1062:118-135.

[4] ZHANG Junbin, CAI Jinyan, MENG Yafeng, et al. Fault self-repair strategy based on evolvable hardware and reparation balance technology[J]. Chinese Journal of Aeronautics, 2014, 27(5): 1211-1222.

[5] YAN S L, CHEN Y, PU Q M. A new evolutionary hardware system using FPGAS[C]//Proceeding of International Colloquium on Computing, Communication, Control, and Management. Piscataway, NJ: IEEE Press, 2009: 82-85.

[6] LOPEZ-BUEDO S, GARRIDO J, BOEMO E I. Dynamically inserting, operating, and eliminating thermal sensors of FPGA-based systems[J]. IEEE Transactions on Components and Packing Technologies, 2002, 25(4): 561-566.

[7] DAS N, ROY P, RAHAMAN H. Runtime congestion and crosstalk aware router for FPGA using jbits3.0 for partial reconfigurable[C]//Proceeding of International Symposium on Electronic System Design. Piscataway, NJ: IEEE Press, 2011: 146-151.

[8] 任小西, 李仁發(fā), 金聲震, 等. 基于JBits的一種可重構(gòu)數(shù)據(jù)處理系統(tǒng)可靠性研究[J]. 計算機研究與發(fā)展, 2007, 44(4): 722-728.

REN Xiaoxi, LI Renfa, JIN Shengzhen, et al. Research on reliability of a reconfigurable data processing system based on jbits[J]. Journal of Computer Research and Development, 2007, 44(4): 722-728.

[9] WANG Jin, LEE C H. Virtual reconfigurable architecture for evolving combinational logic circuits[J]. Journal of Central South University, 2014, 21(5): 1862-1870.

[10]OMAR E, IMBABY I M, MOHAMED K R, et al. Hardware implementation of virtual reconfigurable circuit for fault tolerant evolvable hardware system on FPGA[J]. American Journal of Engineering and Technology Research, 2015, 15(1): 2015.

[11]樸昌浩, 王進, 孫志華, 等. 自適應(yīng)變異比率控制在虛擬可重構(gòu)結(jié)構(gòu)中的應(yīng)用[J]. 高技術(shù)通訊, 2010, 20(4): 398-402.

PIAO Changhao, WANG Jin, SUN Zhihua, et al. Applying self-adaptive mutation rate control to virtual reconfigurable architecture[J]. Chinese High Technology Letters, 2010, 20(4): 398-402.

[12]蔡金燕, 朱賽, 孟亞峰. 一種新型的仿生電子細胞基因存儲結(jié)構(gòu)[J]. 電子學(xué)報, 2016, 44(8): 1915-1924.

CAI Jinyan, ZHU Sai, MENG Yafeng.A novel gene memory structure for bio-inspired electronic cell[J]. Acta Electronica Sinica, 2016, 44(8): 1915-1924.

[13]王南天, 錢彥嶺, 李岳, 等. 胚胎型在線自修復(fù)FIR濾波器研究[J]. 儀器儀表學(xué)報, 2012, 33(6): 1385-1391.

WANG Nantian, QIAN Yanling, LI Yue, et al. Study of embryonic type on-line self-healing FIR filters[J]. Chinese Journal of Scientific Instrument, 2012, 33(6): 1385-1391.

[14]XU Guili, XIA Zhenghao, WANG Haibin, et al. Design of embryo-electronic systems capable of self-diagnosing and self-healing and configuration control[J]. Chinese Journal of Aeronautics, 2009, 22(6): 637-643.

[15]朱敏, 王石記, 楊春玲. 改進Tent混沌序列的數(shù)字電路BIST技術(shù)[J]. 哈爾濱工業(yè)大學(xué)學(xué)報, 2010, 42(4): 607-611.

ZHU Min, WANG Shiji, YANG Chunling. BIST technique of digital circuits based on improved tent chaotic sequence[J]. Journal of Harbin Institute of Technology, 2010, 42(4): 607-611. DOI: 10.11918/j.issn. 0367-6234.2010.04.022.

[16]楊德才,陳光礻禹, 謝永樂. 進位保留陣列乘法器的一種內(nèi)建自測試[J]. 電子科技大學(xué)學(xué)報, 2007,36(4):751-754.

YANG Decai, CHEN Guangju, XIE Yongle. A built-in self-test scheme for carry save array multiplier[J]. Journal of University of Electronic Science and Technology of China, 2007, 36(4): 751-754.

[17]潘張鑫, 陳偕雄. 或-符合型通用邏輯門組合電路的故障檢測[J]. 浙江大學(xué)學(xué)報(工學(xué)版), 2007, 41(8): 1260-1264.

PAN Zhangxin, CHEN Xiexiong. Faults detection in combinational circuits of OR-coincidence type universal logic gates[J]. Journal of Zhejiang University (Engineering Science), 2007, 41(8): 1260-1264.

[18]婁建安, 崔新風(fēng), 褚杰. 基于類神經(jīng)網(wǎng)絡(luò)模型的電路自主修復(fù)方法[J]. 軍械工程學(xué)院學(xué)報, 2010,22(6):46-49.

LOU Jian'an, CUI Xinfeng, CHU Jie. Self-repairing method of the electronic circuit based on neural network model[J]. Journal of Ordnance Engineering College, 2010, 22(6): 46-49.

[19]張峻賓, 蔡金燕, 孟亞峰. 面向復(fù)雜電磁環(huán)境的容錯電路系統(tǒng)設(shè)計技術(shù)[J]. 西安交通大學(xué)學(xué)報, 2017, 51(2): 53-59.

ZHANG Junbin, CAI Jinyan, MENG Yafeng. A design technology of fault tolerance circuit systems facing complex electromagnetic environments[J]. Journal of Xi′an Jiaotong University, 2017, 51(2): 53-59.

[20]李杰,黃士坦. 可進化硬件的動態(tài)進化[J]. 武漢大學(xué)學(xué)報, 2008, 41(6): 103-107.

LI Jie, HUANG Shitan. Dynamic evolution for evolvable hardware[J]. Engineering Journal of Wuhan University, 2008, 41(6): 103-107.

RapidfaultlocalizationtechnologyofVRCbasedonimprovedbinarysearch

CAI Jinyan1, ZHANG Junbin1,2, MENG Yafeng1

(1. Department of Electronic and Optical Engineering, Ordnance Engineering College, Shijiazhuang 050003, China;2. China Aerodynamics Research & Development Center, Hypervelocity Aerodynamics Institute, Mianyang 621000, China)

According to difficult fault localization of virtual reconfigurable circuits (VRC) and large test times of traditional fault localization technology, a novel rapid fault localization technology of VRC based on improved binary search is proposed. When the scales of VRC are no more than two rows (or two columns), fault PE can be located line by line (or column by column). When the scales of VRC are larger than two rows and two columns, the fault dubitable area of programmable elements (PE) can be confirmed by one row-test and one column-test, and then the test direction can be confirmed through the number of rows and columns of fault dubitable area. Eventually, fault dubitable area can be divided equally in the test direction, and two parts can be configured based on the theory of row-test and column-test. Faults can be located by “AND” operation of two parts. All faults PE can be located until fault dubitable area can not divided two parts. Compared with traditional VRC fault localization technology, the test performance analysis of fault localization proves that continuous distribution trouble-free PE can be detected and isolated by proposed VRC fault localization technology, and test area can be narrowed quickly. The test number of faults localization can be reduced, and the maximum test numbers are smaller than former. The average decrement of single and dual fault localization test number is more than 50%. The feasibility and validity of proposed improved rapid fault localization technology are proved, and it has definite generality and engineering application value.

evolvable hardware (EHW); fault localization; virtual reconfigurable circuits(VRC); programmable elements(PE); binary search

10.11918/j.issn.0367-6234.201612042

TP302.8

A

0367-6234(2017)11-0151-07

2016-12-9.

國家自然科學(xué)基金(61372039, 61601495)

蔡金燕(1961—)，女，教授，博士生導(dǎo)師

蔡金燕，cjyrad@163.com

(編輯苗秀芝)