随着数字电路规模与复杂度的不断提高,电路测试变得越来越困难。传统的测试生成算法已经无法适应数字电路的发展,需要不断的研究新颖的测试生成及其相关的算法。本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下:1)通过介绍VLSI集成电路实现的基本流程,阐述测试生成在集成电路实现中的作用和地位。文中还介绍了集成电路测试的基本流程,综述了当前数字电路测试生成的发展及研究状态。2)较详细地介绍了可满足性问题的基本概念和代数基础,以及可满足性算法的基本分类、发展历史以及研究与应用状态。3)提出一个与传统组合电路测试生成算法不同的无回溯并行多路径搜索测试向量生成算法(NBMP)。算法在生成测试向量过程中生成基于原始输入端的奇异立方和与原始输出端关联的传输立方,并利用生成的奇异立方和传输立方生成测试向量。实现过程无须回溯,采用规模控制和多路径探索策略。算法对ISCAS85基准电路进行实验,将实验结果与传统算法结果进行比较,实验表明NBMP算法故障覆盖率优于传统算法。通过分析和实验结果证明算法时间复杂度近似为线性。4)本文提出一个时序电路测试生成算法——基于SAT分级处理增量式测试生成算法(HISAT)。在第一级,以算法提出的无分支路径为单位,向输出端进行故障敏化。用隐含分支敏化通路树存放备选路径,采用路径冲突预判策略提高路径选择速度。在敏化路径过程中生成的约束CNF及故障激活CNF,被第二级增量式SAT算法所使用。在第二级,对于冲突节点进行蕴含学习以预防未来冲突的发生。在蕴含学习规则中,增加了基于电路结构的学习规则。当输入端不为原始输入端时,需回到前一帧搜索可满足解,一个可观察参数指导算法向原始输入端搜索。输出端不为原始输出端时,需向后一帧敏化,算法同样提供一个可观察参数指导算法向原始输出端敏化。算法对ISCAS89基准电路进行实验,且与其它算法结果进行了比较和分析。实验表明HISAT算法的故障覆盖率高。5)提出一个基于带路径布尔函数的电路冗余识别(RDIBP)算法。RDIBP算法能够发现数字电路中的冗余故障。本文提出了带中间节点信息,基于SOP形式的布尔函数表示方法。为了便于发现冗余故障改进了传统的布尔函数化简。根据电路节点相关性,将电路节点分组以提高算法效率,防止内存爆炸。通过调整控制参数确保算法在合理的时间内完成。算法对ISCAS85,ISCAS89和ITC99基准电路进行实验,且与其它算法结果进行了比较和分析。实验表明RDIBP算法能够有效地识别电路冗余故障。6)本文又提出一个多目标启发式集成电路测试集约简算法(Priority-Selected)。集成电路故障测试集往往含有大量的冗余,造成集成电路测试效率降低。本文对已有的贪婪算法、GE算法、GRE算法和Harrold提出的基于测试用例重要性的启发式算法进行了分析,提出一个依据必不可少用例和最大故障需求用例的启发式集成电路测试集约简算法(Priority-Selected)。Priority-Selected算法通过计算测试向量权值选择需要的测试用例,并去除测试集中的所有的冗余,因此选择策略更加合理,效率也更高。两个系列的测试用例集用来测试贪婪算法、GE算法、GRE算法、H算法和Priority-Selected算法的效率。实验表明Priority-Selected算法是有效的。7)论文最后对所做工作进行了总结,并提出了进一步研究的方向。