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

Classical Algorithms

经典算法形式比较简单，操作以简单的读写为主。

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，以此来检测单元内是否有故障，因此它也被称为“0-1算法”。在MSCAN的操作过程中，每个cell都有被置0和被置1的过程，因此该算法可以检测到所有的SAF（Stuck-At Fault，指某个单元的值被固定，SA0固定为0，SA1固定为1）。同时，因为它只有从0变化到1的过程而没有从1变化到0的过程，所以它只能检测到<↑/0>TF(上转换故障，指某个单元无法从0变化为1)。

根据该算法的操作逻辑可以知道，每个cell均经历了4步操作（R/W），故该算法的时间复杂度为4N。

Tips：时间复杂度表征的是执行一个算法所需要花费的时间的趋势，通常情况下只保留最高次项，忽略常数项。一般来说，时间复杂度越高，运行算法的时间就越长。

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

    假设黑色为逻辑1，白色为逻辑0，ckbd’即为ckbd取反。

    Checkerboard算法对所有cell写的pattern可以抽象为一个棋盘，故被称为“棋盘算法”。该算法同样可以检测到所有的SAF。因为该算法的pattern是“1-0-1”间隔排列，所以只能检测到一半的TF，具体哪个cell能检测出何种TF取决于该cell执行的操作是“1->0”还是“0->1”。

    该算法对每个cell同样执行了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

    根据操作逻辑可以看出，GALPAT算法通过2个For循环嵌套，遍历了所有cell，每个cell被当做BC时，都会依次同所有其他OC完成1次独立的读/写操作，以此来检测它们在操作时是否会互相影响。抽象来看，可以想象为有一个乒乓球在BC与OC之间跳动，故该算法也被称为“乒乓算法”。
    由于该算法遍历了所有cell并针对每2个cell之间的影响也做了测试，所以该算法可以检测到所有的SAF、TF、CF（Coupling Fault，耦合故障）和AF（Address Decoder Fault，地址解码器故障）。它的时间复杂度为4N²，测试时间很长，测试开销巨大，所以一般很少采用。

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的值，随后距离翻倍，按之前的顺序再次读取，直到距离超出允许的最大距离后跳出循环，将BC取反并给所有cell写1，重复上述操作。在该算法的执行过程中，每个cell都经历了“0 -> 1”和“1 -> 0”的过程，所以它可以检测到所有的SAF和TF，因为它没有检测BC与其斜角方向的cell的耦合关系和地址互联，所以它不能检测出所有的CF和AF。

该算法的时间复杂度为10NlogN。

1.5 总览

    从表中可以看到经典算法具有一定的局限性，GALPAT虽然故障覆盖率高，但它的开销太大，往往不能很好的应用，故针对读/写顺序有特定要求的March算法应运而生。

March Algorithms

    March算法通过March元素来表示，每个March元素包含了操作和数据：

    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都经历了“0 -> 1”的过程，所以该算法可以检测出所有的SAF和一半的TF，不能检测出所有的CF和AF。MATS算法对每个cell执行了4步操作，故它的时间复杂度为4N。

2.2 MATS+

    MATS+算法在MATS的基础上增加了1步按地址降序“w0”的操作，即：{⇕(w0); ⇑(r0,w1); ⇓(r1,w0) }，它可以检测出“与”模式的AF和“或”模式的AF。
    以“与”模式的AF举例，如图所示：

    若A1与A3两个地址单元存在“与”模式的AF，即A1和A3中实际存放的逻辑值均为该两个单元中的值相与之后的结果，在对A3执行完“(r1,w0)”后，A3中的值为0，若A1与A3存在“与”模式的AF，则当我们对A1执行”(r1,w0)”时，A1中的初值为0，没法完成”r1”，故可以检测出”与”模式的AF，”或”模式的AF也同理。但是由于该算法没有检测“1 -> 0”这个过程，故它只能检测出一半的TF。

    它的时间复杂度为5N。

2.3 MATS++

    MATS++算法又在MATS+的基础上追加了1步按地址降序“r0”的操作，即{⇕(w0); ⇑(r0,w1); ⇓(r1,w0,r0) }。
    追加的“读0”操作可以检测到MATS+中无法检测的下转换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执行完“(r1,w0)”后，由于A1和A3之间存在CFin，对A1写0会导致A3中的值发生翻转，A3中的值会因此翻转为1，在最后一步“(r0)”可以检测到。

    相较于MATS++，March X的时间复杂度同样为6N，但是可以检测到CFin。

2.5 March C

    March C算法将2个升降序对称的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”操作为冗余项，故将这一步优化掉，不影响其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 总览

    随着算法一代一代的优化，演变出March C-这种保证Fault Coverage的同时还能减少测试时间的优质算法，大大节约了测试成本。

    本期介绍的以上几种算法仅仅是一些基本的算法，实际应用中各家公司往往会将它们互相组合来达到更优的效果。