組合電路中邏輯錯誤診斷方法研究

摘要：介紹了近些年出現的幾種錯誤診斷方法，它們在傳統方法的基礎上利用啟發式對原有方法進行了不同程度的改進和提高，產生了較好的診斷結果。

關鍵詞：診斷；路徑追蹤；模擬；可滿足性

中圖分類號：TP306文獻標志碼：A

文章編號：1001－3695(2008)01－0114－03

超大規模數字集成電路的設計周期通常開始于對系統基本行為的刻畫。它采用硬件描述語言(HDL)編寫，又稱為行為級描述。這種描述被轉換為寄存器轉換級(RTL)表示，然后RTL表示被綜合為一個門級實現。為保證產品的性能及其正確性，最后要對系統設計進行優化和驗證。雖然綜合與優化過程中采用了自動化的CAD工具，但電路設計者仍然需要手工修改網表以獲得特定的優化限制，或對規范作出一些修改以提高某些設計方面的要求（如性能），又或者由于規范的變動需要對實現進行修改。隨著電路規模和復雜度的不斷增加，人工的再綜合過程極易引入錯誤。當驗證工具顯示實現不符合規范時，設計者需要對電路中的錯誤進行診斷；然后基于診斷結果對錯誤進行糾正。這對提供一個正確的VLSI產品起著決定性作用。一種快速且有效的錯誤診斷方法不僅能夠縮短產品面市的時間，而且可以降低產品成本，提高產品質量。由于時序電路的復雜性，目前存在的錯誤診斷方法大多是針對組合電路的。近些年出現了一些錯誤診斷方法，它們是在早些年基本方法的基礎上分別采用不同的啟發式對算法進行改進和提高，產生了較好的診斷結果。Boppana等人[1]介紹了一種基于Xlists模擬的診斷算法，并使用符號變量來提高診斷結果。A.Veneris等人[2]引入了通過測試向量模擬的算法，并使用一個可簡化的交叉圖對錯誤空間進行縮小。L. Anand等人[3]使用基于區域模型的診斷算法。其中區域模型可以擴展，以進行多錯誤及簡單時序電路的錯誤診斷。Li Guang hui等人[4]介紹了基于驗證技術的錯誤診斷方法，該方法將三值模擬(0，1，x)與布爾可滿足性技術相結合來快速、有效地消減錯誤空間，提高診斷結果。A.Smith等人[5]介紹了一種基于SAT的解決方法來進行錯誤診斷，利用一個已存在的SAT引擎，該算法對存在多錯誤的電路診斷具有較好的效率和實用性。本文主要針對其中一些具有代表性的算法作較詳細的介紹。

1基本邏輯錯誤診斷方法

符號方法主要采用符號處理技術，如BDD(binary decision diagram)，對實現中的錯誤進行診斷[6，7]。假設電路中存在一個錯誤，符號方法首先在實現中尋找這樣一個內部信號：該信號必須滿足單修正的條件，通過改變這個內部信號的函數從而修改整個實現。將信號f用一個新的布爾函數代替的過程就稱為信號f的再綜合。一個單修正信號的意思是，實現完全可以通過再綜合這一個內部信號f使得整個電路的性能和規范保持一致。符號方法可以得到一個比較準確的結果，但是由于信號函數的表示使用BDD，有可能導致內存爆炸。對于含有多個錯誤的實現，符號方法可以同時對多個信號進行再綜合來糾正整個電路，但是需要對較多的候選對進行檢查。因此具有較高的計算復雜度。譬如對一個含有兩個錯誤的實現，當電路中具有k個信號時需要對k(k-1)/2個候選信號對進行檢查。

