吳益鋒,朱恒亮,曾　璇

(復旦大學 專用集成電路與系統(tǒng)國家重點實驗室,上海 201203)

?

魯棒主元分析和稀疏表示方法在模擬電路錯誤檢測中的應用

吳益鋒,朱恒亮,曾璇

(復旦大學 專用集成電路與系統(tǒng)國家重點實驗室,上海 201203)

模擬電路錯誤檢測問題,即重點是檢測出模擬電路芯片存在錯誤后確定錯誤元件或參數(shù)的問題,對于進一步明確錯誤產(chǎn)生原因,在設計或制造中加以改進,有重要的意義.經(jīng)典做法是通過預先設置錯誤,并仿真得到其對應的響應數(shù)據(jù),構造“錯誤字典”,然后將測試信號與錯誤字典進行比對,識別其屬于哪一類錯誤類型.本文提出一種基于數(shù)據(jù)稀疏表示方法來進行錯誤類型識別的新方法,它計算屬于不同錯誤類型的數(shù)據(jù)在所有類型的數(shù)據(jù)構成的空間中的展開向量,根據(jù)得到的稀疏向量來判斷其所屬錯誤類型.對于稀疏表示方法無法進行準確分類識別的情況,采用SVM作為二級分類器進行修正.存在某些錯誤類型,其響應數(shù)據(jù)構成的空間之間線性相關性較強,對于稀疏表示后屬于其中之一類型的數(shù)據(jù),采用傳統(tǒng)的SVM方法來加以輔助分類.在兩個實驗例子中,與SVM,Ada Boost以及沒有加SVM輔助分類的單純稀疏表示方法相比較,本文方法有更高的錯誤類型識別正確率.

錯誤檢測； 支持向量機； 魯棒主元分析； 稀疏表示

模擬電路和混合信號電路中的錯誤檢測以及錯誤定位問題,是電路設計驗證和電路原型特征描述的重要課題[1-4].模擬電路錯誤檢測,也即錯誤元器件位置的確定[5],一直是一個比較困難的問題.一部分原因是模擬電路錯誤檢測缺乏良好的錯誤定義模型以及在不斷開電路連接的情況下測量節(jié)點電流的困難性；另外,電路具有非線性特性等因素也造成了一定的困難性.

模擬電路的錯誤一般指任何電路元件對于其名義取值的偏離,從而可能破壞電路性能的情況.這些錯誤可能是“硬錯誤”,即電路發(fā)生短路或開路；也可能是“軟錯誤”,即電路元件參數(shù)值偏離了設計的名義值,但還沒有超出可接受的極限.這些軟錯誤可能來源于制造過程的工藝偏差、器件的老化或者一些寄生效應.很多錯誤檢測技術著眼于某一元件發(fā)生錯誤的情況的“單錯誤”問題,但從現(xiàn)在設計的復雜性以及電路檢測技術的實用性考慮,“多錯誤”模型是我們的研究重點和方向.在本文后面的理論以及測試電路例子中,我們都會考慮電路中的多個參數(shù)同時發(fā)生錯誤的情況,一方面這相比“單錯誤”問題更加接近應用問題的實際情況[6],另一方面,“多錯誤”情況增加了問題的復雜度,從而可以更好地說明本文所提出的方法在處理復雜問題時的優(yōu)勢.

1　相關工作

過去對模擬電路錯誤檢測的方法研究基本上可以分為兩類: 測試前仿真(Simulation Before Test, SBT)方法和測試后仿真(Simulation After Test, SAT)方法.SAT方法是先得到待測試電路的響應,然后計算電路參數(shù),從而完成錯誤檢測.SBT方法的要點是將電路的響應與“錯誤字典”(fault dictionaries)中各個錯誤分類的對應電路響應進行比較,判斷其是否屬于某一特定錯誤分類.由于SBT方法是基于已經(jīng)生成好的電路錯誤字典,所以比SAT方法時間開銷更小,故本文所述也是基于SBT方法.

在過去的一段時間里,模擬電路錯誤檢測方面的研究無論是在系統(tǒng)級、電路板級還是芯片級,都取得了很多進展[7-10].在SBT方法的整個錯誤檢測流程中,最關鍵的地方是錯誤分類的學習過程,也即錯誤字典的構造過程.

