李可長

(柳州職業(yè)技術(shù)學(xué)院，廣西 柳州 545006)

未知邏輯的故障電路快速重構(gòu)算法研究

李可長

(柳州職業(yè)技術(shù)學(xué)院，廣西 柳州 545006)

針對未知邏輯的故障電路診斷與修復(fù)問題，研究了一種以同樣功能的正常電路作為參考電路，然后利用電路邏輯快速重構(gòu)算法進(jìn)行故障修復(fù)的方法。該算法將對參考電路的邏輯功能采集與故障電路的邏輯功能重構(gòu)同步進(jìn)行，既能降低算法運(yùn)行過程中的空間消耗，同時也避免了故障電路邏輯功能重構(gòu)過程中，進(jìn)行復(fù)雜的邏輯綜合。此外該算法改進(jìn)了傳統(tǒng)的分塊串行處理模式，解決了將采集數(shù)據(jù)分塊并行邏輯綜合的問題，提高了故障電路重構(gòu)的速度。測試表明，相對直接的Q－M邏輯綜合算法，該算法處理時間最快能減少70%。

故障修復(fù);電路重構(gòu);邏輯綜合;速度;參考電路

0 前言

電路故障診斷與修復(fù)是一項涉及信號采集、信號處理、故障建模、邏輯推理等多種專業(yè)技術(shù)、難度較大的工作，然而，在現(xiàn)實應(yīng)用中，由于元器件老化、操作不當(dāng)、外部短路等各種因素都可能導(dǎo)致電路故障［1］。對于組合邏輯出現(xiàn)的故障，目前常用的方法是自動測試圖(Automatic test pattern generation，以下簡稱ATPG)的測試方法，該方法通過預(yù)先存儲好的測試向量依次施加至被測電路，檢測電路中的響應(yīng)與測試向量中的是否一致［2，3］。該方法應(yīng)用前提是測試者用于被測電路的ATPG，即相當(dāng)于測試者掌握了被測電路的設(shè)計細(xì)節(jié)。然而，對于被測電路詳細(xì)邏輯功能未知的情況，如何有效地對被測電路進(jìn)行診斷并修復(fù)，是電路故障診斷中很少被涉及的領(lǐng)域。目前相關(guān)研究也不多，主要集中在一些表面的異常診斷方式，比如檢測電路是否短路、阻抗是否有異常［4－6］。而如果是深層次的一些邏輯功能故障，則難以被檢測到，更無法進(jìn)行功能修復(fù)［7，8］。然而，在我國目前應(yīng)用的電子設(shè)備中，由于各種因素，在故障診斷時獲取其完整的ATPG并不容易，比如電子設(shè)備從國外進(jìn)口本身不提供ATPG、或者一些早期非正規(guī)企業(yè)開發(fā)的電路系統(tǒng)，也沒有完善的ATPG。如果能夠為這類設(shè)備提供有效的故障診斷修復(fù)功能，可以大幅延長這類設(shè)備的使用壽命，提高設(shè)備綜合利用率［9］。本文將研究針對未知邏輯電路故障診斷修復(fù)的方法，對提出的功能重構(gòu)方案中，重點分析和設(shè)計一種快速、高效的邏輯數(shù)據(jù)綜合算法。

1 未知邏輯電路故障功能重構(gòu)方案

針對未知邏輯功能的電路進(jìn)行故障檢測和修復(fù)難度非常大，由于被檢測電路的邏輯功能和關(guān)系式都未知，因此很難對存在故障的電路進(jìn)行有效的測試與分析［10，11］。為了解決這一問題，一種可行的方案是以功能相同的正常電路作為參照電路，并將正常功能的電路與故障電路的功能作對比，從而實現(xiàn)對故障電路的檢測和修復(fù)。參考電路的功能雖然正常，但在實際應(yīng)用中，其內(nèi)部設(shè)計的邏輯關(guān)系式并不對用戶公開，用戶只了解該邏輯電路在總體上完成某一特定功能，對其邏輯關(guān)系式同樣是未知的。因此本文設(shè)計的檢測方案如下:對正常功能的參考電路進(jìn)行邏輯功能采集，即對該電路的所有輸入引腳施加激勵信號，并采集電路產(chǎn)生的響應(yīng)信號，當(dāng)激勵信號遍歷所有可能的組合情況，則可采集到邏輯電路在任一激勵條件下的響應(yīng)信號，即邏輯電路的完整邏輯功能關(guān)系。整體處理方案過程圖如圖1所示。

