|
D算法描述如下:
(1)准备:
(1.1)求出每一个元件的覆盖Cover和传播D立方pdc;
(1.2)求出指定定故障元件的故障D立方pdcf;
(1.3)初始化D前沿DF和C前沿CF:DF = CF = φ;
(2)形成初始测试D立方tc0:
(2.1)若pdcf = φ则算法失败(求不出该故障的测试码),退出;
(2.2)选f∈pdcf, pdcf = pdcf-{f};
(2.3)tc0 = {f};
(2.4)形成D前沿DF和C前沿CF;
(3)判断是否成功:
(3.1)若CF ≠ φ, 则转(5), 做一致性操作;
(3.2)若D或D 已到达某一外部输出端,则D算法成功,结束;
(3.3)否则执行(4),做D驱赶;
(4)D驱赶:
(4.1)若DF = φ, D驱赶失败,回溯到(2);
(4.2)若DF≠φ, 选元件 d∈DF, DF = DF-{d}, 令Pd = pdc(d);
(4.3)若Pd = φ, 则元件d的D驱赶失败,回溯到(4.1), 试选另一元件d;
若Pd≠φ, 则选d的一个传播D立方PP∈Pd, Pd = Pd-{PP};
(4.4)作D交:tck+1 = tck∩DPP;
(4.5)若tck+1 = φ, PP失败,tck+1无效,回溯到(4.3), 试选另一传播D立方PP;
(4.6)若tck+1≠φ, 形成新的DF和CF, 执行(5), 做一致性操作;
(5)做一致性操作:
(5.1)若CF = φ, 一致性操作成功,承认最近一次D驱赶结果,转(3), 判是否成功;
(5.2)若CF≠φ, 选元件 e∈CF, CF = CF-{e};
令Ce = Cover(e); (或pdc(e), 若其输入输出值中有D或D)
(5.3)若Ce = φ, 表明不一致,不承认最近一次D驱赶结果,
回溯到(4.3), 试选另一传播D立方PP;
(5.4)若Ce≠φ, 则选e的一个质立方或传播D立方CC∈Ce, Ce = Ce-{CC};
(5.5)作D交:tck+1 = tck CC;
(5.6)若tck+1 = φ, 表明不一致,CC失败,tck+1无效,
回溯到(5.3), 试选另一传播D立方CC;
(5.7)若tck+1≠φ, 形成新的DF和CF, 重复执行(5), 做一致性操作;
图7. 9是D算法粗框图。
|