背景介绍

Combinational ATPG是一个Branch and Bound的演算法，它的本质是在组合电路（Combinational Circuit）内找到适合的输入向量（Input Vector）工具。所有输入讯号的可能组合形成输入空间（Input Space）。这个输入空间的大小主要和组合电路内Primary Inputs的数量有关，它会形成一个二元树（Binary Tree），每个节点（Node）有两个分支（Branch），节点上的符号代表输入讯号的代号，假定左边的分支代表该Node输入值为0，右边的分支代表该Node输入值为1。ATPG用DFS（Depth First Search）可以在输入空间内找到一条路径（Tour），当所有输入讯号（Input）的值依照这条路径输入进去电路设计的时候，能够满足某个我们想观察的性​​质（ Property）。

由于输入空间这个二元树的节点数量太大，需要一个更有效率的资料结构才能够在有限的记忆体空间内表示它；另外一方面人们也致力于发展如何缩小这个输入空间以及更聪明的寻访该输入空间的方法。
...
...