文獻[3-4]提出使用神經(jīng)網(wǎng)絡來作為分類學習器,直接將對電路測試得到的響應數(shù)據(jù)輸入到學習網(wǎng)絡中,在這種不加任何數(shù)據(jù)前處理的情況下,即便是小規(guī)模的電路也會需要比較復雜的學習網(wǎng)絡[3],模型的學習時間過長.文獻[11-12]提出用小波變換對一開始得到的電路響應數(shù)據(jù)進行前處理后,再作為神經(jīng)網(wǎng)絡的輸入,不過雖然小波變換通常來說是不錯的數(shù)據(jù)處理工具,在實際的電路檢測實時應用場景下,小波變換的基、階數(shù)以及變換后小波系數(shù)的選擇都具有主觀任意性,不能很好地把握.

文獻[10,13-14]等提出用支持向量機(Support Vector Machine, SVM)來對錯誤進行分類學習,主要使用了經(jīng)典的SVM方法以及一些改進算法,如LS-SVM等.SVM的基本思想是: 通過某種非線性映射,將輸入數(shù)據(jù)向量映射到一個高維的空間Z,在這個高維的空間Z中,構造最優(yōu)分離超平面,使得在原空間不可分的數(shù)據(jù)在變換后的空間中變得容易分類.通過修改不同的核函數(shù)(變換后空間的內積函數(shù)),可以得到不同的分離曲面.在數(shù)據(jù)量很大的時候,SVM的學習是比較耗時的,對此,文獻[15]提出了一些近似算法.近似算法可以減少計算時間,但是會使屬于各錯誤類型的樣例個數(shù)變差.文獻[16-18]進一步闡述了這個問題,提出了bagging, boosting以及Ada Boost等方法.但是,仍然存在boosting這一類方法自身難以很好地在分類精度和分類多樣性之間進行平衡的問題[19].

本文中我們采用魯棒主元分析(Robust Principal Component Analysis, RPCA)與稀疏表示方法(Sparse Representation, SR)相結合來作為分類器.屬于不同錯誤分類的數(shù)據(jù)具有不同的主元特征,通過魯棒主元分析并計算其稀疏表示后,得到的測試數(shù)據(jù)在包含各個分類的總的空間上的展開.若一個測試數(shù)據(jù)只屬于某一分類,則得到的表示向量是稀疏的,與其所屬分類相對應的位置上的元素占主要部分.稀疏表示方法的主要問題是對于線性相關度大的數(shù)據(jù)無法準確分類,因此采取SVM方法進一步分類以提高分類精度.實驗結果表明,特別是在有若干錯誤類型線性相關度很大的情況下,這種稀疏表示再加上SVM的方法,相比SVM、Ada Boost等傳統(tǒng)方法,具有更好的分類正確率.

2　基于RPCA和稀疏表示的錯誤檢測方法

本文基于RPCA和數(shù)據(jù)稀疏表示方法來構造基本的分類器,假設訓練數(shù)據(jù)為D,測試數(shù)據(jù)為T,首先運用RPCA提取訓練數(shù)據(jù)的主元特征,若Ui是D中第i類錯誤類型數(shù)據(jù)的特征基矩陣,則有

(1)

(2)

那么如果將一個測試數(shù)據(jù)在包含所有分類的訓練數(shù)據(jù)形成的主元空間上展開:

(3)

2.1魯棒主元分析方法

RPCA方法可以有效地將原始數(shù)據(jù)的主元提取出來[20-21],假設有:

D=V+E,

(4)

D是數(shù)據(jù)矩陣,V是一個低秩的待恢復矩陣(即為RPCA后得到的矩陣),E是一個稀疏的噪聲矩陣,傳統(tǒng)的PCA方法根據(jù)E的2-范數(shù)最小的原則來計算V,但是這時即便E中只有一小部分的元被噪聲污染或者是異常值,V就很有可能無法有效恢復.應用表明,RPCA采用0-norm具有更大優(yōu)勢,即:

min(rank(V)+‖E‖0),

(5)

‖?‖0代表求解一個向量的0-范數(shù).但是這并不是一個容易求解的凸優(yōu)化問題,文獻[20]證明了在絕大多數(shù)情況下,將V的秩換為核范數(shù)(矩陣奇異值之和),將E的0-范數(shù)換為1-范數(shù),在大概率下求出的解可以命中真實解,即最小化目標變?yōu)?

min(nuclearnorm(V)+‖E‖1).

(6)

這時我們就得到一個可以在多項式時間復雜度內求解的凸優(yōu)化問題:

(7)

其中β是一個參數(shù),‖?‖*表示核范數(shù).對V進行奇異值分解(SingularValueDecomposition,SVD)后,可以分解為V=UΣV′,U和V′分別包含了V的行列主元,Σ是一個對角陣,對角線上是V的奇異值從大到小的排列.我們設定一個閾值,只選取那些能量占比比較大的奇異值.這樣,就可以由訓練數(shù)據(jù)D得到一個包含不同錯誤類型的特征基矩陣U.