圖1 未知邏輯電路故障功能重構(gòu)方案過程圖

假設(shè)未知電路的實際邏輯關(guān)系式為F，其涵蓋的激勵響應(yīng)邏輯關(guān)系集合為SX，對參考電路的邏輯功能采集到的激勵響應(yīng)邏輯集合為SC，由于SC是對所有激勵信號的采集結(jié)果，所以SX?SC，即SC中的數(shù)據(jù)對于故障邏輯電路滿足完備性，因此，通過對SX邏輯綜合得到的關(guān)系式必定涵蓋了F。此外，在對參考電路的激勵響應(yīng)數(shù)據(jù)采集時，進(jìn)行數(shù)據(jù)的重復(fù)性檢測，重復(fù)的數(shù)據(jù)不被保存進(jìn)集合。當(dāng)然，數(shù)據(jù)重復(fù)性的檢測在一定程度上可以通過選擇合理的激勵信號施加順序解決。因為在激勵信號施加時，假如使激勵信號(i1，i2，…，ik)按照(00…0)→(11…1)的順序依次施加，則可保證施加的激勵信號完整，且也不會出現(xiàn)重復(fù)。而按照組合邏輯電路的輸入輸出關(guān)系可知，對于一個給定的激勵信號，其響應(yīng)信號也是固定的，因此，這種激勵施加方式在邏輯電路輸入端明確的情況下，其采集到的激勵響應(yīng)數(shù)據(jù)向量不會出現(xiàn)重復(fù)。由此可知SC中的數(shù)據(jù)之間滿足正則性，即邏輯關(guān)系式F中的任意一個真值表項在Sc中有且僅有一個(含補(bǔ)碼形式)。

雖然有SX?SC，對SC中的數(shù)據(jù)進(jìn)行邏輯綜合即可得到邏輯關(guān)系式FC，而F?FC，，即用FC生成替換芯片完全可以代替故障電路，實現(xiàn)對未知邏輯的故障電路修復(fù)。然而Sc中的數(shù)據(jù)包括了所有激勵的情況，其數(shù)據(jù)規(guī)模是2n，n為輸入信號的個數(shù)。當(dāng)n較大時，SC邏輯綜合消耗的時間呈指數(shù)增長。目前經(jīng)典的邏輯綜合算法主要有Q－M算法、銳積算法和廣義相容算法。這些算法對小規(guī)模數(shù)據(jù)處理效率還能接收，但對于大規(guī)模數(shù)據(jù)的處理時間和空間復(fù)雜度太高，難以實現(xiàn)。目前已經(jīng)有改進(jìn)的Q－M算法、Q－M與銳積算法相結(jié)合的算法，算法效率有一些提高(時間復(fù)雜度為O(N)2)。但是這些處理算法中對數(shù)據(jù)分塊處理都存在一個問題，即分塊后處理的中間結(jié)果將作為下一塊數(shù)據(jù)處理的輸入?yún)?shù)，因此各個數(shù)據(jù)分塊之間處理必須串行進(jìn)行，這極大限制了邏輯綜合速度的提高。為此，本文將對數(shù)據(jù)間分塊串行處理的模式進(jìn)行研究，設(shè)計的邏輯綜合算法能夠支持?jǐn)?shù)據(jù)分塊的并行處理，以提高算法的整體運(yùn)行速度。

2 數(shù)據(jù)采集與分塊邏輯綜合同步處理算法

2.1 算法原理

針對電路功能重構(gòu)過程中采集的數(shù)據(jù)量龐大等問題，本文設(shè)計的未知功能故障電路重構(gòu)算法的基本思想是在對參照電路進(jìn)行功能數(shù)據(jù)采集時，同步進(jìn)行數(shù)據(jù)的邏輯綜合，降低數(shù)據(jù)處理的空間量，以漸進(jìn)式的邏輯功能逼近策略，實現(xiàn)對參照電路的功能重構(gòu)。但由于對參照電路中采集的數(shù)據(jù)量龐大，數(shù)據(jù)之間的關(guān)系是離散的，而按照邏輯綜合的相關(guān)理論，只有將空間盡可能相交的立方體數(shù)據(jù)進(jìn)行綜合，才可能使邏輯綜合的空間增長不至于過快，這也有利于降低其對后續(xù)數(shù)據(jù)的邏輯綜合計算量［12］。因此，這一處理算法的關(guān)鍵是如何設(shè)計高效的將采集數(shù)據(jù)分塊，并逐步累積生成中間結(jié)果，最終逼近得到參照電路的完整邏輯功能表達(dá)式。

