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

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

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