2.2數(shù)據(jù)的稀疏表示分類

U=[U1,U2,…,Up],p為錯誤分類類型總數(shù)目,

(8)

(9)

(10)

(11)[22]

(12)

該問題可以在多項式時間復雜度求解.

(13)

(14)

2.3SVM二級分類

2.4步驟歸納

基于稀疏表示方法+SVM的模擬電路錯誤檢測流程主要包括4個步驟: (1) 對電路進行仿真,提取響應數(shù)據(jù)D和T；(2) 用稀疏表示方法對D訓練分類器M1,并得到“線性相關類型組”；(3) 用D中屬于“線性相關類型組”的那些數(shù)據(jù)來訓練SVM分類器M2；用M1對測試數(shù)據(jù)T分類,得其分類后所屬類型；(4) 用稀疏表示方法對T分類,如果某測試數(shù)據(jù)的稀疏表示結果顯示其屬于某一“線性相關類型組”,則再用SVM方法進行分類.

3　實驗和結果分析

本文用兩個例子來對所提錯誤檢測方法進行有效性的驗證: 一個二級運放(two-stage opam)和一個電平轉換電路(level shifter).兩個電路所采用工藝分別為TSMC 180nm和SMIC 40nm, 電路仿真軟件為HSPICE.

3.1電路例子以及錯誤類型設置

圖1是二級運放,我們這里主要關注MOS管因制造工藝偏差造成的長寬誤差.對現(xiàn)在的模擬電路單元來說[23],晶體管的寬比長大得多,所以電路的性能對于管長更加敏感.假設lmid,ldn,lup是3個參數(shù),電路設計過程中,各個管子的溝道長滿足L(M4)=L(M5)=lmid,L(M1)=L(M7)=ldn,L(M0)=L(M2)=L(M3)=lup.當這三個參數(shù)實際取值偏離設計值20%,就視為發(fā)生錯誤；同時考慮到工藝偏差,錯誤參數(shù)之外的其他參數(shù)在其各自設計值的5%以內隨機偏離.所提取的二級運放的響應數(shù)據(jù)向量包含增益、單位增益帶寬、相位裕度、跨導等,這些指標也是這個電路的性能優(yōu)化目標.其錯誤類型設置如表1所示.

注: ↑和↓分別表示實際值比名義值偏大或偏小.

具體來說,例子中的運放設計規(guī)范(spec)是: Gain>80,Ugf > 1×107,Pm>-110,在設計的各個錯誤類型下,電路仿真得到的主要參數(shù)結果(每一錯誤類型的結果取的是50次仿真結果的平均值)如下表2所示,仿真結果中帶有灰度的數(shù)據(jù)表示不符合spec的結果,視為存在錯誤.相應地,圖2是電平轉換電路的電路圖,表3中是其錯誤類型設置情況,這里我們主要關注的是模擬電路中某處導線電阻異常增大甚至發(fā)生開路的錯誤情況.R1,R2和R3是虛擬設置的導線電阻,開路時的電阻值設定為100MΩ,當非出錯時,其阻值在數(shù)歐到數(shù)十歐之間隨機分布.錯誤分類提取的響應數(shù)據(jù)向量包含電路輸入點、輸出點的電壓最值,以及電源點和接地點的電流最值等(都是在一個周期內).

表2　運放具體錯誤類型下電路主要參數(shù)

3.2結果分析

對于每一錯誤分類,仿真生成100個響應數(shù)據(jù)向量D和T各50個.4種不同方法在T上的屬于各錯誤類型的樣例個數(shù)如表4所示.

表4　4種方法屬于各錯誤類型的樣例個數(shù)比較

實驗結果顯示,我們提出的基于稀疏表示并使用SVM進行二次分類的方法在分類正確率上優(yōu)于單使用稀疏表示、SVM或Ada Boost方法,在某些分類線性相關性強時,基于稀疏表示+SVM的方法具有更好的有效性和魯棒性.