設(shè)計數(shù)據(jù)采集和分塊邏輯綜合同步處理算法之前，首先需要借鑒邏輯綜合中的Demorgan定理［13］，該定律給出了待邏輯綜合的立方體數(shù)據(jù)之間銳積關(guān)系式。假設(shè)有待邏輯綜合的立方體數(shù)據(jù)A、B、C，用“#”表示銳積運(yùn)算。則有式(1)關(guān)系式:

假設(shè)對參考電路共有n個信號引腳，對該電路采集的所有不重復(fù)的激勵和響應(yīng)之間的向量數(shù)據(jù)集合S={V1，V2，…，Vt}，其中 Vi=(I1I2…IkO1O2…Oj)，Im∈(0，1)，Qp∈(0，1)，m=1，2，…k，p=1，2，…，j，k+j=n.對集合S中的數(shù)據(jù)進(jìn)行邏輯綜合時，令Son表示on點集合，Soff表示off點集合，SDC表示DC項集合，有S=Son∪Soff∪SDC.

由于對參考電路中的邏輯數(shù)據(jù)是分散采集的，因此數(shù)據(jù)集合可以由若干個小集合組成。S={S1，S2，…，St}，又因為數(shù)據(jù)采集時同時對數(shù)據(jù)的重復(fù)性進(jìn)行了監(jiān)測，相同的數(shù)據(jù)向量不被送入集合中，因此有Si∩Sj=Φ。有邏輯綜合的集合運(yùn)算關(guān)系有:

事實上，式(4)給出了對參考電路邏輯綜合的一般遞推式。令X0=S，此S為最初采集到的原始數(shù)據(jù)向量集合。

X1=S#Soff1=Son∪SDC∪Soff2∪Soff3∪…∪Sofft，將此式計算結(jié)果與X0求交后作為新的X0值，即X0=X1∩X0.同樣的方法計算X2，并更新X0的值，依次類推，有:

最終可計算得到:Xt=S#Sofft=Son∪SDC∪Soff1∪Soff2∪…∪Sofft－1，X0=Xt∩X0

此時得到的X0即為對參考電路數(shù)據(jù)邏輯綜合的結(jié)果，即所有采集的數(shù)據(jù)集合的ON點集合與DC點集合的并集。

2.2 算法步驟

根據(jù)上面分析的算法原理，本文設(shè)計的數(shù)據(jù)采集與分塊邏輯綜合同步處理算法流程圖如圖2所示。

步驟1:初始化集合S，即將采集的第一塊數(shù)據(jù)項賦值給S。

步驟2:判斷數(shù)據(jù)采集是否完成，如果數(shù)據(jù)采集已完成，則退出，直接輸出當(dāng)前結(jié)果，若沒有，則繼續(xù)處理新的數(shù)據(jù)塊。

步驟3:接收一個新的數(shù)據(jù)塊，并提取出該數(shù)據(jù)塊中所有響應(yīng)的Soffi，隨后對Soffi集合中的數(shù)據(jù)用廣義相容算法化簡。

步驟4:使用 Xi=S#Soffi=Son∪SDC∪Soff1∪Soff2∪…∪Soffi－1∪Soffi+1…∪Sofft計算每一個新的 Xi值，并更新 Xi值。

步驟5:判斷是否所有的響應(yīng)數(shù)據(jù)均已處理，如果沒有，則繼續(xù)處理Soffi，否則表明一個數(shù)據(jù)塊中的數(shù)據(jù)已經(jīng)處理完成。

步驟6:輸出最終得到的邏輯綜合結(jié)果。

整個算法執(zhí)行過程中，塊內(nèi)數(shù)據(jù)化簡是節(jié)省時間消耗的關(guān)鍵環(huán)節(jié)，如果不使用化簡處理，則分塊內(nèi)需要進(jìn)行的銳積運(yùn)算最多為t次(t為原始數(shù)據(jù)個數(shù))，如果采用塊內(nèi)數(shù)據(jù)化簡，則實際進(jìn)行的銳積運(yùn)算次數(shù)要遠(yuǎn)小于t次，假設(shè)數(shù)據(jù)化簡的比率為k，則化簡后進(jìn)行的銳積運(yùn)算次數(shù)為t/k次。