模擬是最常用的錯誤診斷方法[8，9]。按照診斷結果的準確性，模擬方法又可以分為錐體交集法、敏感過濾器法、反向傳播(backward propagation，BP)法、可觀察性測量(observability measure，OM)法等。其中錐體交集方法是在假設電路中只有一個錯誤存在的情況下，通過對測試向量的模擬，將實現的主要輸出劃分為正確輸出和錯誤輸出兩部分，則錯誤信號f必定出現在錯誤主要輸出的扇入錐的交集中。該方法不能產生好的診斷結果，需要改進以提高準確度。敏感過濾器方法提出了定位錯誤區域的一種過濾法。其基本思想是：如果一個錯誤向量v不能察覺到內部信號f和錯誤主要輸出Ik之間的不符，則在向量v下的錯誤輸出Ik不能通過改變f來糾正。一個錯誤向量可以解釋為使得實現的輸出響應與規范的輸出響應不匹配的向量。對于一個給定的錯誤向量，反向傳播方法利用一個路徑追蹤程序從錯誤輸出信號反向追蹤到主要輸入來確定一個潛在的可疑區域；然后再使用啟發式將潛在可疑區域逐漸縮小。可觀察性測量方法是在反向傳播方法基礎上對算法準確度的一個改進提高。它是在反向傳播的過程中給傳播路徑中的每個信號賦予一個權值，以表示信號成為錯誤點的可能性。BP和OM方法都主要依賴于一個叫做路徑追蹤的程序。它是基于關鍵路徑追蹤算法在S.Venkataraman等人[10]的錯誤診斷中開發的一種信號線標記算法。以后出現的基于模擬的錯誤診斷方法核心仍然是路徑追蹤程序，在其產生的錯誤候選者的集合上利用各種啟發式不斷刪除非錯誤區域而使錯誤區域逐漸被限定下來。關于路徑追蹤程序將在下文作比較詳細的介紹。

2測試向量模擬法及交叉圖的引入

由A. Veneris和I. N.Hajj設計的通過測試向量模擬進行錯誤診斷與糾錯的方法[2]雖然也是以路徑追蹤程序為核心，但是他們提出的方法適合于含有多個錯誤的電路診斷，并且在診斷過程中通過可簡化交叉圖的使用及有針對的錯誤候選元組的列舉，有效地減少了錯誤候選者的數量。因此避免了隨著錯誤數量的增加而發生的錯誤空間的指數級爆炸問題。

在介紹路徑追蹤程序之前先介紹一下控制值的概念。以v作為輸入向量對電路進行模擬。如果AND或NAND門的扇入信號線l邏輯值為0，則稱l的值為控制值；如果OR或NOR門的扇入信號線l邏輯值為1，則稱l的值為控制值。對于驅動NOT或buffer元件的信號線l來說，不管其邏輯值是1還是0都永遠是控制值。

假設v是一個測試向量，由該向量所產生的一個錯誤主要輸出開始，路徑追蹤程序向主要輸入方向進行反向處理，并且依據一些規則對信號線進行標記。其中標記規則如下：如果已標記一個門G的輸出并且G有一個或多個帶控制值的扇入，則算法隨機標記任意一個控制性扇入；如果門G的所有扇入都有著非控制值，則標記門G的所有扇入；如果已標記了一個支信號線，則算法自動標記該支的干信號線。

單錯誤的診斷方法與基本方法中的錐體交集法相似。它從各個錯誤輸出開始，利用路徑追蹤程序可以獲得可疑信號線的一些集合。而本文要尋找的真正錯誤點必存在于這些集合的交集中。對于多錯誤的診斷，主要分為三個階段：剪除錯誤空間、錯誤元組列舉以及錯誤元組的模擬。在剪除錯誤空間階段中，該測試向量模擬法擯棄了傳統方法中先將電路的所有信號線作為候選者考慮，然后利用模擬將不正確的候選者一一去除的方法，而是引入利用可簡化的交叉圖減少候選者個數的方法。

可以將交叉圖看做一個數據結構，用它來清楚表示path trace程序所提供的不同類型的信息，并且交叉圖在診斷過程中動態地處理。交叉圖的構建處理過程如下：初始IG中無任何頂點；將path trace程序每次在不同的測試向量下運行所得到的一些信號線集合作為頂點加入IG圖中；根據IG簡化規則[2]隨時對每步中所得到的IG進行簡化。這個過程直到path trace程序對Vact中的所有測試向量以及每個向量所對應的所有錯誤主要輸出調用完畢時終止。由證明可知，化簡后的IG中的每個頂點至少包含每個有效錯誤信號線元組中的一個信號線。

對于多錯誤（錯誤數≥2）的診斷過程，大體上可以分為以下幾步：a)通過調用path trace程序構建實現Gc的IG，根據簡化規則隨時對IG進行化簡，直到得到一個不可簡化的IG。b)根據猜測的錯誤數N以及一個用戶指定的n樣本的值調用錯誤列舉程序，返回一個錯誤元組的集合Cerror。c)對Cerror中的每個錯誤元組依次調用錯誤模擬程序。如果Cerror在錯誤模擬過程中變為空并且已經達到反復執行的最大數，則對錯誤數N加1后重新執行多錯誤的診斷過程。

