李可長

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

未知邏輯的故障電路快速重構算法研究

李可長

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

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

故障修復;電路重構;邏輯綜合;速度;參考電路

0 前言

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

1 未知邏輯電路故障功能重構方案

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

圖1 未知邏輯電路故障功能重構方案過程圖

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

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

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

2.1 算法原理

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

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

假設對參考電路共有n個信號引腳，對該電路采集的所有不重復的激勵和響應之間的向量數(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ù)進行邏輯綜合時，令Son表示on點集合，Soff表示off點集合，SDC表示DC項集合，有S=Son∪Soff∪SDC.

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

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

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

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

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

2.2 算法步驟

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

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

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

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

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

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

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

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

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

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

步驟 1:令 X=Soff.

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

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

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

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

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

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

2.3 算法性能測試

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

表1 單純算法性能的改進測試表

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

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

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

3 總結

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

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

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

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

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

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

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

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

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

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

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

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

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

［13］邊計年，薛宏熙，蘇明，等.數(shù)字系統(tǒng)設計自動化［M］.北京:清華大學出版社，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è)技術學院講師，主要研究方向:應用電子技術。

2011－01－10

［責任編輯 劉景平］