本期給大家介紹一下DFT中涉及到的一些MBIST算法，主要分為Classical Algorithms和March Algorithms。

Classical Algorithms

經(jīng)典算法形式比較簡單，操作以簡單的讀寫為主。

1.1 MSCAN

MSCAN算法的操作邏輯為：

????1) Write 0 to every cell
????2) Read 0 from every cell
????3) Write 1 to every cell
????4) Read 1 from every cell

可以看到，MSCAN的思路就是對每個單元依次讀寫0和讀寫1，以此來檢測單元內(nèi)是否有故障，因此它也被稱為“0-1算法”。在MSCAN的操作過程中，每個cell都有被置0和被置1的過程，因此該算法可以檢測到所有的SAF（Stuck-At Fault，指某個單元的值被固定，SA0固定為0，SA1固定為1）。同時，因為它只有從0變化到1的過程而沒有從1變化到0的過程，所以它只能檢測到<↑/0>TF(上轉(zhuǎn)換故障，指某個單元無法從0變化為1)。

根據(jù)該算法的操作邏輯可以知道，每個cell均經(jīng)歷了4步操作（R/W），故該算法的時間復雜度為4N。

Tips：時間復雜度表征的是執(zhí)行一個算法所需要花費的時間的趨勢，通常情況下只保留最高次項，忽略常數(shù)項。一般來說，時間復雜度越高，運行算法的時間就越長。

1.2 Checkerboard

??? Checkerboard算法的操作邏輯為：

????1) Write ckbd pattern to all cells
????2) Read ckbd pattern from all cells
????3) Write ckbd’ pattern to all cells
????4) Read ckbd’ pattern from all cells

? ? ? Tip:ckbd -> checkerboard

????假設(shè)黑色為邏輯1，白色為邏輯0，ckbd’即為ckbd取反。

??? Checkerboard算法對所有cell寫的pattern可以抽象為一個棋盤，故被稱為“棋盤算法”。該算法同樣可以檢測到所有的SAF。因為該算法的pattern是“1-0-1”間隔排列，所以只能檢測到一半的TF，具體哪個cell能檢測出何種TF取決于該cell執(zhí)行的操作是“1->0”還是“0->1”。

????該算法對每個cell同樣執(zhí)行了4步操作，故該算法的時間復雜度為4N。

1.3 GALPAT

??? GALPAT算法的操作邏輯為：

????1) Write background 0 to all cells
????2) For BaseCell = 0 to N-1
???????Complement BC
???????For OtherCell = 0 to N-1
??????????Read BC; Read OC
???????Complement BC
????3) Write background 1 to all cells
????4) Repeat Step2
????Tip: BC -> Base Cell; OC -> Other Cells

????根據(jù)操作邏輯可以看出，GALPAT算法通過2個For循環(huán)嵌套，遍歷了所有cell，每個cell被當做BC時，都會依次同所有其他OC完成1次獨立的讀/寫操作，以此來檢測它們在操作時是否會互相影響。抽象來看，可以想象為有一個乒乓球在BC與OC之間跳動，故該算法也被稱為“乒乓算法”。
????由于該算法遍歷了所有cell并針對每2個cell之間的影響也做了測試，所以該算法可以檢測到所有的SAF、TF、CF（Coupling Fault，耦合故障）和AF（Address Decoder Fault，地址解碼器故障）。它的時間復雜度為4N2，測試時間很長，測試開銷巨大，所以一般很少采用。

1.4?Butterfly

??? Butterfly算法的操作邏輯為：

????1) Write background 0
????2) For BaseCell = 0 to N-1
???????Complement BC; dist=1
???????While dist ≤ MAXDIST
??????????Read cell @ dist north from BC
??????????Read cell @ dist east from BC
??????????Read cell @ dist south from BC
??????????Read cell @ dist weat from BC
??????????Read BC? dist = dist*2
???????Complement BC
????3) Write background 1
????4) Repeat Step 2
????Tip: dist即為與BC的距離，MAXDIST為允許的最大距離

????????“1/2/3……”表示讀/寫順序

通過Butterfly算法的操作邏輯可以知道，它首先選擇1個cell作為BC，隨后依次讀BC上、右、下、左方向與BC距離為1的cell的值，再讀BC的值，隨后距離翻倍，按之前的順序再次讀取，直到距離超出允許的最大距離后跳出循環(huán)，將BC取反并給所有cell寫1，重復上述操作。在該算法的執(zhí)行過程中，每個cell都經(jīng)歷了“0 -> 1”和“1 -> 0”的過程，所以它可以檢測到所有的SAF和TF，因為它沒有檢測BC與其斜角方向的cell的耦合關(guān)系和地址互聯(lián)，所以它不能檢測出所有的CF和AF。

該算法的時間復雜度為10NlogN。

1.5 總覽