圖2 數(shù)據(jù)采集與分塊邏輯綜合同步處理算法

改進(jìn)后的廣義相容算法步驟如下:假設(shè)數(shù)據(jù)塊大小為2p，每個數(shù)據(jù)塊內(nèi)的原始零維體數(shù)據(jù)前k位相同，總的輸入位數(shù)為m，因此在數(shù)據(jù)提升過程中無需對前面相同的k位處理。并定義Soff表示邏輯綜合時的OFF集合，Bi表示每一次對多維體計算時得到的綜合結(jié)果，X表示邏輯綜合向量表，Xi表示向量表中某一個元素值。

步驟 1:令 X=Soff.

步驟2:i從1到k重復(fù)執(zhí)行如下計算過程:

(1)令 B0=?，B1=?.

(2)從多維體輸入組合的某一端開始，掃描X中的每一個多維體。若變量xi=0，則令xi=X，其它組元取值不變，使之加入B0;若變量xi=1，則令xi=X，其它組元取值不變，使之加入B1.

(3)計算X=X∪(B0∩B1).

步驟3:最后得到的X集合即為處理后結(jié)果。

改進(jìn)后的廣義相容算法的時間復(fù)雜度為O(p*t)，其中t為原始立方體個數(shù)，p為分塊大小，也是常量。所以，改進(jìn)后的廣義相容算法其時間復(fù)雜度為O(n)，且由于其基本運(yùn)算都是簡單的相交運(yùn)算，所以處理較大規(guī)模數(shù)據(jù)量時，其性能明顯優(yōu)于改進(jìn)的Q－M算法。

2.3 算法性能測試

本文設(shè)計的算法性能測試主要是對設(shè)計的并行邏輯綜合算法性能測試，測試分為兩部分:單純算法性能的改進(jìn)測試、算法并行處理后總體性能的改進(jìn)。主要測試環(huán)境:測試單機(jī)(酷睿雙核CPU2.4 G，內(nèi)存2 G，硬盤320 G)，安捷倫邏輯分析儀、測試激勵發(fā)生器。不同算法運(yùn)行時間測試結(jié)果如表1所示。表中電路規(guī)模Px－y中，x表示輸入信號的個數(shù)，y表示輸出信號的個數(shù)，測試結(jié)果單位為s。從表中可以看出本文設(shè)計的算法比Q－M算法和改進(jìn)的Q－M算法速度都快，尤其是對大規(guī)模的邏輯電路處理速度的提高更為明顯。

表1 單純算法性能的改進(jìn)測試表

算法并行處理后的總體性能改進(jìn)結(jié)果如表2所示，電路規(guī)模選用的是P24－9，串行重構(gòu)方案中采樣的邏輯綜合算法是改進(jìn)的Q－M算法，由于原來的方案是將采集與邏輯綜合串行進(jìn)行，因此，功能重構(gòu)的時間為兩部分的時間之和。而本文設(shè)計數(shù)據(jù)采集與邏輯綜合并行處理的算法當(dāng)數(shù)據(jù)采集了一部分后，即可同步進(jìn)行邏輯綜合，最終完成功能重構(gòu)的時間(529 s)僅比單純邏輯綜合的時間(436 s)略大。

表2 并行處理后的總體性能改進(jìn)測試表(P24－9)

通過這兩項的測試，證實了本文設(shè)計的算法能夠?qū)崿F(xiàn)未知邏輯電路故障的快速重構(gòu)。

3 總結(jié)

對參考電路采集的激勵響應(yīng)數(shù)據(jù)量隨著電路引腳規(guī)模的增大呈指數(shù)級增加，因此，通過對參考電路的功能分析重構(gòu)，以實現(xiàn)對功能未知的故障電路測試與修復(fù)面臨最大的問題即為處理數(shù)據(jù)量急劇膨脹的問題。當(dāng)故障電路是小規(guī)模電路時，對采集數(shù)據(jù)邏輯綜合的效率要求并不高，然而當(dāng)電路規(guī)模擴(kuò)大時，邏輯綜合效率將成為制約這一技術(shù)應(yīng)用的瓶頸。與此同時，對參考電路數(shù)據(jù)采集本身是一個非常耗時、耗空間的工作，本文設(shè)計的邏輯數(shù)據(jù)采集與綜合分塊同步處理算法很好地解決了這一難題，并且通過在數(shù)據(jù)采集過程中同步綜合數(shù)據(jù)，既可降低銳積運(yùn)算的計算規(guī)模和時間代價，也可降低對采集的原始數(shù)據(jù)和龐大的中間計算結(jié)果保存的空間消耗。

