《TestSetCompactionAlgorithmsforCombinationalCircuits》中文翻译.docVIP

计算机辅助设计国际会议记录，1998年11月 组合电路的测试集压缩算法 Ilker Hamzaoglu 和Janak H.Patel 乌尔班纳市伊利诺伊州大学可靠和高性能计算中心 摘要：文章提出两种新算法，冗余矢量消除算法（RVE）和基本故障减少算法（EFR），为组合电路在故障模型单卡下产生压缩测试集，在故障测试集下启发式估算最小单固定故障。结合动态压缩算法，这些算法被合并成组合电路的ATPG系统，称为MinTest。MinTest找到更低跳变数，相比先前为ISCAS85公布的记过，其能产生更小的测试集，同时能完整扫描ISCAS89基准电路。 1 介绍 压缩测试集对降低超大规模集成电路的测试成本非常重要，通过降低测试应用时间可实现。这对基于扫描链电路尤为重要，因为这些电路的测试时间与测试集大小的产生和扫描链中存储设备数量有直接关系。少的测试集也降低测试存储设备的需求。 因为在故障测试集中为给定的不可缩短的组合电路估算最小单固定故障已经被证明是NP完全问题，所以在文献中提出了一些基于不同试探法的测试集压缩算法，例如，静态压缩算法[6],动态压缩算法[6]，基于测试产生的独立和兼容故障集[1,9,12,14]，倒序故障仿真[13]，最大压缩[12]，旋转回溯[12]，双重检测[8,9]，二选一[9]，三选二[9]，强迫对合并[4]，基本故障修剪[4]。 虽然这些算法能成功产生小测试集，但是作为结果的测试集仍然比已知的低跳变数要大。这是因为如下两个原因：以前公开发表的测试压缩集算法不能更进一层和测试集结合，已知低跳变数不是严格的。为了进一步结束这个缺口，本文解决这两个问题。我们提出两个新的测试集压缩算法，冗余矢量消除算法和基本故障减少算法，以及在故障测试集中一个新的估算最小单固定故障启发法。这些算法和动态压缩算法为组合电路包含到先进的ATPG系统中，称为MinTest. MinTest找到更低跳变数，相比先前为ISCAS85公布的记过，其能产生更小的测试集，同时能完整扫描ISCAS89基准电路[2,3]. 文章余下部分的结构如下。第二部分叙述文章中将要用到的定义。第三部分叙述冗余矢量消除算法。基本故障消除减少算法在第四部分出现。最小测试集估算启发法在第五部分描述。第六部分给出实验结果。最后第七部分进行总结。 2 预备知识 在这部分中，我们将介绍文章将会使用的定义。如果一个测试矢量能发现至少一个在这个测试集中其他矢量不能发现的故障，那么在这个给定测试集中，该测试矢量称为基本矢量。如果一个故障只能被给定测试集中的这个测试矢量发现，那么这个故障被定义为测试矢量的基本故障[4,9].换句话说，一个基本矢量至少发现一个基本故障。如果测试矢量不能发现任何基本故障，那么在给定测试集中该测试矢量被认为是冗余的，也就是说，被它发现的所有的故障也被这个测试集中其他测试矢量发现[9]. 如果测试集中测试矢量，测试矢量被新测试矢量替代，能发现测试矢量的基本故障，同时故障只能被和发现，那么测试矢量的基本故障据说会被删除[4]。 如果两个故障能被一个单一测试向量检测出来，那么称它们是兼容的。类似地，如果两个故障不能被一个单一测试向量检测出来，那么称它们是不相容的。给定故障集的不相容图表，，定义为,其中[1,4,9,14].如果在一个集合中所有的故障都是成对的不相容，那么这个故障集就称为独立故障集[1].对于一个给定的组合电路，最大尺寸的独立故障集称为最大独立故障集。因为寻找最大独立故障集是NP完全问题[10],因此在实践中经常使用的是最全面的独立故障集。 在故障模型的单一故障下，给定组合电路的最小测试集大小是指在这个电路中，检测故障中所有可检测的单一故障的最少的测试向量的数量。 3 冗余矢量消除 在动态测试模式产生的过程中，被早期测试向量检测到的一些故障也能偶然地被后来产生的测试向量检测到。因此，随着在ATPG算法中产生更多的向量，早期产生的测试向量有可能变成冗余向量。冗余矢量消除算法（RVE）在测试向量产生的过程中识别冗余矢量同时将他们从测试集中动态删除。如图1所示，RVE模拟故障列表中所有故障，除了那些被证明不具有可测性的故障，算法同时记录被每个矢量检测到的故障，基本故障数，和故障检测时间。例如，在测试矢量产生过程中，如果一个测试矢量的基本故障数减少到0，那么这个测试矢量就成为冗余矢量并且将被从测试集中删除。 下面举例说明，RVE算法比翻转顺序故障模拟（ROFS）算法更能降低测试集大小[13].这是因为如果被检测的一些故障只能被早期产生的测试矢量检测，那么ROFS算法不能识别冗余测试矢量。如果被检测的所有故障也能被早期产生的测试矢量检测，那么ROFS算法才能识别出冗余矢量。 举例：考虑故障集。假设针对这个故障集，ATPG系统产生