測試向量模擬法提出利用交叉圖簡化縮小錯誤空間，消除了錯誤空間的指數級爆炸問題。但是該方法從理論層次上來說并不能保證返回所有有效的修改元組。這是因為有時返回的錯誤元組的集合依賴于一個隨機樣本n的選擇[2]。

3基于區域模型的錯誤診斷

文獻[3]采用基于區域模型的方法進行錯誤診斷。它所使用的主要技術是三值模擬和非列舉分析。三值模擬采用三值邏輯（即0、1、X）模擬電路的行為特征。其基本方法是在規范和實現的門器件輸入端加入相同的三值信號。如果規范的輸出為X，而實現的輸出為1或0，則表示該門器件存在錯誤。非列舉分析技術不需要詳細列舉每一個可疑信號，而是通過確定錯誤區域來同時確定多個錯誤的位置。實驗結果表明，基于區域模型的方法對門連接以及門置換類型的錯誤診斷非常有效，對其他類型的錯誤也可以產生較好的結果。

在介紹基于區域模型的錯誤診斷方法之前有必要介紹一下區域的概念。

定義2結構距離。電路中的任一門元件g與它的直接扇入門或直接扇出門之間的距離稱為一個結構距離。

定義3區域。給定d為一個固定化的結構距離，g為電路的任一門元件，則以g為中心、d為半徑的區域是集合D(g)={h|dis(g，h)≤d}。

例如門g周圍半徑為1的區域集合中包括g、g的直接扇出以及直接扇入。電路中的每個門都可以形成一個區域，因此電路中有多少個門就有多少個重疊區域。在模擬過程中，區域的所有輸出節點首先被設置為未知值X，以掩蓋發生在該區域中的任何錯誤。如果對于一個給定向量v，沒有X傳播到一個主要輸出，則可以判定向量v探測不出區域中的任何錯誤；否則說明區域中存在錯誤并將該區域作為一個錯誤候選者。如圖2、3所示。

定義4錯誤輸出。在錯誤向量的模擬下，實現中出現與規范不一致的輸出稱為不一致輸出或錯誤輸出。

基于區域模型的診斷算法如下：首先從錯誤的門級實現中抽取指定半徑的區域，將所有抽取得到的區域標記為候選者，并放入候選列表中；然后將候選列表中每個區域的所有輸出節點設為X，模擬程序；如果一個區域的輸出X不能傳播到所有錯誤輸出，則將該區域從候選列表中移出，否則對該區域的所有錯誤輸出依據部分匹配進行分值計算；在每一個錯誤向量的模擬下，對候選列表中剩余的候選者依次進行分值計算；最后，候選列表中每個區域都對應一個等級。一個候選區域的分值越高說明它完全包含錯誤的可能性越大。

使用基于區域模型的錯誤診斷方法時，如何選擇一個合適的結構距離半徑d非常重要。因為d過大會導致區域包含過多的元素，使得很多區域都包含錯誤，導致候選列表過大；區域過小，錯誤不能完全包含在一個區域內，而是分散在多個區域內，即多于一個的區域含有部分錯誤，從而得到一個有著部分錯誤命中率的候選列表。

4基于驗證技術的錯誤診斷

基于驗證技術的方法[4]是在基于區域模型診斷方法上的一個改進提高。它結合了三值(0，1，X)邏輯并行模擬[1]和布爾可滿足性方法[11]，提高了錯誤診斷的準確度。算法假設真正的錯誤區域被完全地包含在至少一個有著給定半徑的候選區域中，并依據下面的定理展開。

解決米勒機網絡的CNF公式問題實質上等價于比較規范和實現的特征函數。在基于驗證技術的錯誤診斷方法中，將候選區域看做實現的一個黑盒，并且將黑盒的輸出作為實現額外的主要輸入，然后直接創建米勒機網絡的CNF公式S。正如定理所表示的，如果要找出黑盒區域外的錯誤，必須為公式S找到一個獨立于黑盒中實現部分的可滿足性賦值。為此將黑盒區域的輸出節點設置為X，這樣從CNF公式中全局地量化出所有表示額外主要輸入的新變量。如果最后的CNF公式是可滿足的，則在候選區域之外的區域發現一個錯誤。根據之前的假設，這個候選區域應從候選列表中去除。