對于空間線性相關性較大的錯誤分類之間,采用SVM方法來二次分類.表5和表6分別是二級運放電路數(shù)據(jù)D在稀疏表示方法下、T在稀疏表示方法下、T在稀疏表示+SVM下的屬于各錯誤類型的樣例個數(shù).格中數(shù)字表示原屬于縱向分類類型的數(shù)據(jù)被最終分類為橫向分類類型的數(shù)目,例如表5中第5列數(shù)據(jù)表示,屬于第4類錯誤類型的50個測試數(shù)據(jù),有35個分類正確,而15個被錯誤地分類為第6類錯誤.因為稀疏表示分類方法基于向量在空間中的線性展開,主要假設是: 相同錯誤類型的特征空間線性相關,而不同錯誤類型的特征空間線性相關性很小,從而屬于某一分類的數(shù)據(jù)在總的空間上的線性展開系數(shù)向量是稀疏的；那么對于D在稀疏表示方法下分類具體結果中分類錯誤的情況,可以看作是分類類型之間線性相關性大所造成的.

表5中屬于各錯誤類型的樣例個數(shù)顯示: 第4和第6類類型線性相關度大,第5和第7類類型線性相關度大(分別構成“線性相關類型組”),這也得到表5中各錯誤類型的樣例個數(shù)的驗證.表6中則為T在稀疏表示+SVM方法下各錯誤類型的樣例個數(shù),與表5結果相對比可以發(fā)現(xiàn),對于屬于線性相關度大的分類類型的數(shù)據(jù),SVM二次分類可以進行很好地區(qū)分,大大提高了分類正確率.

類似地,表7,表8的數(shù)據(jù)顯示了電平轉換電路在稀疏表示+SVM方法下有效提高分類正確率的結果,表8是對表7得出的“線性相關類型組”的交叉驗證,而表8的各錯誤類型的樣例個數(shù)再次說明了對線性相關度大的分類進行SVM二次分類可以提高分類正確率.表5和表7,或表5和表8的數(shù)據(jù)對比也說明了表4中4種方法總體判別正確率在兩個例子上的差異的原因: 電平轉換電路的不同分類中數(shù)據(jù)空間線性相關程度更大,從而在電平轉換電路中,稀疏表示+SVM方法的正確率比單純的稀疏表示分類方法高出12.5%,運放例子中則為6.7%.

表5　運放電路訓練數(shù)據(jù)D和運放電路測試數(shù)據(jù)T在稀疏表示方法下各錯誤類型的樣例個數(shù)

表6　運放測試數(shù)據(jù)T在稀疏表示+SVM下各錯誤類型的樣例個數(shù)

表7　電平轉換電路訓練數(shù)據(jù)D在稀疏表示方法下各錯誤類型的樣例個數(shù)

表8　電平轉換電路測試數(shù)據(jù)T在稀疏表示方法、稀疏表示+SVM下各錯誤類型的樣例個數(shù)

4　結　論

本文將魯棒主元分析、數(shù)據(jù)稀疏表示方法應用于模擬電路錯誤檢測問題,并與傳統(tǒng)SVM方法相結合來提高分類判別的正確率.這種方法相比SVM、Ada Boost以及沒有SVM輔助分類的RPCA方法,分類正確率更高,克服了其他幾種方法面臨的復雜性過大、分類效果不夠好、性能表現(xiàn)不穩(wěn)定等弊端.特別是當某些錯誤類型的數(shù)據(jù)空間線性相關性比較大時,本文方法可以更大地提高分類正確率,更好地顯示出其魯棒性.

[1]MAHDAVI S J S, MOHAMMADI K. Evolutionary derivation of optimal test sets for neural network based analog and mixed signal circuits fault diagnosis approach [J].MicroelectronicsReliability, 2009,49(2): 199-208.

[2]VOORAKARANAM R, AKBAY S S, BHATTACHARYA S,etal. Signature testing of analog and RF circuits: Algorithms and methodology [J].IEEETransactionsonCircuitsandSystemsI:RegularPapers, 2007,54(5): 1018-1031.

[3]AMINIAN M, AMINIAN F. A modular fault-diagnostic system for analog electronic circuits using neural networks with wavelet transform as a preprocessor [J].IEEETransactionsonInstrumentationandMeasurement, 2007,56(5): 1546-1554.

[4]YUAN L, HE Y, HUANG J,etal. A new neural-network-based fault diagnosis approach for analog circuits by using kurtosis and entropy as a preprocessor [J].IEEETransactionsonInstrumentationandMeasurement, 2010,59(3): 586-595.

[5]DEJKA W J. A review of measures of testability for analog systems[C]∥Imaginative Engineering thru Education and Experience: Proceedings of Southeastcon’77 Region 3 Conference. New York: Institute of Electrical and Electronics Engineers, 1977,1: 279-284.

[6]BANDLER J W, SALAMA A E. Fault diagnosis of analog circuits [J].ProceedingsoftheIEEE, 1985,73(8): 1279-1325.