［1］歐偉明.基于FPGA電路重構(gòu)技術(shù)的電子系統(tǒng)設(shè)計［J］.儀表技術(shù)與傳感器，2006，(4):39－41.

［2］賈銀鎖，王卓，李春蔚，等.有窮自動機(jī)的數(shù)字電路故障定位方法［J］.西北民族大學(xué)學(xué)報(自然科學(xué)版)，2004，25(2):47－51.

［3］周治杰，胡昌華.一種數(shù)字電路故障診斷方法的研究及實現(xiàn)［J］.測試技術(shù)學(xué)報，2003，17(1):91－94.

［4］張世德，蘇瑋，薛立軍，等.基于故障字典的數(shù)字電路故障定位過程研究［J］.微計算機(jī)信息，2007，(7):213－215.

［5］欒家輝，姜興渭.一種故障重構(gòu)技術(shù)在導(dǎo)彈系統(tǒng)故障診斷中的應(yīng)用［J］.導(dǎo)彈與航天運(yùn)載技術(shù)，2007，(2):30－34.

［6］于云華，石寅.數(shù)字集成電路故障測試策略和技術(shù)的研究進(jìn)展［J］.電路與系統(tǒng)學(xué)報，2004，9(3):83－91.

［7］俞振華，江建慧.基于故障注入的基準(zhǔn)電路故障響應(yīng)分析［J］.現(xiàn)代電子技術(shù)，2008，31(4):6－8.

［8］周躍夫，姜海勛，袁鋼，等.基于自適應(yīng)神經(jīng)網(wǎng)絡(luò)的高速數(shù)字電路測試的研究［J］.計算機(jī)測量與控制，2009，(6):1 092－1 094.

［9］曹寧，楊巨前.一種數(shù)字組合電路多故障測試生成的高效算法［J］.電子測量技術(shù)，2007，30(6):49－51，95.

［10］王琳，王曉峰，鐘波.基于仿真和編碼理論的數(shù)?；炻?lián)電路故障診斷方法研究［J］.現(xiàn)代電子技術(shù)，2007，30(14):185－188.

［11］王蔚，宋加濤.一種對復(fù)雜數(shù)字電路進(jìn)行智能化故障診斷的新方法［J］.國外電子測量技術(shù)，2004，23(2):23－25，28.

［12］楊俊華，尚志恩，呂鋒.基于布爾差分的數(shù)字邏輯電路故障診斷［J］.電子科技大學(xué)學(xué)報，2005，34(4):517－520.

［13］邊計年，薛宏熙，蘇明，等.數(shù)字系統(tǒng)設(shè)計自動化［M］.北京:清華大學(xué)出版社，2005:1－4，193 －240.

Research into the Fast Restructuring Algorithm for Unknown Logical Breakdown Electric Circuit

LI Ke-chang
(Liuzhou Vocational and Technical College，Liuzhou，Guangxi 545006，China)

To diagnose and repair the unknown logic breakdown electric circuit，one kind of fast restructuring algorithm that used to take place the breakdown electric circuit is studied，based on the analysis of the similar function normal electric circuit.This algorithm gathers the logical function of the reference circuit and simultaneously restructures that of the breakdown electric circuit，which can not only reduce the algorithm running time and storages space，but also avoid carrying on the complex comprehensive algorithm in the process of breakdown circuit logic function restructuring.In addition，it also solves the problem of the gathered data block synthesis paralleling，which may raise the restructured speed of the breakdown electric circuit.The test result indicates that the algorithm designed in this paper can reduce time as much as 70%，compared with the direct Q－M logic synthesis algorithm.

breakdown repairing;electric circuit restructuring;logic synthesis;speed;reference circuit

TN79

A

1672－9021(2011)02－0036－05

李可長(1963－)，男，廣西柳州人，柳州職業(yè)技術(shù)學(xué)院講師，主要研究方向:應(yīng)用電子技術(shù)。

2011－01－10

［責(zé)任編輯 劉景平］