基于重量分析的OBDD变量排序算法

有序的二叉判决图（ＯＢＤＤ）是布尔表达式的一种有效表示方法，但它的体积对变量排序具有较强的依赖性．本文提出一种电路结构图，并在此基础上定义了原始输入重量和节点重量等参数，并建立了用重量分析来指导的ＯＢＤＤ变量排序算法．由于从考虑变量对输出函数的影响出发与从考虑ＯＢＤＤ节点共享性出发对变量排序的要求不同，本文分别设计了两类算法．实验结果表明，本文对大多数标准电路变量排序的效果都优于国际上的同类算法，尤其是对一些较难排序的电路（如Ｃ２６７０）效果更加突出．

一个有效的通路时滞故障测试生成系统DTPG

本文提出了一种两向量测试模式下的通路时滞故障分类，并在此基础上设计并实现了一个有效的通路时滞故障测试生成系统DTPG，该系统可识别强健可测通路、非强健可测通路和功能可敏化通路．DTPG用通路标识值来表示通路，并用一个位表结构的通路信息表来存储通路测试信息．实验结果表明，DTPG在利用内存上是有效的，可以为通路数较大的电路（如C3540）产生时滞测试向量对．

基于遗传算法的TBDD排序方法

带时间参数的二叉判决图（TBDD）在电路的时滞故障测试中有着重要的应用价值，但其变量排序是用常规方法无法解决的一个优化问题．本文提出一种基于遗传算法的TBDD排序算法．用快速衡量值和TBDD节点数来计算个体的适应度，针对变量排序的特定问题，提出一种模板保序交叉方法．采用自适应的变异概率计算方法，并提出一个适合于TBDD排序问题的变异算法．实验结果表明较好地解决了TBDD的排序问题．

基于蕴涵树的冗余添加和删除技术

可替换线逻辑综合（如ＲＡＭＢＯ）是近年来兴起的一种方法，它采用测试向量自动生成（ＡＴＰＧ）方法来实现冗余添加和删除．但是，频繁调用逻辑蕴涵过程使得整个逻辑综合的速度较慢．因此，如何减少ＡＴＰＧ过程的调用次数便成为提高这类算法的速度之关键．该文提出一种逻辑蕴涵树来存储节点间的逻辑蕴涵关系，并设计了一个基于逻辑蕴涵树的可替换线源节点的挑选算法．在此基础上形成一个快速的可替换线逻辑变换算法ＩＢＡＷ．实验结果表明，在为目标线寻找可替换线时，ＩＢＡＷ的速度是ＲＡＭＢＯ的３．６倍．

OBDD变量排序的自适应选择算法

有序的二叉决策图（ＯＢＤＤ）是形式验证领域的基础技术之一．由于ＯＢＤＤ的大小对变量序非常敏感，使得变量排序问题成为最关键的一个问题．首先将ＯＢＤＤ变量排序问题分解为３ 个子问题，定义了若干启发信息，给出了上述子问题的启发式解法；然后提出了一个变量排序自适应选择算法，从若干候选变量序中选出“最佳”的变量序．最后给出了ＩＳＣＡＳ８５ 电路的实验结果．

基于行列奇偶校验和特征分析法的数字系统自诊断技术

提出一种用行列奇偶校验原理和特征压缩技术实现的数字电路板自诊断技术，讨论 了它对电路板上固定型故障的定位性能。此方案可准确定位电路板上单模块故障和位于同行 或同列的多模块故障，并可将其它多模块故障定位在一个较小的区间里。讨论了故障模块数目 的分布情况，从中可以看到单模块故障和双模块故障出现的概率在所有故障的出现概率中占 有很大比例，因而本方案具有较大的实用价值。

Short-Time Scaling of Variable Orderingof OBDDs

A short-time scaling criterion of variable ordering of OBDDs is proposed. By this criterion it is easy and fast to determine which one is better when several. variable orders are given, especially when they differ 10% or more in resulted BDD size from each other. An adaptive variable order selection method, based on the short-time scaling criterion, is also presented. The experimental results show that this method is efficient and it makes the heuristic variable ordering methods more practical.

Efficient Heuristic Variable Ordering of OBDDs

An efficient heuristic algorithm for variable ordering of OBDDs, the WDHA (Weight and Distance based Heuristic Algorithm), is presented. The algorithm is based on the heuristics implied in the circuit structure graph. To scale the heuristics, pi -weight , node -weight , average -weight and pi -distance in the circuit structure graph are defined. As any of the heuristics is not a panacea for all circuits, several sub algorithms are proposed to cope with various cases. One is a direct method that uses pi -weight and pi -distance . The others are based on the depth first search (DFS) traversal of the circuit structure graph, with each focusing on one of the heuristics. An adaptive order selection strategy is adopted in WDHA. Experimental results show that WDHA is efficient in terms of BDD size and run time, and the dynamic OBDD variable ordering is more attractive if combined with WDHA.