[7]JANTOS P, GRZECHCA D, GOLONEK T,etal. Heuristic methods to test frequencies optimization for analogue circuit diagnosis [J].TechnicalSciences, 2008,56(1): 29-38.

[8]SUN Y C. Test and diagnosis of analogue, mixed-signal and RF integrated circuits: The system on chip approach [M]. London, UK: The Institution of Engineering and Technology, 2008.

[9]GISLASON P O, BENEDIKTSSON J A, SVEINSSON J R. Random forests for land cover classification [J].PatternRecognitionLetters, 2006,27(4): 294-300.

[10]CUI J, WANG Y. A novel approach of analog circuit fault diagnosis using support vector machines classifier [J].Measurement, 2011,44(1): 281-289.

[11]HE Y, TAN Y, SUN Y. Wavelet neural network approach for fault diagnosis of analogue circuits [J].IEEEProceedings-Circuits,DevicesandSystems, 2004,151(4): 379-384.

[12]AMINIAN F, AMINIAN M, COLLINS Jr H W. Analog fault diagnosis of actual circuits using neural networks [J].IEEETransactionsonInstrumentationandMeasurement, 2002,51(3): 544-550.

[13]TANG J Y, SHI Y B, ZHANG W. Analog circuit fault diagnosis based on support vector machine ensemble [J].ChineseJournalofScientificInstrument, 2008,6: 19.

[14]LONG B, TIAN S, MIAO Q,etal. Research on features for diagnostics of filtered analog circuits based on LS-SVM[C]∥AUTOTESTCON, 2011 IEEE.Baltimore, Maryland, USA: IEEE Press, 2011: 360-366.

[15]BURGES C J C. A tutorial on support vector machines for pattern recognition [J].DataMiningandKnowledgeDiscovery, 1998,2(2): 121-167.

[16]KIM H C, PANG S, JE H M,etal. Constructing support vector machine ensemble [J].PatternRecognition, 2003,36(12): 2757-2767.

[17]VALENTINI G, DIETTERICH T G. Bias-variance analysis of support vector machines for the development of SVM-based ensemble methods [J].TheJournalofMachineLearningResearch, 2004,5: 725-775.

[18]TANG J Y, SHI Y B, ZHOU L F,etal. Analog circuit fault diagnosis using Ada boost and SVM[C]∥International Conference on Communications, Circuits and Systems, 2008.Xiamen, China: IEEE Press, 2008: 1184-1187.

[19]WOLD S, ESBENSEN K, GELADI P. Principal component analysis [J].ChemometricsandIntelligentLaboratorySystems, 1987,2(1): 37-52.

[20]WRIGHT J, GANESH A, RAO S,etal. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization[C]∥Advances in Neural Information Processing Systems.MA, USA: MIT Press, 2009: 2080-2088.

[21]WRIGHT J, YANG A Y, GANESH A,etal. Robust face recognition via sparse representation [J].IEEETransactionsonPatternAnalysisandMachineIntelligence, 2009,31(2): 210-227.

[22]DONOHO D L. For most large underdetermined systems of linear equations theminimal L1-norm solution is also the sparsest solution [J].CommunicationsonPureandAppliedMathematics, 2006,59(6): 797-829.

[23]BOOLCHANDANI D, GARG L, KHANDELWAL S,etal. Variability aware yield optimal sizing of analog circuits using SVM-genetic approach[C]∥SM2ACD, 2010. Gammarth, Tunisia: Springer, 2010: 1-6.

Analog Circuit Fault Diagnosis Based on Robust Principal Component Analysis and Sparse Signal Representation

WU Yifeng, ZHU Hengliang, ZENG Xuan

(State Key Laboratory of ASIC & Systems, Fudan University, Shanghai 201203, China)

Aiming at better solving the problem of fault diagnosis of analog circuits, a new method is proposed here, which is a combination of some different concepts and algorithms. It consists of robust principal component analysis, SVD, sparse representation and SVM. This method for fault analysis is especially useful and powerful when we cannot select out the most suitable features of circuit for diagnosis due to the lack of knowledge about the circuit itself, or just no enough training samples are got. In the test of the examples in our work, the new method has achieved better accuracy rate over SVM and Ada Boost framework based method.

fault diagnosis; support vector machine; robust principal component analysis; sparse signal representation

0427-7104(2016)01-0051-08

2015-02-12

國家自然科學基金(91330201)

吳益鋒(1989—),男,碩士研究生；朱恒亮,男,講師,通訊聯(lián)系人,E-mail: hlzhu@fudan.edu.cn.

TN 47

A