????從表中可以看到經(jīng)典算法具有一定的局限性，GALPAT雖然故障覆蓋率高，但它的開銷太大，往往不能很好的應(yīng)用，故針對讀/寫順序有特定要求的March算法應(yīng)運而生。

March Algorithms

????March算法通過March元素來表示，每個March元素包含了操作和數(shù)據(jù)：

????r0 -> read 0
????r1 -> read 1
????w0 -> write 0
????w1 -> write 1

??? March算法通過雙線箭頭表示操作順序：

?????：按地址升序讀/寫
?????：按地址降序讀/寫
?????：按地址升/降序讀/寫均可

??? March算法每1步讀寫操作的時間復雜度視為1，例如：

????{?(w0); ?(r0,w1); ?(r1) }
????含有3個March元素；
????時間復雜度為4N。

2.1?MATS

??? MATS算法的操作邏輯為：{?(w0); ?(r0,w1); ?(r1) }。
????即先對所有cell寫0，然后按照地址升序依次對每個cell讀0寫1，最后按地址降序依次從每個cell讀1，如下圖所示：

????可以看到，MATS算法含有3個March元素，因為所有cell都經(jīng)歷了“0 -> 1”的過程，所以該算法可以檢測出所有的SAF和一半的TF，不能檢測出所有的CF和AF。MATS算法對每個cell執(zhí)行了4步操作，故它的時間復雜度為4N。

2.2?MATS+

??? MATS+算法在MATS的基礎(chǔ)上增加了1步按地址降序“w0”的操作，即：{?(w0); ?(r0,w1); ?(r1,w0) }，它可以檢測出“與”模式的AF和“或”模式的AF。
????以“與”模式的AF舉例，如圖所示：

????若A1與A3兩個地址單元存在“與”模式的AF，即A1和A3中實際存放的邏輯值均為該兩個單元中的值相與之后的結(jié)果，在對A3執(zhí)行完“(r1,w0)”后，A3中的值為0，若A1與A3存在“與”模式的AF，則當我們對A1執(zhí)行”(r1,w0)”時，A1中的初值為0，沒法完成”r1”，故可以檢測出”與”模式的AF，”或”模式的AF也同理。但是由于該算法沒有檢測“1 -> 0”這個過程，故它只能檢測出一半的TF。

????它的時間復雜度為5N。

2.3 MATS++

????MATS++算法又在MATS+的基礎(chǔ)上追加了1步按地址降序“r0”的操作，即{?(w0); ?(r0,w1); ?(r1,w0,r0) }。
????追加的“讀0”操作可以檢測到MATS+中無法檢測的下轉(zhuǎn)換TF，即MATS++可以檢測到所有的SAF、AF和TF。

????它的時間復雜度為6N。

2.4 March X

??? March X算法相較于MATS++算法，將最后一步“r0”操作單獨分離出來，可以檢測到CFin。
????即：{?(w0); ?(r0,w1); ?(r1,w0)；?(r0)}。
????以A1(A)和A3(V)之間的CFin<↓;?/?>為例：

????當對A1執(zhí)行完“(r1,w0)”后，由于A1和A3之間存在CFin，對A1寫0會導致A3中的值發(fā)生翻轉(zhuǎn)，A3中的值會因此翻轉(zhuǎn)為1，在最后一步“(r0)”可以檢測到。

????相較于MATS++，March X的時間復雜度同樣為6N，但是可以檢測到CFin。

2.5?March C

??? March C算法將2個升降序?qū)ΨQ的March X操作前后拼接，可以檢測到所有的SAF、TF、AF和CF。即:{?(w0);?(r0,w1);?(r1,w0);?(r0);?(r0,w1); ?(r1,w0); ?(r0)}。

??? March C可以檢測所有的8種CFid，這里舉4個例子（A1是aggressor，A3是victim，其余4種情況是A1和A3身份互換），如圖所示：

????分析方法同March X。

????它的時間復雜度為11N。

2.6 March C-

????通過分析March C算法操作邏輯可以看出中間的“r0”操作為冗余項，故將這一步優(yōu)化掉，不影響其Fault Coverage，降低了時間復雜度。

??? March C ：{?(w0); ?(r0,w1); ?(r1,w0);?(r0); ?(r0,w1); ?(r1,w0); ?(r0)}

????March C-:{?(w0); ?(r0,w1); ?(r1,w0); ?(r0,w1); ?(r1,w0); ?(r0)}

????March C-同樣可以檢測到所有的SAF、TF、AF和CF，但時間復雜度為10N。

2.7 總覽

????隨著算法一代一代的優(yōu)化，演變出March C-這種保證Fault Coverage的同時還能減少測試時間的優(yōu)質(zhì)算法，大大節(jié)約了測試成本。

????本期介紹的以上幾種算法僅僅是一些基本的算法，實際應(yīng)用中各家公司往往會將它們互相組合來達到更優(yōu)的效果。