基于BDD和布爾差分的組合電路測試生成方法

在數(shù)字系統(tǒng)的測試中, ATPG 是對測試電路產(chǎn)生測試向量的過程[ 1] 。通常ATPG 算法首先給電路插入一個故障; 然后通過在電路輸入端激活這個故障, 并將其產(chǎn)生的響應通過電路傳播到輸出端。若輸出信號與無故障電路的期望值不同, 就可以檢測到這個故障了。針對組合電路中固定型故障, 目前存在一些ATPG 算法。最基本的是布爾差分法[ 2, 3] 。它描述嚴格, 是研究組合電路測試生成的理論基礎。最經(jīng)典的是Roth 的D 算法[ 4] , 采用D 立方建立了ATPG 的運算。此外還有Geol 的PODEM算法、Fujiwara 的FAN算法[ 6] 等, 在回溯和加快搜索速度上作出了很大的貢獻。Geol 在其PODEM算法[ 5] 中采用二元決策樹( binary decision tree, BDT) 進行搜索。Akers[ 7] 提出的使用BDD 來表述邏輯電路則更為實際。近年來, BDD 的理論有了更進一步的完善和發(fā)展[ 8, 9] , 并更多地運用到數(shù)字電路設計中的驗證、綜合[ 10] 及自動測試模式生成[ 11] 。本文嘗試采用簡潔的簡化排序二元決策圖( reduced orderedBDD, ROBDD) 來對組合電路進行表示及運算; 同時融入布爾差分的思想, 對被測電路BDD 結構進行判斷, 從而進行測試生成。

BDD 的相關知識
1. 1 使用BDD 表示布爾函數(shù)
根據(jù)香農(nóng)展開式[ 7] , 對于任意一個布爾函數(shù)F = f( a, b,c) , 可以將其轉換為f( a, b, c) = af( 1, b, c) ∨af( 0, b, c) 。例如對于布爾函數(shù)f = ( x1 ∧x2 ) ?? x3 , 可以表示為f = x1 [ ( 1∧x2 ) ?? x3 ] ∨x1 [ ( 0∧x2 ) ?? x3 ] ( 1 )對式( 1) , 將x1 分別設置為0 值和1 值時, 在運算中就會產(chǎn)生兩種不同的情況, 以圖的形式表述如圖1( a) ( 圖中的虛線邊表示節(jié)點變量取0 值, 為節(jié)點的左后繼; 同理實線邊表示取1 值, 為右后繼) 所示。接下來繼續(xù)對此函數(shù)中的另外兩個變量x2 和x3 也進行同樣的展開操作, 直至全部變量都被展開。至此, 布爾函數(shù)f = ( x1∧x2 ) ?? x3 中可能的變量取值及運算結果全部由圖1( b) 表示。