注意如果SAT處理器的驗證結果是可滿足的，則候選區域之外的區域存在錯誤，該候選區域從列表中刪除；如果結果顯示是不可滿足的，則該結果并不能保證候選區域的周圍區域中沒有錯誤。因為使用X作為候選區域的輸出值有可能掩蓋一些錯誤。另外直接量化表示額外主要輸出的變量有可能引起最后CNF公式的沖突，特別對較大區域更是如此。盡管基于SAT的布爾比較算法引入X值的原因對探測錯誤具有限制，但是卻可以用來提高三值并行模擬診斷算法的結果。兩者結合最終可以產生較好的診斷結果，具體算法可以參看文獻[4]。

5結束語

本文討論了近些年在錯誤診斷領域出現的一些新方法和新技術，并對它們的特點作了總結。雖然邏輯錯誤的診斷方法經過幾十年的發展已經獲得了長足的進步，但是仍然存在很多不足之處：a）現存的錯誤診斷算法并不能診斷所有的錯誤類型。它們大多是針對Abadir等人提出的錯誤模型中的十種錯誤類型進行診斷。雖然該模型中所包含的錯誤類型已經可以涵蓋人工再綜合過程中出現的錯誤的97%，但是仍然不能排除3% 其他類型錯誤的存在。b）多錯誤的診斷仍然不太完善。目前的算法對電路中存在一個、兩個或者三個錯誤情況下的診斷效果還是比較好的，但對多于三個錯誤的情況，在算法的運行時間性能以及錯誤診斷結果方面并不十分令人滿意。目前有些算法將多錯誤診斷情況轉換為多個單錯誤的診斷情況，理想化地忽略掉各個錯誤之間有可能存在的聯系。因此實際上取得的效果也是有限的。c）設計規模越來越大，周期越來越長。設計人員希望驗證與診斷糾錯都可以實現自動化，以縮短產品的上市時間，降低成本。但目前的情況是驗證器檢驗出實現與規范不相符后，依然大部分靠熟悉設計的人員進行手工糾錯，或僅實現這方面的部分自動化。d）本文僅對組合電路的錯誤診斷問題作了討論，對時序電路的邏輯錯誤診斷研究仍然是個比較復雜的課題。諸如以上的各個問題，還有待研究人員進一步的探索。

參考文獻：

［1］

BOPPANA V，MUKHERJEE R，JAIN J，et al.Multiple error diagnosis based on Xlists[C]//Proc of the 36th ACM/IEEE Design automation Conf.New York:ACM Press， 1999：660－665.

[2]VENERIS A，HAJJI N.Design error diagnosis and correction via test vector simulation[J].IEEE Trans on Computer Aided Design，1999，18(12): 1803 1816.

[3]ANAND L，SOUZA D’，HSIAO M S.Error diagnosis of sequential circuits using region based model[C]//Proc of IEEE VLSI Design Conf.2001:103 108.

[4]LI Guang hui，SHAO Ming，LI Xiao wei.Design error diagnosis based on verification techniques[C]//Proc of the 12th Asian Test Symposium.Xi’an:[s.n.]，2003:474 477.

[5]SMITH A，VENERIS A，VIGLAS A.Design diagnosis using boolean satisfiability[C]//Proc of Asia South Pacific Design Automation Conf.2004:218－223.

[6]CHUNG P Y，WANG Y M，HAJJ I N.Logic design error diagnosis and correction[J].IEEE Trans on VLSI System，1994，2(3):320－332.

[7]VENERIS A G，HAJJ I N.A fast algorithm for locating and correcting simple design errors in VLSI digital circuits[C]//Proc of Great Lake Symposium on VLSI Design.1997:45－50.

[8]POMERANZ I，REDDY S M.On diagnosis and correction of design errors[J].IEEE Trans on Computer Aided Design，1995，14(2): 255－264.

[9]WAHBA A M，BORRIONE D.A method for automatic design error location and correction in combinational logic circuits[J].Journal of Electronic Testing: Theory and Applications，1996，18(2):113 127.

[10]VENKATARAMAN S，FUCHS W K.A deductive technique for diagnosis of bridging faults[C]//Proc of IEEE/ACM Int Conf Computer Aided Design.New York:ACM Press，1997:562－567.

[11]JAIN A，BOPPANA V，MUKHERJEE R，et al.Verification， and diagnosis in the presence of unknowns[C]//Proc of the 18th VLSI Test Symposium.2000:263－269.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”