📚 课程目录第3章组合逻辑测试生成基础

3. 组合逻辑测试生成基础：D算法原理、步骤、示例与优缺点

组合逻辑测试生成的核心任务是为一个组合电路找到能够检测特定故障的输入向量。D算法（D-Algorithm）是历史上第一个被形式化、系统化的测试生成算法，由 Roth 等人于 1966 年提出。它通过引入“D”和“D̅”符号，将故障效应在电路中的传播与敏化过程统一为代数运算，为后续的 PODEM、FAN 等算法奠定了理论基础。

  核心思想：D算法将“正常电路输出为1、故障电路输出为0”的差异抽象为符号 D（1/0），将“正常为0、故障为1”的差异抽象为 D̅（0/1）。测试生成过程即是将 D 或 D̅ 从故障点传播到主输出，同时确保所有路径上的逻辑值一致。

3.1 D算法原理

D算法的理论基础是布尔差分的代数化表示。它通过以下三个核心操作完成测试向量的推导：

故障激活（Fault Activation）：在故障点处设置与正常值相反的逻辑值，产生 D 或 D̅。
故障传播（Fault Propagation）：通过敏化路径将 D 或 D̅ 传递至至少一个主输出。
一致性操作（Consistency Operation）：确保所有已赋值的信号线不存在逻辑冲突，并为未赋值线寻找合理的赋值。

D算法使用一个“D-立方”（D-Cube）集合来描述门电路的输入输出关系。每个门都有一个“奇异立方”（Singular Cover）和“传播立方”（Propagation D-Cube）。奇异立方用于在一致性操作中确定门输入与输出的关系；传播立方则用于描述如何将 D 或 D̅ 从输入传播到输出。

关键符号：D = 1/0（正常为1，故障为0）；D̅ = 0/1（正常为0，故障为1）。在电路图中，D 和 D̅ 被视为“故障信号”，它们沿着路径传播时遵循门电路的逻辑规则。

3.2 D算法步骤

D算法的执行过程可以分解为以下五个主要步骤。每一步都涉及对电路信号线的赋值与检查。

步骤	名称	操作描述	关键数据结构
1	故障激活	在故障线 g 上设置 D 或 D̅。若故障为 sa0，则 g = D；若为 sa1，则 g = D̅。	故障立方
2	D-前沿初始化	将故障点加入 D-前沿（D-Frontier），即所有输出为 D 或 D̅ 且尚未传播到主输出的门。	D-前沿集合
3	D-传播	从 D-前沿中选一个门，使用其传播 D-立方将 D 或 D̅ 向输出端推进。更新 D-前沿。	传播 D-立方
4	一致性检查	对已赋值的信号线进行逻辑一致性检查。若发现冲突，则回溯到上一个决策点，尝试其他传播路径。	奇异立方
5	回溯与完成	若 D 或 D̅ 到达主输出且所有赋值一致，则成功；否则回溯。若所有路径尝试失败，则故障不可测。	决策树

注意：D算法在遇到“扇出重汇聚”（Fan-out Reconvergence）结构时，可能产生“奇偶性冲突”或“路径冲突”，导致算法效率下降。这是 D 算法的主要局限性之一。

3.3 D算法示例

以下通过一个简单的组合电路示例，演示 D 算法生成测试向量的完整过程。电路包含一个两输入与非门（NAND）和一个两输入或非门（NOR），最终汇入一个与门（AND）。

电路结构：

输入：A, B, C, D
内部节点：E = NAND(A, B)，F = NOR(C, D)
输出：G = AND(E, F)

目标故障：节点 E 上发生 stuck-at-0 故障（E sa0）。

D算法执行过程：

故障激活：E sa0 表示正常值为1，故障值为0，因此 E = D。为激活故障，需使 NAND 门输出为1，即输入 A=0 或 B=0（至少一个为0）。选择 A=0, B=1。
D-前沿初始化：E = D，其扇出指向与门 G。D-前沿 = {G}。
D-传播：从 D-前沿选择 G。G 为与门，其传播 D-立方要求：一个输入为 D，另一个输入为 1（非控制值）。因此需要 F = 1。
一致性操作（对 F）：F = NOR(C, D) = 1，要求 C=0 且 D=0。
一致性检查：所有赋值：A=0, B=1, C=0, D=0, E=D, F=1, G=D。无冲突。
完成：D 已传播到主输出 G，测试向量为 (A,B,C,D) = (0,1,0,0)。

  测试向量结果：输入 (A,B,C,D) = (0,1,0,0) 可检测 E sa0 故障。正常输出 G = 0，故障输出 G = 1，差异在输出端可观测。

3.4 D算法优缺点

D算法作为测试生成领域的奠基性算法，其优缺点非常鲜明。理解这些特性有助于在实际工程中选择合适的算法或进行算法改进。

维度	优点	缺点
完备性	理论上对任何组合逻辑故障都能找到测试向量（若存在），具有完备性。	对于大型电路，搜索空间呈指数级增长，效率低下。
理论基础	首次将测试生成形式化为代数运算，为后续算法（PODEM、FAN）提供了理论框架。	D-立方运算复杂，实现难度较高。
处理能力	能够处理多路径传播和扇出重汇聚结构。	在扇出重汇聚处容易产生“奇偶性冲突”，导致大量无效回溯。
回溯效率	回溯机制保证了算法的完备性。	回溯策略简单粗暴，缺乏启发式引导，常陷入深度搜索。
适用场景	适合中小规模组合电路（门数 < 10,000）的测试生成。	不适合大规模电路或时序电路（需扩展为时序D算法）。

工程启示：在实际的 DFT 工具中，D 算法通常作为“最后手段”使用——当更高效的算法（如 PODEM、FAN）无法生成测试向量时，才启用 D 算法进行穷举搜索。现代 EDA 工具已很少直接使用原始 D 算法，但其核心思想（故障激活 + 传播 + 一致性）是所有 ATPG 算法的基石。

D算法与后续算法的对比：

算法	核心改进	回溯策略	适用规模
D算法	D-立方代数系统	无启发式回溯	小规模
PODEM	面向目标的隐式枚举	基于PI赋值的回溯	中规模
FAN	扇出分析与唯一敏化	多路回溯与停止规则	大规模
SOCRATES	静态与动态学习	基于冲突学习的回溯	超大规模

  总结：D算法是测试生成领域的“第一原理”。虽然其直接应用已不多见，但理解 D 算法是掌握所有现代 ATPG 技术的前提。在 BIST 设计中，D 算法的传播与一致性思想也被用于测试响应压缩器的设计与故障诊断。