第三章 组合电路ATPG算法：从D算法到SOCRATES

好，咱们进入正题。组合电路的ATPG算法，说白了就是怎么给芯片“出题”——找出那些能暴露故障的测试向量。我刚开始接触这块时，觉得不就是找条路径吗？后来才发现，这里面的门道深着呢。

今天要聊的四个算法：D算法、PODEM、FAN、SOCRATES。它们一个比一个聪明，一个比一个快。咱们一个一个来看。

3.1 D算法：老祖宗的智慧

D算法是1966年提出的，算是ATPG的鼻祖。它的核心思想很简单：同时考虑好电路和坏电路。

这里有个关键概念——D立方。D代表“好电路是1，坏电路是0”，D-bar（写作\(\overline{D}\)）代表“好电路是0，坏电路是1”。你想想看，这不就是同时模拟了两种状态吗？

D算法的步骤大致是：

1. 选一个故障，比如某个节点s-a-1（ stuck-at 1）
2. 在故障点设置D或D-bar
3. 向前传播D到某个输出端
4. 向后回溯，确定所有输入值

我个人习惯把D算法比作“走迷宫”。你从故障点出发，要找到一条路通到输出，同时还得保证这条路走得通。嗯，这里要注意——D算法会尝试所有可能的路径，所以它一定能找到测试向量（如果存在的话）。

我在项目中遇到过这样的情况：一个中等规模的电路，D算法跑了几个小时还没出结果。当时我就想，这肯定得优化啊。

3.2 PODEM算法：别再盲目回溯了

PODEM（Path-Oriented Decision Making）是1981年提出的。它改进了D算法的一个大问题——不必要的回溯。

D算法是怎么干的？它先选一条路径，然后去赋值。如果发现走不通，就回溯重来。但问题是，它可能回溯到很远的地方，浪费大量时间。

PODEM的思路是：只对原始输入（PI）做决策。说白了，我不去管内部节点怎么赋值，我只管输入引脚应该设成什么值。内部的事情，让电路自己去决定。

这样做的好处很明显：

• 决策空间变小了（只有PI需要决定）
• 回溯次数大大减少
• 速度比D算法快很多

我曾经用PODEM处理一个2000门左右的电路，D算法跑了45分钟没出结果，PODEM只用了3秒。你说这差距大不大？

3.3 FAN算法：更聪明的回溯策略

FAN（Fanout-Oriented）算法是1983年问世的。它比PODEM又进了一步。

FAN的核心改进有两点：

1. 扇出点处理：遇到扇出点（一个信号分叉成多个），FAN会特别小心。它会优先处理那些“容易”的分支。
2. 唯一赋值：有些节点的值是“唯一确定”的，比如某个门的所有输入都定了，输出也就定了。FAN会先处理这些，减少后续的猜测。

你想想看，这就像下棋。新手走一步看一步，高手会先处理那些“必走之棋”。FAN就是那个高手。

我记得有一次，一个同事用PODEM跑一个电路，跑了半小时没结果。换成FAN后，5分钟就搞定了。原因就是这个电路扇出特别多，FAN的处理策略正好对症。

3.4 SOCRATES算法：集大成者

SOCRATES（Structured and Optimized Cell-based ATPG System）是1988年推出的。它把前面几个算法的优点都整合了进来，还加了一些自己的绝活。

SOCRATES的主要改进：

改进点	说明
静态学习	提前分析电路结构，找出隐含的约束关系
动态学习	在搜索过程中，实时学习新的约束
改进的唯一赋值	比FAN更彻底地处理唯一赋值
多路径传播	同时尝试多条传播路径

说白了，SOCRATES就是“站在巨人的肩膀上”。它用了D算法的完备性思想，PODEM的PI决策策略，FAN的扇出处理，再加上自己的学习机制。

我曾经用SOCRATES处理一个上万门的电路，D算法根本跑不动，PODEM跑了几个小时，FAN跑了40分钟，SOCRATES只用了8分钟。这就是技术进步的力量。

3.5 四个算法的对比总结

咱们来做个对比，一目了然：

算法	提出年份	完备性	速度	适用场景
D算法	1966	完备	慢	小规模电路，教学演示
PODEM	1981	完备	中等	中等规模电路
FAN	1983	非完备	快	扇出多的电路
SOCRATES	1988	完备	最快	大规模电路，工业应用

嗯，这里要提醒一句：没有银弹。每个算法都有自己的适用场景。我个人的建议是：

• 做教学或研究，从D算法入手，理解基本原理
• 做工程，优先用SOCRATES或其变种
• 遇到特殊电路（比如扇出特别多），试试FAN

好了，这一章的内容就到这儿。下一章咱们聊聊时序电路的ATPG，那又是另一番天地了。