数字集成电路自动测试生成算法研究
|
摘要
随着数字电路规模与复杂度的不断提高,电路测试变得越来越困难。传统的测试生成算法已经无法适应数字电路的发展,需要不断的研究新颖的测试生成及其相关的算法。
本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下:
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)论文最后对所做工作进行了总结,并提出了进一步研究的方向。
With the scale and complexity growing, digital Circuit testing is becoming more and more difficult. Traditional test pattern generations are no longer meeting the actual development demand of digital circuit. Novel test pattern generation and related algorithms need to be proposed constantly.
Test pattern generations are chosen as objects, and fault coverage and time complexity are aimed in this dissertation. The major research contents and results are as follows:
1) The Role and Status of test pattern generation is realized by introducing basic implementing process of VLSI. The main flow of IC testing is described too. Meanwhile the development and current study status of test pattern generation for digital circuits is summarized.
2) This dissertation introduces basic concepts and algebra of satisfiability in detail. At same time, satisfiability algorithms are expatiated on classification, history, present research, and applications.
3) A Non-backtracking Multipath Algorithm For Test Pattern Generation (NBMP) which different from traditional test pattern generation is proposed. A Non-backtracking Multipath Algorithms
NBMP constructs singular cubes which only contain primary inputs and fault driving cubes which only connect with primary outputs. Then, NBMP produces test patterns using singular cubes and fault driving cubes. NBMP not backtrack during processing. It adopts scope restricting and multi-path searching strategy.
The fault coverages of test pattern involving ISCAS85 benchmarks show that NBMP algorithm is superior to the traditional test pattern generation. Moreover, the time complexity is proved approximate linearity by the time complexity analysis and experimental results
4) A test pattern generation algorithm for sequential circuits, Hierarchical and
Incremental SAT-based Test Pattern Generation (HISAT), is shown in this dissertation. At the first stage, faults are sensitized to output in unit of non-branching path gradually. Optional branches are put into an implicit sensitized branch tree. The prediction strategy for conflicting paths speeds path selection. After that, CNF of Constraints and activation of faults generated in this stage are used for the incremental SAT executed in the second stage.
At the second stage, Implication learning is implemented while values of nodes conflict. A new learn rule based on circuit structure is added into implication rules. Algorithm returns to preceding frame for searching satiable solution when the input is not primal input. An observable parameter helps searching along the direction of primal input. By the same way, algorithm goes to following frame for fault sensitization when the output is not primal output. An observable parameter helps sensitizing towards primal output too.
The fault coverages involving ISCAS89 benchmarks show that HISAT algorithm is good at the fault coverage.
5) Circuits redundancy identification on Boolean functions with paths (RDIBP) is proposed in this dissertation.
The RDIBP algorithm which bases on Boolean functions with paths can identify redundancy nodes of digital circuits. Boolean function representations with intermediate nodes expressed as SOP are provided by RDIBP. Moreover, the traditional Boolean function simplifications are improved for finding redundant faults more easily. The circuit nodes are divided into groups according to correlation for increasing algorithm efficiency and preventing memory explosion. So RDIBP is ensured within a reasonable time by adjusting the control parameters.
RDIBP experimental results on ISCAS85 ISCAS89 and ITC99 benchmark circuits are compared and analyzed with other algorithms. The experimental results indicate that it can identify redundancy efficiently.
6) In this dissertation, a multi-objective heuristic for ICs test suite reduction is also given.
The time efficiency of ICs test is reduced greatly because large numbers of redundant test cases exist in test suites. Four test suite reduction algorithms, which are Greedy algorithm, GE, GRE and H heuristic based on the importance of test cases, are compared and analyzed.
Furthermore, a new heuristic (Priority-Selected) based on the essential cases and maximal fault coverage is presented for test suite reduction. Priority-Selected algorithm selects essential cases and deletes redundancy by computing test cases weights. Therefore, selection strategies are more reasonable and efficient.
Two groups of test suits are used for efficiency of Greedy, GE, GRE, H heuristic and‘Priority-Selected’.‘Priority-Selected’is proved effective in test suite reduction. 7) Finally, the work of this dissertation is summarized and the prospective research is discussed.
本文以测试生成算法作为主要研究对象,以提高测试算法故障覆盖率和时间效率为研究目标。主要的研究内容和研究成果如下:
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)论文最后对所做工作进行了总结,并提出了进一步研究的方向。
With the scale and complexity growing, digital Circuit testing is becoming more and more difficult. Traditional test pattern generations are no longer meeting the actual development demand of digital circuit. Novel test pattern generation and related algorithms need to be proposed constantly.
Test pattern generations are chosen as objects, and fault coverage and time complexity are aimed in this dissertation. The major research contents and results are as follows:
1) The Role and Status of test pattern generation is realized by introducing basic implementing process of VLSI. The main flow of IC testing is described too. Meanwhile the development and current study status of test pattern generation for digital circuits is summarized.
2) This dissertation introduces basic concepts and algebra of satisfiability in detail. At same time, satisfiability algorithms are expatiated on classification, history, present research, and applications.
3) A Non-backtracking Multipath Algorithm For Test Pattern Generation (NBMP) which different from traditional test pattern generation is proposed. A Non-backtracking Multipath Algorithms
NBMP constructs singular cubes which only contain primary inputs and fault driving cubes which only connect with primary outputs. Then, NBMP produces test patterns using singular cubes and fault driving cubes. NBMP not backtrack during processing. It adopts scope restricting and multi-path searching strategy.
The fault coverages of test pattern involving ISCAS85 benchmarks show that NBMP algorithm is superior to the traditional test pattern generation. Moreover, the time complexity is proved approximate linearity by the time complexity analysis and experimental results
4) A test pattern generation algorithm for sequential circuits, Hierarchical and
Incremental SAT-based Test Pattern Generation (HISAT), is shown in this dissertation. At the first stage, faults are sensitized to output in unit of non-branching path gradually. Optional branches are put into an implicit sensitized branch tree. The prediction strategy for conflicting paths speeds path selection. After that, CNF of Constraints and activation of faults generated in this stage are used for the incremental SAT executed in the second stage.
At the second stage, Implication learning is implemented while values of nodes conflict. A new learn rule based on circuit structure is added into implication rules. Algorithm returns to preceding frame for searching satiable solution when the input is not primal input. An observable parameter helps searching along the direction of primal input. By the same way, algorithm goes to following frame for fault sensitization when the output is not primal output. An observable parameter helps sensitizing towards primal output too.
The fault coverages involving ISCAS89 benchmarks show that HISAT algorithm is good at the fault coverage.
5) Circuits redundancy identification on Boolean functions with paths (RDIBP) is proposed in this dissertation.
The RDIBP algorithm which bases on Boolean functions with paths can identify redundancy nodes of digital circuits. Boolean function representations with intermediate nodes expressed as SOP are provided by RDIBP. Moreover, the traditional Boolean function simplifications are improved for finding redundant faults more easily. The circuit nodes are divided into groups according to correlation for increasing algorithm efficiency and preventing memory explosion. So RDIBP is ensured within a reasonable time by adjusting the control parameters.
RDIBP experimental results on ISCAS85 ISCAS89 and ITC99 benchmark circuits are compared and analyzed with other algorithms. The experimental results indicate that it can identify redundancy efficiently.
6) In this dissertation, a multi-objective heuristic for ICs test suite reduction is also given.
The time efficiency of ICs test is reduced greatly because large numbers of redundant test cases exist in test suites. Four test suite reduction algorithms, which are Greedy algorithm, GE, GRE and H heuristic based on the importance of test cases, are compared and analyzed.
Furthermore, a new heuristic (Priority-Selected) based on the essential cases and maximal fault coverage is presented for test suite reduction. Priority-Selected algorithm selects essential cases and deletes redundancy by computing test cases weights. Therefore, selection strategies are more reasonable and efficient.
Two groups of test suits are used for efficiency of Greedy, GE, GRE, H heuristic and‘Priority-Selected’.‘Priority-Selected’is proved effective in test suite reduction. 7) Finally, the work of this dissertation is summarized and the prospective research is discussed.
引文
1.蔡懿慈,周强.超大规模集成电路设计导论(第二版) [M].北京:清华大学出版社, 2005.
2. M. L. Bushnell, V. D. Agrawal.超大规模集成电路测试—数字、存储器和混合信号系统[M].北京:电子工业出版社, 2005.
3.雷绍充,邵志标,梁峰.VLSI测试方法学和可测性设计[M].北京:电子工业出版社, 2005.
4. International technology oadmap for semiconductors 2009 edition test and test equipment [EB/OL]. http://www.itrs.net/Links/2009ITRS/2009Chapters_2009Tables/ 2009_Test.pdf, 2009.
5. B. Krishnamurthy, S. B. Akers. On the complexity of estimating the size of a test set[J]. IEEE Trans. Computers, 1984, C-33( 8): 750–753.
6. R. Eldred. Test Routines Based on Symbolic Logical Statements[J]. ACM Journal, 1958, 6(1):33–36.
7. J. P. Roth. Diagnosis of automata failures: A calculus and a method[J]. IBM J. Res. Develop., 1966 , 10(4):278-291.
8. J. P. Roth, W. G. Bouricius, P. R. Schneider. Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits[J]. IEEE Trans. on Electronic Computers, 1967, EC-16(5):567-580.
9. P. Goel. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits[J]. IEEE Trans. on Computers, 1981, C-30(3):215-222.
10. H. Fujiwara, T. Shimono. On the Acceleration of Test Generation Algorithms[J]. IEEE Trans. on Computers, 1983, C-32(12):1137-1144.
11. M. H. Schulz, E. Auth. Advanced Automatic Test Pattern Generation and Redundancy Identi_cation Techniques[C]. in Proc. of the International Fault-Tolerant Computing Symp., 1988, 30-35.
12. M. H. Schulz, E. Auth. Improved Deterministic Test Pattern Generation with Applications to Redundancy Identication [J]. IEEE Trans. on Computer-Aided Design, 1989, 8(7):811-816.
13. M. H. Schulz, E. Trischler, T. M. Serfert. SOCRATES: A Highly Effcient Automatic Test Pattern Generation System[J]. IEEE Trans. on Computer-Aided Design, 1988, CAD-7(1):126-137 .
14. W. Kunz, D. K. Pradhan. Recursive Learning: An Attractive Alternative to the Decision Tree for Test Generation in Digital Circuits[C]. in Proc. of the International Test Conf., 1992, 816-825.
15. F. F. Seller, M. Y. Hsiao, L. W. Bearnson. Analysis Errors with the Boolean Difference[J]. IEEE Trans. On Computers., 1968, C-17(7):676-683.
16. S. T.Chakradha. Neural Network Models and Optimization Methods for Digital Testing [D]. Computer Science Department, Rutgers University,New Brunswick New Jersey, 1990.
17. S. T. Chakradhar, V. D. Agrawal, M. L. Bushnell. Neural Models and Algorithmsfor Digital Testing [M] .Boston, Kluwer Academic Publishers, 1991.
18. R. K. Gaede, M. R. Mercer, K. M. Butler, et al. CATAPULT: Concurrent Automatic Testing Allowing Parallelization and Using Limited Topology[C]. in Proc. Of the 25th Design Automation Conf., 1988, 597-600.
19. P. Muth. A Nine-Valued Circuit Model for Test Generation[J]. IEEE Trans.on Computers, 1976, C-25(6):630-636.
20. M. J. Marlett, J. A. Abraham. DCIATP- An Iterative Analog Circuit Test Generation Program for Generating DC Single Pattern Tests[C]. in Proc. of the International Test Conf., 1988, 839-844.
21. R.A. Marlett. EBT: A Comprehensive Test Generation Technique for Highly Sequential Circuits[C]. in Proc. of the 15th Design Automation Conf., 1978, 335-339.
22. W. T. Cheng. SPLIT Circuit Model for Test Generation[C]. in Proc. of the 25th Design Automation Conf., 1988, 96-101.
23. W. T. Cheng. The BACK Algorithm for Sequential Test Generation[C]. in Proc. of the International Conf. on Computer Design, 1988, 66-69.
24. W.T. Cheng, T. J. Chakraborty. Gentest: An Automatic Test Generation System for Sequential Circuits[J]. Computer, 1989, 22(4):43-49.
25. R. Bencivenga,T. J. Chakraborty, S. Davidson.The Architecture of the Gentest Sequential Test Generator[C]. in Proc. of the Custom Integrated Circuits Conf.,1991, 17.1.1-17.1.4.
26. V. D. Agrawal, K. T. Cheng, and P. Agrawal. A Directed Search Method for Test Generation using a Concurrent Simulator[J]. IEEE Trans. on Computer-Aided Design, 1989, 8(2):131-138.
27. K. T. Cheng, V. D. Agrawal. Unified Methods for VLSI Simulation and Test Generation[M]. Boston:Kluwer Academic Publishers, 1989.
28. T. M. Niermann, J. H. Patel. HITEC:A Test Generation Package for Sequential Circuits[C]. in Proc. of the European Design Automation Conf., 1991, 214-218.
29. F.Corno, P. Prinetto, M. Rebaudengo, et al. A Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits[J]. IEEE Trans.on Computer-Aided Design, 1996, 15(8):991-1000.
30. M. W. Moskewicz, C. F. Madigan, Y. Zhao, et al. Chaff: Engineering an efficient SAT solver[C]. In Proceedings Of the 38th Design Automation Conference (DAC), 2001, 530-535.
31. E. Goldberg, Y. Novikov. BerkMin: A fast and robust SAT-solver[C]. In Proceedings of Design Automation and Test in Europe (DATE), 2002,142-149.
32. N. Eén, N. S?rensson. An extensible SAT-solver. Theory and Applications of Satisfiability Testing [A]. In International Conf. on Theory and Applications of Satisfiability Testing, 2003, 3:502–518.
33. N. Een, N. S¨orensson. MiniSat v1.13 - A SAT Solver with Conflict-Clause Minimization[A], System description for the SAT competition. 2005, 61-75.
34.曾繁泰. EDA工程方法学[M].北京:清华大学出版社, 2003.
35.郭兵. SoC技术原理与应用[M].北京:清华大学出版社, 2006.
36. Benoit Nadeau-Dostie. Design for at-speed test, diagnosis, and measurement[M]. United States of America:Kluwer Academic Publishers, 2000.
37. J. M. Galey, R. E. Norby, J. P. Roth. Techniques for the Diagnosis of Switching Circuit Failures[C]. in Proc. of the Second Annual Symp. on Switching Circuit Theory and Logical Design, (Detroit), AIEE, 1961, 152-160.
38. S. Seshu, D. N. Freeman. The Diagnosis of Asynchronous Sequential Switching Systems[J]. IRE Trans. on Electronic Computers, 1962, EC-11(13): 459-465.
39. J. F. Poage. Derivation of Optimum Tests to Detect Faults in Combinational Circuits[C]. in Proc.of the Symp.on Mathematical Theory of Automata, 1962, 483-528.
40. V. K. Agrawal, A. F. S. Fung. Multiple Fault Testing of Large Circuits by Single Fault Test Sets[J]. IEEE Trans. on Computers, 1981, C-30( 11):855-865.
41. J. L. A. Hughes, E. J. McClusky. Multiple Stuck-at Fault Coverage of Single Stuck-at Fault Test Sets[C]. in Proc. of the International Test Conf., 1986, 168-174.
42. M. Abramovici, M. A. Breuer, A. D. Friedman. Digital Systems Testing and Testable Design[M]. New York :Computer Science Press, 1990.
43. V. S. Iyengar, B. K. Rosen, J. A. Waicukauski. On Computing the Sizes of Detected Delay Faults[J]. IEEE Trans.on Computer-Aided Design, 1990, 9(3):200-312.
44. A. K. Majhi, J. Jacob, L. M. Patnaik, et al. On Test Coverage of Path Delay Faults[C]. in Proc. of the 9th International Conf. on VLSI Design, 1996, 418-421.
45. C. J. Lin, S. M. Reddy. On Delay Fault Testing in Logic Circuits[J]. IEEE Trans.on Computer-Aided Design, 1987, CAD-6(5):694-703.
46. A. Krstic, K. T. Cheng. Delay Fault Testing for VLSI Circuits[M]. Boston:Kluwer Academic Publishers, 1998.
47. A. D. Friedman. Fault detection in redundant circuits[J]. IEEE Trans. on Electronic Computers, 1967, 16:99-100.
48. S. Kajihara, H. Shiba, K. Kinoshita. Removal of Redundancy in Logic Circuits under Classification of Undetectable Faults[C]. in Proc. FTCS, 1992, 263-270.
49. S. J. Chang, M. A. Breuer. A Fault-Collapsing Analysis in Sequential Logic Networks[J]. Bell System Technical Journal, 1981, 6(9):2259-2271.
50. J. E. Chen, C. L. Lee, W. Z. Shen. Single-Fault Fault-Collapsing Analysis in Sequential Logic Circuits[J]. IEEE Trans.on Computer-Aided Design, 1991, 10(12):1159-1568.
51.沈海华,卫文丽,陈云霁.覆盖率驱动的随机测试生成技术综述[J].计算机辅助设计与图形学学报, 2009, 21(4):419-431.
52.张建胜,黄维康,唐璞山.变长重复播种测试码生成方法[J].复旦学报(自然科学版) 2006, 45(4):517-522.
53. S. Pateras, J. Rajski. Cube-Contained Random Patterns and their Application to the Complete Testing of Synthesized Multi-Level Circuits[C]. Proc. of Int. Test Conf., 1991, 473-482.
54. I. Pomeranz, S. M. Reddy. 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits[J]. IEEE Trans. on Computer-Aided Design, 1993, 12(7):1050-1058.
55. C. Dufaza, H. Viallon, C. Chevalier. BIST Hardware Generator for Mixed Test Scheme[C]. Proc. IEEE European Design and Test Conf., 1995, 424-430.
56. L. Li, Y. Min. An Efficient BIST Design Using LFSR-ROM Architecture[C]. in Proc.
9th Asian Test Symp., 2000, 386-390.
57. F. F. Sellers, M. Y. Hsiao, L. W. Bearnson. Analyzing errors with the Boolean difference[J]. IEEE Trans. Comput., 1968, 17(7): 676-683.
58. F. F. Sellers, M. Y. Hsiao, and L. W. Bearnson. Error Detecting Logic for Digital Computers[M]. New York:McGraw-Hill,1968.
59.吴丽华,李涛,邹海英等.多故障测试生成的一种简化算法[J].电机与控制学报, 2008, 12(3):348-352.
60. A. Thayse, M. Davio. Boolean differential calculus and its application to switching theory[J]. IEEE Trans. Computers,1973, 22 (4): 409-420.
61. H. R. Andersen, H. Hulgaard. Boolean Expression Diagrams[C]. 12th Annual IEEE Symposium on Logic in Computer Science, 1997, 88~98.
62.魏道政.产生功能级数字电路测试码的一种算法一主路径敏化法[J].计算机学报, 1982, 2:125-139
63. S. A. Cook. The Complexity of Theorem proving Procedures[C]. in Proceeding of Annual ACM Symposium Theory Computing, 1971, 151-158.
64. M. Davis, G.Longemann, D. Loveland. A Machine program for theorem proving[J]. Communications of the ACM, 1962, 5(7):394-397.
65. M. Davis, H. Putnam. A Computing Procedure for Quantification Theory[J]. Journal of ACM, 1960, 7(3):201-215.
66.邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社, 2005.
67.刘晓东.数字集成电路测试生成算法研究[D]:[博士学位论文].哈尔滨理工大学, 2003年.
68.袁晓辉,袁艳斌,王乘等.一种新型的自适应混沌遗传算法[J].电子学报, 2006, 34(4):708-711.
69. J. T. Tsai, T. K. Liu and J. H. Chou. Hybrid Taguchi-genetic algorithm for global numerical optimization [J]. IEEE Trans. Evol. Comput., 2004, 8(4):365-377.
70.陈小平.于盛林.实数遗传算法交叉策略的改进[J].电子学报, 2003, 31(1):71-74.
71. R. Krishnamoorthi, S. A. Sahaaya, A. Mary Regression Test Suite Prioritization Using Genetic Algorithms[J]. International Journal of Hybrid Information Technology, 2009, 12(3):35-52.
72. M. A. Ahmed, I. Hermadi. GA-based multiple paths test data generator[J]. Computers and Operations Research, 2008, 35(10):3107-3124.
73.巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报, 2010, 38(6):1-7.
74. E. M. Rudnick, J. G. Holm, D. G. Saab, et al. Application of Simple Genetic Algorithms to Sequential Circuit Test Generation[C]. Proc. European Design & Test Conf., 1994, 40-45.
75. P. Prinetto, M. Rebaudengo, M. Sonza Reorda, et al. GATTO: an Intelligent Tool for Automatic Test Pattern Generation for Digital Circuits [C]. Proceedings of Int. Conference on Tools with Artificial Intelligence, 1994, 441-417.
76. E. M. Rudnick, J. H. Patel, G. S. Greenstein, et al. A genetic algorithm framework for test generation[J]. IEEE Tran. Computer-Aided Design, 1997, 16(9): 1034-1044.
77. B. F. Jones, D. E. Eyres, H. H. Sthamer. A Strategy for using Genetic Algorithms to Automate Branch and Fault-based Testing[J]. The Computer Journal, 1998, 41( 2):98-107.
78. M. S. Hsiao, E. M. Rudnick, J. H. Patel. Application of Genetically-Engineered Finite-State-Machine Sequences to Sequential Circuit ATPG[J]. IEEE Trans. on Computer-Aided Design, 1998, 17(3): 239-254.
79. R. Pargas, M. Harrold, R. Peck. Test-data generation using genetic algorithms[J]. Software Testing, Verification and Reliability, 1999, 9(4):263-282.
80. M. Keim, N. Drechsler, B. Becker. Combining GAs and symbolic methods for high quality tests of sequential circuits[J]. Journal of Electronic Testing, 1999, 17(1)37-51.
81. Research in VLSI Circuit Testing, Verification, and Diagnosis[EB/OL] http://www.crhc.illinois.edu/IGATE/, 2000.
82. M. Dorigo, V. M. Aniezzo, A .Colornt. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Trans. on Systems, Man, and Cybernetics Part B, 1996, 26(1):29-41.
83. J. L. Pan, X. H. Ye, Q. Xue. A new method for sequential fault diagnosis based on ant algorithm[C]. Second International Symposium on Computational Intelligence and Design, 2009, 44-48.
84.许川佩,李智,莫玮.基于蚂蚁算法和遗传算法的时序电路测试生成[J].电子与信息学报, 2005, 27(7):1157-1161.
85. X. Zhou, X. L. Wang. The study on the test generation of digital circuit on the basis of the GA and the ant colony algorithm[C]. Mechanic Automation and Control Engineering (MACE), 2011 Second International Conference on, 2011, 4627– 4629.
86.徐建斌,李智.神经网络在组合电路故障模拟测试生成算法中的应用[J].电路与系统学报, 2001, 6(4):256-257.
87. S. T. Chakradhar, V. D. Agrawal, and M. L. Bushnell. Toward Massively Parallel Automatic Test Generation[J]. IEEE Trans, on Computer-Aided Design, 1990,
9(9):981-994
88. M. Fayyazi, Z. Navabi. Using VHDL Model for Automatic TestGeneration[A]. Spain IEEE Symposium on Hardware Modeling 1997.
89.张立明.人工神经网络的模型及应用[M].上海:复旦大学出版社, 2000.
90.杨行峻,郑君里.人工神经网路与盲信号处理[M].北京:清华大学出版社,2003.
91. H. Fujiwara. Three-valued neural networks for test generation[C]. Proc. of 20th Fault- Tolerant Computing Symposium, 1990, 66-67.
92. M. Arai, T. Nakagawa, H. Kitagawa. An approach to automatic test pattern generation using strictly digital neural networks[C]. IEEE Int. Joint conf. on Neural Networks, 1992, 4:474—479.
93.潘中良,陈翎.基于神经网络的电路多故障测试及并行实现[J].仪器仪表学报, 2002, 23(6):680-681.
94. T. Arslan, A. Al-Jumah. Compact artificial neural network approach for multiple fault location in digital circuits[J]. IEE Electronics Letters, 1997, 33(22):1801-1803.
95.吴丽华,王旭东,史芳芳等.遗传优化三值神经网络多故障测试生成算法[J].仪器仪表学报, 2010, 31(8):1744-1749.
96. T. Sorsa, H. N. Koivo, H. Koivisto. Neural networks in process fault diagnosis[J]. IEEE Systems, Man, and Cybernetics Society, 1991, 21( 4): 815–825.
97.田树新,孙胜春,王红霞.基于BP网络的数字电路多故障诊断研究[J].电子器件, 2006, 29 (2):490-492.
98. Y. G. He, Y. H. Tan, Y.Sun. A neural network approach for fault diagnosis of large-scale analog circuits[C]. Proc of Circuits and Systems. ISCAS 2002, 2002, 1:153 - 156.
99. L. F. Yuan, Y. G. He, J. Y. Huang, et al. A New Neural-Network-Based Fault Diagnosis Approach for Analog Circuits by Using Kurtosis and Entropy as a Preprocessor[J]. IEEE Tran. On Instrumentation and Measurement, 2010, 59(3):586-595.
100.杨维,李岐强.粒子群优化算法综述[J ].中国工程科学, 2004, 6 (5): 87-93.
101. J. Kennedy, R. C. Eberhart. Particle swarm optimization[C]. Proc. IEEE international conference on Neural Networks, 1995, 4:1942-1948.
102. J. Kennedy, R. C. Eberhart. A discrete binary version of the particle swarm algorithm[C]. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, 1997, 4104-4109.
103. C. A. C. Coello, M. S. Lechuga. MOPSO: a proposal for multiple objective particle swarm optimization[C]. in Proceedings of the 2002 Congress on Evolutionary Computation, 2002, 2:1051-1056.
104. F. van den Bergh, A. P. Engelbrecht. A cooperative approach to particle swarm optimization[J]. IEEE Trans. Evol Comput., 2004, 8(3):225-239.
105.李爱国.多粒子群协同优化方法[J ] .复旦学报(自然科学版) , 2004, 43(5):923-925.
106. M.Clerc, J.Kennedy. The particle swarm: explosion, stability, and convergence in a multi -dimensional complex space[J]. IEEE Trans. on Evol. Comput., 2002, 6(1):58-73.
107.孟红记,郑鹏,梅国辉等.基于混沌序列的粒子群优化算法[J].控制与决策, 2006, 21(3): 263-266.
108. J. Sun, B. Feng, W. B. Xu. Particle swarm optimization with particles having quantum behavior[C]. In Proceedings of congress on evolutionary computation, 2004, 325-331.
109.周雅兰,王甲海,印鉴.一种基于分布估计的离散粒子群优化算法[J].电子学报, 2008, 36(6):1242-1247.
110.许川佩.时序电路测试生成算法研究[D]:[博士学位论文].西安电子科技大学,2006.
111.蒋荣华,王厚军,龙兵.基于DPSO的改进AO*算法在大型复杂电子系统最优序贯测试中的应用[J].计算机学报, 2008, 31(10):1835-1840.
112.李爱国,张艳丽.基于PSO的软件结构测试数据自动生成方法[J].计算机工程, 2008, 34(8):93-94.
113.顾凡一,王友仁,黄三傲等.基于案例库推理法的模拟电路故障诊断技术研究[J].计算机测量与控制, 2005, 13(9):921-923.
114.周红,张胜,刘琳岚等.基于GA-PSO算法的路径测试数据自动生成[J].计算机应用研究2010, 27(4):1366-1369.
115.丁洁,王学伟.时序电路SACO和PSO混合算法的测试向量生成[J].北京化工大学学报(自然科学版), 2011, 38(5):120-124.
116. Engelbrecht A P,谭营(译).计算群体智能基础[M].北京:清华大学出版社, 2009.
117. M. Iyer, M. Abramovici. FIRE: A Fault Independent Combinational. Redundancy Identification Algorithm[J]. IEEE Trans. on VLSI Systems, 1996, 4 (2): 295-301.
118.曾芷德.一种基于动态可测性测度的快速识别逻辑冗余故障的方法—DRFM[J].计算机学报, 1991, 8:615-623.
119. S. Davidson. Is IDDQ yield loss inevitable?[C]. Proceedings of Int.Test, 1994, 572-579.
120. D. E. Long, M. A. Iyer, M. Abramovici. FILL and FUNI: Algorithms to Identify Illegal States and Sequentially Untestable Faults[J]. ACM TODAES, 2000, 5(3):631-657.
121. C. Yang, M. Ciesielski. BDS: A BDD-based Logic Optimization System[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 21(7): 866–876.
122. V. D. Agrawal, S. T. Chakradhar. Combinational ATPG Theorems for Identifying Untestable Faults in Sequential Circuits[J]. IEEE Trans. Computer-Aided Design, 1995, 14(9):1155-1160.
123. M. A. Iyer, M. .bramovici. Low Cost Redundancy Identification for Combinational Circuits[C]. Proceedings of the 7th IEEE VLSI Design, 1994, 315-318.
124. J. K. Zhao, E. M. Rudnick, J. H. Patel. Static logic implication with application to redundancy identification [C]. Proceedings of the15th IEEE VLSI Test, 1997, 288-293.
125. M. Syal, M. S. Hsiao. Untestable fault identificationusing recurrence relations and impossible value assignments[C]. Proc. of Int. VLSI Design, 2004, 481-486.
126. M. S. Hsiao. Maximizing Impossibilities for Untestable Fault Identification[C]. Proc. IEEE Design Automation and Test in Europe, 2002, 949-953.
127. J. Zhao, J. A. Newquist, J. Patel. A graph traversal based framework for sequential logic implication with an application to c-cycle redundancy identification[C]. Proc. VLSI Design, 2001, 163-169.
128. E. Gizdarski, H. Fujiwara. SPIRIT. A Highly Robust Combinational TestGeneration Algorithm[J]. IEEE Trans. Computers, 2002, 21(12):1446-1458.
129. M. R. Prasad, M. S. Hsiao, Jawahar Jain. Can SAT be used to Improve Sequential ATPG Methods[C]. Proceedings of the 17th IEEE VLSI Design, 2004, 585-590.
130. J. Kim, J. P. M. Silva, H. Savoj, et al. RID-GRASP: Redundancy identification and removal using grasp[C]. in Proceedings of the International Workshop on Logic Syn- thesis, 1997,131-134.
131. C. A. Wu, T. H. Lin, L. Huang. SAT- controlled redundancy addition and removal-a novel circuit estructuring technique[C]. In Proc. ASP-DAC, 2009, 191-196
132.俞龙江,彭喜源,彭宇.基于蚁群算法的测试集优化[J].电子学报, 2003, 31(8):1178-1181.
133. H. Fujiwara and S. Toda. The complexity of fault detection problems for combinational logic circuits[J] . IEEE Trans. Comput ., 1982, 31( 6):555-560.
134.杨士元.数字系统的故障诊断与可靠性设计[M].北京:清华大学出版社, 2000.
135. T. Y. Chen, M. F. Lau. Dividing strategies for the optimization of a test suite[J]. Information Processing Letters, 1996, 60(3):135-141.
136. T. Y. Chen, M. F. Lau. A new heuristic for test suite reduction[J]. Information and Software Technology, 1998, 40(5):347-354.
137. Y. Huang, W. B. Xu. A Multiobjective Heuristic for ICs Test Suite Reduction[C]. Proc. Of 2008 International Symposium on Distributed Computing and Applications for Business Engineering and Science, 2008, 2(2):1277-1281.
138. Radu Belea. Genetic algorithm convergence analysis using a unified representation of genes and the hamming distance[J]. International Journal of Knowledge based and Intelligent Engineering Systems, 2006, 10( 1): 29- 40.
139.乔家庆,付平,尹洪涛.基于遗传排序的测试集优化[J].电子学报, 2007, 36(12):2335-2338.
140. Bharti Suri. Implementing Ant Colony Optimization for Test Case Selection and Prioritization[J]. International Journal on Computer Science and Engineering, 2011, 3(5):1923-1932.
141.侯艳丽,赵春晖,胡佳伟.基于粒子群算法的故障测试集优化[J].电子测量与仪器学报, 2006, 22(4):21-25.
142.蒋荣华,王厚军,龙兵.基于离散粒子群算法的测试选择[J].电子测量与仪器学报, 2008, 22(2):11-15.
143.马飒飒,赵守伟,王光平.基于智能混合策略的测试集优化[J].测试技术学报, 2007, 21(4):307-312.
144.陈希祥,邱静,刘冠军.基于混合二进制粒子群-遗传算法的测试优化选择研究[J].仪器仪表学报, 2009, 30(8):1674-1680.
145.高燕.基于寄存器传输级层次模型的测试生成研究[D]:[博士学位论文].中国科学院计算技术研究所, 2003.
146.姚志江.异步时序电路测试生成研究[D]:[博士学位论文].中国科学院计算技术研究所, 2001.
147.刘歆.数字电路的故障测试模式生成方法研究[D]:[博士学位论文].华中科技大学, 2004.
148. J. Giraldi, M. L. Bushnell. EST: The New Frontier in Automatic Test Pattern Generation[C] Proceedings of the 27th ACM IEEE Design Automation Conference. Orlando, 1990, 667-672.
149. M. L. Bushnell, J. Giraldi. A Functional Decomposition Method for Redundancy Identification and Test Generation[J]. Journal of Electronic Testing: Theory and Applications, 1997, 10( 3):175-195.
150.刘晓东.数字集成电路测试生成算法研[D]:[博士学位论文].哈尔滨工业大学, 2003.
151. J. P. Marques-Silva, K. A. Sakallah. GRASP: A Search Algorithm for Propositional Satisability[J]. IEEE Transactions on Computers, 1999, 48(5):506-521.
152. G. R. Putzolu, J. P. Roth. A heuristic algorithm for the testing of asynchronous circuits[J]. IEEE Trans. Comput., 1971, C-20(7): 639-647.
153. H. Kubo. A Procedure for Generating Test Sequences to Detect Sequential circuit Failures[J]. NEC Res.& Dev, 1968, 12(4):69-78.
154. T. Kirkland, M. R. Mercer. A Topological Search Algorithm for ATPG[C]. in Proc. of the 24th Design Automation Conference, 1987, 502-508.
155. H. K. T. Ma, S. Devadas, A. R. Newton, et al. Test Generation for Sequential Circuits[J]. IEEE Trans. on Computer-Aided Design, 1988, 7(10):1081-1093.
156. A. Ghosh, S. Devadas, A. R. Newton. Sequential Logic Testing and Verication[M] Boston:Kluwer Academic Publishers, 1992.
157. W. T. Cheng, M. L. Yu. Differential fault simulation– a fast method using minimal memory[C]. Proc. Int. Conf. Computer-Aided Design, 1989, 424-428.
158. W. T. Cheng, J. H. Patel. PROOFS: A super fast fault simulation for sequential circuit test[C]. Proc. Euro. Design Automation Conf., 1990, 475-479.
159. T. M. Niermann, W. T. Cheng, J. H. Patel. PROOFS: A fast memory efficient sequential circuit fault simulator[J]. IEEE Trans. Computer-Aided Design, 1992, 11:198-207.
160. H. K. Lee, D. S. Ha. HOPE: An efficient parallel fault simulator for synchronous sequential circuits[J]. IEEE Trans. Computer-Aided Design, 1996, 15(9):1048–1058 .
161. Y. Takamatsu, K. Kinoshita. CONT: a concurrent test generation system[J]. IEEE Trans. on Computer-Aided Design, 1989, 8(9): 966-997.
162. U. Gl?ser, H. T. Vierhaus. Mixed Level Test Generation for Synchronous Sequential Circuits Using the FOGBUSTER Algorithm[J]. IEEE Trans. CAD, 1996, 15(4): 410-423.
163. Boolean satisfiability problem [EB/OL]. http://en.wikipedia.org/wiki/ Boolean_satisfiability_problem, 2012.
164. NTIME [EB/OL]. http://en.wikipedia.org/wiki/NTIME, 2011.
165. M. R. Garey, D. S. Johnson. Computers And Intractability A Guide To The Theory Of NP-Completeness[M]. San Francisco:W.H. Freeman, 1979.
166. Computer algebra system [EB/OL]. http://en.wikipedia.org/wiki/ Computer_algebra_system, 2011.
167. Berenard Kolman.离散数学结构(第四版影印版)[M].北京:高等教育出版社, 2001.
168.屈婉玲,耿素云,张立昂.离散数学(第三版)[M].北京:清华大学出版社, 2004.
169.焦加麟.一种高效、健壮的SAT程序与开发[D]:[硕士学位论文].上海交通大学, 2003.
170. The international SAT Competitions web page [EB/OL]. http://www.satcompetition.org/.
171. Detlovs, Vilnis, and Podnieks, Karlis.über die Vollst?ndigkeit des Logikkalküls[D]. University Of Vienna, 1929.
172.张效祥.计算机科学技术百科全书[M].北京:清华大学出版社, 2005.
173. J. P. Marques-Silva, K. A. Sakallah. GRASP-A New Search Algorithm for Satisfiability[C]. In Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, 1996, 220-227.
174.丁敏.可满足性问题算法研究以及在时序电路等价验证中的应用[D]:[博士学位论文].复旦大学, 2005.
175. P. Prosser. Hybrid Algorithms for the Constraint Satisfaction Problem[J]. Computational Intelligence, 1993, 9(3):268-299.
176. R. J. Bayardo, R. Schrag. Using CSP Look-Back Techniques to Solve Exceptionally Hard SAT Instances [C]. In Proc. Second Int. Conf. on Principles and Practice of Constraint Programming, 1996, 46-60.
177. R. J. Bayardo, R. C. Schrag. Using CSP Lookback Techniques to Solve Real-World SAT Instances[C]. In Proceedings of the Fourteenth National Conference on Articial Intelligence (AAAI-97), 1997, 203-208.
178. H. Zhang, M. E. Stickel. An Efficient Algorithm for Unit Propagation[C]. In Proceedings of the Fourth International Symposium on Articial Intelligence and Mathematics, 1996, 166-169.
179. H. Zhang. SATO: An Efficient Propositional Prover[C]. In Proceedings of the International Conference on Automated Deduction (CADE'97), 1997, 1249:272-275.
180.荆明娥,周电,唐璞山.启发式极性决策算法解SAT问题[J].中国科学E辑:信息科学, 2007, 37 (12): 1597-1606.
181. J. Kim, J. Whittemore, K. A. Sakallah. On Solving Stack-Based Incremental Satisfiability Problems[C]. In Proceedings of International Conference on Computer Design, 2000, 379-382,.
182. J. Whittemore, J. Kim, K. A. Sakallah. SATIRE: A New Incremental Satisability Engine[C]. In Proceedings of the 38th Design Automation Conference, 2001, 542-545.
183. B. Selman, H. Levesque, D. Mitchell. A New Method for Solving Hard Satisfiability Problems[C]. In Proceedings of the Tenth National Conference on Articial Intelligence (AAAI-92), 1992, 440-446.
184. B. Selman, H. A. Kautz, B. Cohen. Local Search Strategies for Satisfiabilty Testing[J]. DIMACS Series in Discrete mathematics and Theoretical Computer Science, 1993, 26:521-532.
185.赵宇.基于规划的密码协议自动化验证技术研究[D]:[硕士学位论文].中国人民解放军信息工程大学, 2007.
186. J. Gu. Local search for satisfiability(SAT)problem[J]. IEEE Trans. on Systems, Man and Cybemetics, 1993, 23(4):1108-1128.
187.黄文奇,金人超.求解SAT问题的拟物拟人算法—Solar[J].中国科学(E辑), 1997, 27(2):179-186.
188.梁东敏,吴晔,马绍汉.一个求解结构SAT问题的高效局部搜索算法[J].计算机学报, 1998, 21(增刊):92-97.
189.张德富,黄文奇,汪厚祥.求解SAT问题的拟人退火算法[J].计算机学报, 2002, 25(2):148-152.
190.凌应标,吴向军,姜云飞.基于子句权重学习的求解SAT问题的遗传算法[J].计算机学报, 2005, 28(9):1476-1481.
191. DPLL algorithm [EB/OL]. http://en.wikipedia.org/wiki/DPLL_algorithm, 2012.
192. H. Zhang, M. E. Stickel. Implementing the Davis- Putnam algorithm by tries[R]. Technical Report, University of Iowa ,1994.
193. H. Zhang, M. E. Stickel. Implementing the Davis-Putnam method[J]. Journal of Automated Resoning, 2000, 24(1-2):277-296.
194. T. Larrabee. Test pattern generation using Boolean satisfiability[J]. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 1992, 11(1): 4–15.
195. J. N. Hooker. Solving the Incremental Satisfiability Problem[J]. Journal of Logic Programming, 1993, 15(1-2):177-186.
196. J. Shi, G. Fey, R. Drechsler, et al. PASSAT: Efficient SAT-based test pattern generation for industrial circuits[J]. In Proc. IEEE Annu. Symp. VLSI, 2005, 212–217.
197. R.Drechsler, S.Eggersglü?, G.Fey, et al. On acceleration of SAT- Based ATPG for industrial designs[J]. IEEE Trans. on CAD of Integrated Circuits and Systems, 2008, 27(7):1329-1333.
198. D.Tille, S.Eggersglü?, R.Drechsler. Incremental Solving Techniques for SAT-based ATPG[J]. IEEE Trans. on CAD of Integrated Circuits and Systems, 2010, 29(7):1125-1130.
199. D. R. Schertz, G. Metze. A New Representation for Faults in Combinational Digital Circuits[J]. IEEE Trans. on Computers, 1972, 21( 6): 858-866.
200. Vincentelli, A. Wang. Multilevel Logic Minimization Using Implicit Don't Cares[J]. IEEE Trans. on Computer-Aided Design, 1988, 7(6): 723-740.
201. Nripendra N. Biswas, C. Srikanth, James Jacob. Cubical CAMP for minimization of Boolean functions[C]. Proceedings of the 9th IEEE VLSI Design, 1996, 264-269.
202. S. C. Chang, L. V. Ginneken, M. Marek-Sadowska. Circuit optimization by rewiring[J]. IEEE Transaction on Computers, 1999, 48( 9): 962-970.
203. H. Fujiwara, S. Toida. The complexity of fault detection problems forcombinational logic circuits[J]. IEEE Trans. Computers, 1982, C-31(7):555-560.
204. Y. K. Wang. Data Structures, Minimization and Complexity of Boolean Functions[D]. University of Saskatchewan Electronic Thesis ,1995.
205. G. R. Putzolu, J. P. Roth. A heuristic algorithm for the testing of asynchronous circuits[J]. IEEE Trans. Comput., 1971, C-20(7): 639-647.
206. M. J. Harrold, R. Gupta, M. L. Soffa. A methodology for controllingthe size of a test suite[J]. ACM Transactions on Software Engineeringand Methodology, 1993, 2(3):270-285.
207. I. Hamzaoglu, J. H. Patel. Test Set Compaction Algorithms for Combinational Circuits[J]. IEEE Trans. Computer-Aided Design, 2000, 19(8):957-963.
208. S. B. Akers, C. Joseph, B. Krishnamurthy. On the role of independent fault sets in the generation of minimal test sets[C]. In Proc. Int. Test Conf., 1987, 1100–1107.
209. K. Kinoshita, S. M. Reddy. Cost effective generation of minimal test sets for stuck-at faults in combinational logic circuits[J]. IEEE Trans. Computer-Aided Design, 1995, 14:1496–1504.
210. I. Pomeranz, L. Reddy, S. M. Reddy. Compactest: A method to generate compact test sets for combinational circuits[C]. In Proc. Int. Test Conf., 1991, 194–203.
211. G. J. Tromp. Minimal test sets for combinational circuits[C]. In Proc. Int. Test Conf., 1991, 204–209.
212. L. N. Reddy, I. Pomeranz, and S. M. Reddy. ROTCO: A reverse order test compaction technique[C]. In Proc. IEEE EURO-ASIC Conf., 1992, 189–194.
213. M. C. Hansen, J. P. Hayes. High-level test generation using physically- induced faults[C]. In Proc. IEEE VLSI Test Symp., 1995, 20–28.
214. S. Kajihara, I. Pomeranz, K. Kinoshita, et al. Cost effective generation of minimal test sets for stuck-at faults in combinational logic circuits[C]. In Proc. Design Automation Conf., 1993, 102–106.
215. V. Chvatal. A Greedy Heuristic for the Set-Covering Problem[J]. Mathematics of Operations Research, 1979, 4(3):233-235.
216. M. J. Harreld, R. Gupta, M. L. Sofia. A methodology for controlling the size of a test suite[J]. ACM Transactions on Software Engineering and Methodology, 1993, 2(3):270-285.
217. T. Y. Chen, M. F. Lau. A simulation study on some heuristics for test suite reduction[J]. Information and Software Technology, 1998, 40(13):777-787.
218.王小港.遗传算法在VLSI设计自动化中应用研究[D]:[博士学位论文].中国科学院上海冶金研究所, 2001.
2. M. L. Bushnell, V. D. Agrawal.超大规模集成电路测试—数字、存储器和混合信号系统[M].北京:电子工业出版社, 2005.
3.雷绍充,邵志标,梁峰.VLSI测试方法学和可测性设计[M].北京:电子工业出版社, 2005.
4. International technology oadmap for semiconductors 2009 edition test and test equipment [EB/OL]. http://www.itrs.net/Links/2009ITRS/2009Chapters_2009Tables/ 2009_Test.pdf, 2009.
5. B. Krishnamurthy, S. B. Akers. On the complexity of estimating the size of a test set[J]. IEEE Trans. Computers, 1984, C-33( 8): 750–753.
6. R. Eldred. Test Routines Based on Symbolic Logical Statements[J]. ACM Journal, 1958, 6(1):33–36.
7. J. P. Roth. Diagnosis of automata failures: A calculus and a method[J]. IBM J. Res. Develop., 1966 , 10(4):278-291.
8. J. P. Roth, W. G. Bouricius, P. R. Schneider. Programmed Algorithms to Compute Tests to Detect and Distinguish Between Failures in Logic Circuits[J]. IEEE Trans. on Electronic Computers, 1967, EC-16(5):567-580.
9. P. Goel. An Implicit Enumeration Algorithm to Generate Tests for Combinational Logic Circuits[J]. IEEE Trans. on Computers, 1981, C-30(3):215-222.
10. H. Fujiwara, T. Shimono. On the Acceleration of Test Generation Algorithms[J]. IEEE Trans. on Computers, 1983, C-32(12):1137-1144.
11. M. H. Schulz, E. Auth. Advanced Automatic Test Pattern Generation and Redundancy Identi_cation Techniques[C]. in Proc. of the International Fault-Tolerant Computing Symp., 1988, 30-35.
12. M. H. Schulz, E. Auth. Improved Deterministic Test Pattern Generation with Applications to Redundancy Identication [J]. IEEE Trans. on Computer-Aided Design, 1989, 8(7):811-816.
13. M. H. Schulz, E. Trischler, T. M. Serfert. SOCRATES: A Highly Effcient Automatic Test Pattern Generation System[J]. IEEE Trans. on Computer-Aided Design, 1988, CAD-7(1):126-137 .
14. W. Kunz, D. K. Pradhan. Recursive Learning: An Attractive Alternative to the Decision Tree for Test Generation in Digital Circuits[C]. in Proc. of the International Test Conf., 1992, 816-825.
15. F. F. Seller, M. Y. Hsiao, L. W. Bearnson. Analysis Errors with the Boolean Difference[J]. IEEE Trans. On Computers., 1968, C-17(7):676-683.
16. S. T.Chakradha. Neural Network Models and Optimization Methods for Digital Testing [D]. Computer Science Department, Rutgers University,New Brunswick New Jersey, 1990.
17. S. T. Chakradhar, V. D. Agrawal, M. L. Bushnell. Neural Models and Algorithmsfor Digital Testing [M] .Boston, Kluwer Academic Publishers, 1991.
18. R. K. Gaede, M. R. Mercer, K. M. Butler, et al. CATAPULT: Concurrent Automatic Testing Allowing Parallelization and Using Limited Topology[C]. in Proc. Of the 25th Design Automation Conf., 1988, 597-600.
19. P. Muth. A Nine-Valued Circuit Model for Test Generation[J]. IEEE Trans.on Computers, 1976, C-25(6):630-636.
20. M. J. Marlett, J. A. Abraham. DCIATP- An Iterative Analog Circuit Test Generation Program for Generating DC Single Pattern Tests[C]. in Proc. of the International Test Conf., 1988, 839-844.
21. R.A. Marlett. EBT: A Comprehensive Test Generation Technique for Highly Sequential Circuits[C]. in Proc. of the 15th Design Automation Conf., 1978, 335-339.
22. W. T. Cheng. SPLIT Circuit Model for Test Generation[C]. in Proc. of the 25th Design Automation Conf., 1988, 96-101.
23. W. T. Cheng. The BACK Algorithm for Sequential Test Generation[C]. in Proc. of the International Conf. on Computer Design, 1988, 66-69.
24. W.T. Cheng, T. J. Chakraborty. Gentest: An Automatic Test Generation System for Sequential Circuits[J]. Computer, 1989, 22(4):43-49.
25. R. Bencivenga,T. J. Chakraborty, S. Davidson.The Architecture of the Gentest Sequential Test Generator[C]. in Proc. of the Custom Integrated Circuits Conf.,1991, 17.1.1-17.1.4.
26. V. D. Agrawal, K. T. Cheng, and P. Agrawal. A Directed Search Method for Test Generation using a Concurrent Simulator[J]. IEEE Trans. on Computer-Aided Design, 1989, 8(2):131-138.
27. K. T. Cheng, V. D. Agrawal. Unified Methods for VLSI Simulation and Test Generation[M]. Boston:Kluwer Academic Publishers, 1989.
28. T. M. Niermann, J. H. Patel. HITEC:A Test Generation Package for Sequential Circuits[C]. in Proc. of the European Design Automation Conf., 1991, 214-218.
29. F.Corno, P. Prinetto, M. Rebaudengo, et al. A Genetic Algorithm for Automatic Test Pattern Generation for Large Synchronous Sequential Circuits[J]. IEEE Trans.on Computer-Aided Design, 1996, 15(8):991-1000.
30. M. W. Moskewicz, C. F. Madigan, Y. Zhao, et al. Chaff: Engineering an efficient SAT solver[C]. In Proceedings Of the 38th Design Automation Conference (DAC), 2001, 530-535.
31. E. Goldberg, Y. Novikov. BerkMin: A fast and robust SAT-solver[C]. In Proceedings of Design Automation and Test in Europe (DATE), 2002,142-149.
32. N. Eén, N. S?rensson. An extensible SAT-solver. Theory and Applications of Satisfiability Testing [A]. In International Conf. on Theory and Applications of Satisfiability Testing, 2003, 3:502–518.
33. N. Een, N. S¨orensson. MiniSat v1.13 - A SAT Solver with Conflict-Clause Minimization[A], System description for the SAT competition. 2005, 61-75.
34.曾繁泰. EDA工程方法学[M].北京:清华大学出版社, 2003.
35.郭兵. SoC技术原理与应用[M].北京:清华大学出版社, 2006.
36. Benoit Nadeau-Dostie. Design for at-speed test, diagnosis, and measurement[M]. United States of America:Kluwer Academic Publishers, 2000.
37. J. M. Galey, R. E. Norby, J. P. Roth. Techniques for the Diagnosis of Switching Circuit Failures[C]. in Proc. of the Second Annual Symp. on Switching Circuit Theory and Logical Design, (Detroit), AIEE, 1961, 152-160.
38. S. Seshu, D. N. Freeman. The Diagnosis of Asynchronous Sequential Switching Systems[J]. IRE Trans. on Electronic Computers, 1962, EC-11(13): 459-465.
39. J. F. Poage. Derivation of Optimum Tests to Detect Faults in Combinational Circuits[C]. in Proc.of the Symp.on Mathematical Theory of Automata, 1962, 483-528.
40. V. K. Agrawal, A. F. S. Fung. Multiple Fault Testing of Large Circuits by Single Fault Test Sets[J]. IEEE Trans. on Computers, 1981, C-30( 11):855-865.
41. J. L. A. Hughes, E. J. McClusky. Multiple Stuck-at Fault Coverage of Single Stuck-at Fault Test Sets[C]. in Proc. of the International Test Conf., 1986, 168-174.
42. M. Abramovici, M. A. Breuer, A. D. Friedman. Digital Systems Testing and Testable Design[M]. New York :Computer Science Press, 1990.
43. V. S. Iyengar, B. K. Rosen, J. A. Waicukauski. On Computing the Sizes of Detected Delay Faults[J]. IEEE Trans.on Computer-Aided Design, 1990, 9(3):200-312.
44. A. K. Majhi, J. Jacob, L. M. Patnaik, et al. On Test Coverage of Path Delay Faults[C]. in Proc. of the 9th International Conf. on VLSI Design, 1996, 418-421.
45. C. J. Lin, S. M. Reddy. On Delay Fault Testing in Logic Circuits[J]. IEEE Trans.on Computer-Aided Design, 1987, CAD-6(5):694-703.
46. A. Krstic, K. T. Cheng. Delay Fault Testing for VLSI Circuits[M]. Boston:Kluwer Academic Publishers, 1998.
47. A. D. Friedman. Fault detection in redundant circuits[J]. IEEE Trans. on Electronic Computers, 1967, 16:99-100.
48. S. Kajihara, H. Shiba, K. Kinoshita. Removal of Redundancy in Logic Circuits under Classification of Undetectable Faults[C]. in Proc. FTCS, 1992, 263-270.
49. S. J. Chang, M. A. Breuer. A Fault-Collapsing Analysis in Sequential Logic Networks[J]. Bell System Technical Journal, 1981, 6(9):2259-2271.
50. J. E. Chen, C. L. Lee, W. Z. Shen. Single-Fault Fault-Collapsing Analysis in Sequential Logic Circuits[J]. IEEE Trans.on Computer-Aided Design, 1991, 10(12):1159-1568.
51.沈海华,卫文丽,陈云霁.覆盖率驱动的随机测试生成技术综述[J].计算机辅助设计与图形学学报, 2009, 21(4):419-431.
52.张建胜,黄维康,唐璞山.变长重复播种测试码生成方法[J].复旦学报(自然科学版) 2006, 45(4):517-522.
53. S. Pateras, J. Rajski. Cube-Contained Random Patterns and their Application to the Complete Testing of Synthesized Multi-Level Circuits[C]. Proc. of Int. Test Conf., 1991, 473-482.
54. I. Pomeranz, S. M. Reddy. 3-Weight Pseudo-Random Test Generation Based on a Deterministic Test Set for Combinational and Sequential Circuits[J]. IEEE Trans. on Computer-Aided Design, 1993, 12(7):1050-1058.
55. C. Dufaza, H. Viallon, C. Chevalier. BIST Hardware Generator for Mixed Test Scheme[C]. Proc. IEEE European Design and Test Conf., 1995, 424-430.
56. L. Li, Y. Min. An Efficient BIST Design Using LFSR-ROM Architecture[C]. in Proc.
9th Asian Test Symp., 2000, 386-390.
57. F. F. Sellers, M. Y. Hsiao, L. W. Bearnson. Analyzing errors with the Boolean difference[J]. IEEE Trans. Comput., 1968, 17(7): 676-683.
58. F. F. Sellers, M. Y. Hsiao, and L. W. Bearnson. Error Detecting Logic for Digital Computers[M]. New York:McGraw-Hill,1968.
59.吴丽华,李涛,邹海英等.多故障测试生成的一种简化算法[J].电机与控制学报, 2008, 12(3):348-352.
60. A. Thayse, M. Davio. Boolean differential calculus and its application to switching theory[J]. IEEE Trans. Computers,1973, 22 (4): 409-420.
61. H. R. Andersen, H. Hulgaard. Boolean Expression Diagrams[C]. 12th Annual IEEE Symposium on Logic in Computer Science, 1997, 88~98.
62.魏道政.产生功能级数字电路测试码的一种算法一主路径敏化法[J].计算机学报, 1982, 2:125-139
63. S. A. Cook. The Complexity of Theorem proving Procedures[C]. in Proceeding of Annual ACM Symposium Theory Computing, 1971, 151-158.
64. M. Davis, G.Longemann, D. Loveland. A Machine program for theorem proving[J]. Communications of the ACM, 1962, 5(7):394-397.
65. M. Davis, H. Putnam. A Computing Procedure for Quantification Theory[J]. Journal of ACM, 1960, 7(3):201-215.
66.邢文训,谢金星.现代优化计算方法[M].北京:清华大学出版社, 2005.
67.刘晓东.数字集成电路测试生成算法研究[D]:[博士学位论文].哈尔滨理工大学, 2003年.
68.袁晓辉,袁艳斌,王乘等.一种新型的自适应混沌遗传算法[J].电子学报, 2006, 34(4):708-711.
69. J. T. Tsai, T. K. Liu and J. H. Chou. Hybrid Taguchi-genetic algorithm for global numerical optimization [J]. IEEE Trans. Evol. Comput., 2004, 8(4):365-377.
70.陈小平.于盛林.实数遗传算法交叉策略的改进[J].电子学报, 2003, 31(1):71-74.
71. R. Krishnamoorthi, S. A. Sahaaya, A. Mary Regression Test Suite Prioritization Using Genetic Algorithms[J]. International Journal of Hybrid Information Technology, 2009, 12(3):35-52.
72. M. A. Ahmed, I. Hermadi. GA-based multiple paths test data generator[J]. Computers and Operations Research, 2008, 35(10):3107-3124.
73.巩敦卫,张岩.一种新的多路径覆盖测试数据进化生成方法[J].电子学报, 2010, 38(6):1-7.
74. E. M. Rudnick, J. G. Holm, D. G. Saab, et al. Application of Simple Genetic Algorithms to Sequential Circuit Test Generation[C]. Proc. European Design & Test Conf., 1994, 40-45.
75. P. Prinetto, M. Rebaudengo, M. Sonza Reorda, et al. GATTO: an Intelligent Tool for Automatic Test Pattern Generation for Digital Circuits [C]. Proceedings of Int. Conference on Tools with Artificial Intelligence, 1994, 441-417.
76. E. M. Rudnick, J. H. Patel, G. S. Greenstein, et al. A genetic algorithm framework for test generation[J]. IEEE Tran. Computer-Aided Design, 1997, 16(9): 1034-1044.
77. B. F. Jones, D. E. Eyres, H. H. Sthamer. A Strategy for using Genetic Algorithms to Automate Branch and Fault-based Testing[J]. The Computer Journal, 1998, 41( 2):98-107.
78. M. S. Hsiao, E. M. Rudnick, J. H. Patel. Application of Genetically-Engineered Finite-State-Machine Sequences to Sequential Circuit ATPG[J]. IEEE Trans. on Computer-Aided Design, 1998, 17(3): 239-254.
79. R. Pargas, M. Harrold, R. Peck. Test-data generation using genetic algorithms[J]. Software Testing, Verification and Reliability, 1999, 9(4):263-282.
80. M. Keim, N. Drechsler, B. Becker. Combining GAs and symbolic methods for high quality tests of sequential circuits[J]. Journal of Electronic Testing, 1999, 17(1)37-51.
81. Research in VLSI Circuit Testing, Verification, and Diagnosis[EB/OL] http://www.crhc.illinois.edu/IGATE/, 2000.
82. M. Dorigo, V. M. Aniezzo, A .Colornt. Ant system:Optimization by a colony of cooperating agents[J]. IEEE Trans. on Systems, Man, and Cybernetics Part B, 1996, 26(1):29-41.
83. J. L. Pan, X. H. Ye, Q. Xue. A new method for sequential fault diagnosis based on ant algorithm[C]. Second International Symposium on Computational Intelligence and Design, 2009, 44-48.
84.许川佩,李智,莫玮.基于蚂蚁算法和遗传算法的时序电路测试生成[J].电子与信息学报, 2005, 27(7):1157-1161.
85. X. Zhou, X. L. Wang. The study on the test generation of digital circuit on the basis of the GA and the ant colony algorithm[C]. Mechanic Automation and Control Engineering (MACE), 2011 Second International Conference on, 2011, 4627– 4629.
86.徐建斌,李智.神经网络在组合电路故障模拟测试生成算法中的应用[J].电路与系统学报, 2001, 6(4):256-257.
87. S. T. Chakradhar, V. D. Agrawal, and M. L. Bushnell. Toward Massively Parallel Automatic Test Generation[J]. IEEE Trans, on Computer-Aided Design, 1990,
9(9):981-994
88. M. Fayyazi, Z. Navabi. Using VHDL Model for Automatic TestGeneration[A]. Spain IEEE Symposium on Hardware Modeling 1997.
89.张立明.人工神经网络的模型及应用[M].上海:复旦大学出版社, 2000.
90.杨行峻,郑君里.人工神经网路与盲信号处理[M].北京:清华大学出版社,2003.
91. H. Fujiwara. Three-valued neural networks for test generation[C]. Proc. of 20th Fault- Tolerant Computing Symposium, 1990, 66-67.
92. M. Arai, T. Nakagawa, H. Kitagawa. An approach to automatic test pattern generation using strictly digital neural networks[C]. IEEE Int. Joint conf. on Neural Networks, 1992, 4:474—479.
93.潘中良,陈翎.基于神经网络的电路多故障测试及并行实现[J].仪器仪表学报, 2002, 23(6):680-681.
94. T. Arslan, A. Al-Jumah. Compact artificial neural network approach for multiple fault location in digital circuits[J]. IEE Electronics Letters, 1997, 33(22):1801-1803.
95.吴丽华,王旭东,史芳芳等.遗传优化三值神经网络多故障测试生成算法[J].仪器仪表学报, 2010, 31(8):1744-1749.
96. T. Sorsa, H. N. Koivo, H. Koivisto. Neural networks in process fault diagnosis[J]. IEEE Systems, Man, and Cybernetics Society, 1991, 21( 4): 815–825.
97.田树新,孙胜春,王红霞.基于BP网络的数字电路多故障诊断研究[J].电子器件, 2006, 29 (2):490-492.
98. Y. G. He, Y. H. Tan, Y.Sun. A neural network approach for fault diagnosis of large-scale analog circuits[C]. Proc of Circuits and Systems. ISCAS 2002, 2002, 1:153 - 156.
99. L. F. Yuan, Y. G. He, J. Y. Huang, et al. A New Neural-Network-Based Fault Diagnosis Approach for Analog Circuits by Using Kurtosis and Entropy as a Preprocessor[J]. IEEE Tran. On Instrumentation and Measurement, 2010, 59(3):586-595.
100.杨维,李岐强.粒子群优化算法综述[J ].中国工程科学, 2004, 6 (5): 87-93.
101. J. Kennedy, R. C. Eberhart. Particle swarm optimization[C]. Proc. IEEE international conference on Neural Networks, 1995, 4:1942-1948.
102. J. Kennedy, R. C. Eberhart. A discrete binary version of the particle swarm algorithm[C]. Proceedings of the World Multiconference on Systemics, Cybernetics and Informatics, 1997, 4104-4109.
103. C. A. C. Coello, M. S. Lechuga. MOPSO: a proposal for multiple objective particle swarm optimization[C]. in Proceedings of the 2002 Congress on Evolutionary Computation, 2002, 2:1051-1056.
104. F. van den Bergh, A. P. Engelbrecht. A cooperative approach to particle swarm optimization[J]. IEEE Trans. Evol Comput., 2004, 8(3):225-239.
105.李爱国.多粒子群协同优化方法[J ] .复旦学报(自然科学版) , 2004, 43(5):923-925.
106. M.Clerc, J.Kennedy. The particle swarm: explosion, stability, and convergence in a multi -dimensional complex space[J]. IEEE Trans. on Evol. Comput., 2002, 6(1):58-73.
107.孟红记,郑鹏,梅国辉等.基于混沌序列的粒子群优化算法[J].控制与决策, 2006, 21(3): 263-266.
108. J. Sun, B. Feng, W. B. Xu. Particle swarm optimization with particles having quantum behavior[C]. In Proceedings of congress on evolutionary computation, 2004, 325-331.
109.周雅兰,王甲海,印鉴.一种基于分布估计的离散粒子群优化算法[J].电子学报, 2008, 36(6):1242-1247.
110.许川佩.时序电路测试生成算法研究[D]:[博士学位论文].西安电子科技大学,2006.
111.蒋荣华,王厚军,龙兵.基于DPSO的改进AO*算法在大型复杂电子系统最优序贯测试中的应用[J].计算机学报, 2008, 31(10):1835-1840.
112.李爱国,张艳丽.基于PSO的软件结构测试数据自动生成方法[J].计算机工程, 2008, 34(8):93-94.
113.顾凡一,王友仁,黄三傲等.基于案例库推理法的模拟电路故障诊断技术研究[J].计算机测量与控制, 2005, 13(9):921-923.
114.周红,张胜,刘琳岚等.基于GA-PSO算法的路径测试数据自动生成[J].计算机应用研究2010, 27(4):1366-1369.
115.丁洁,王学伟.时序电路SACO和PSO混合算法的测试向量生成[J].北京化工大学学报(自然科学版), 2011, 38(5):120-124.
116. Engelbrecht A P,谭营(译).计算群体智能基础[M].北京:清华大学出版社, 2009.
117. M. Iyer, M. Abramovici. FIRE: A Fault Independent Combinational. Redundancy Identification Algorithm[J]. IEEE Trans. on VLSI Systems, 1996, 4 (2): 295-301.
118.曾芷德.一种基于动态可测性测度的快速识别逻辑冗余故障的方法—DRFM[J].计算机学报, 1991, 8:615-623.
119. S. Davidson. Is IDDQ yield loss inevitable?[C]. Proceedings of Int.Test, 1994, 572-579.
120. D. E. Long, M. A. Iyer, M. Abramovici. FILL and FUNI: Algorithms to Identify Illegal States and Sequentially Untestable Faults[J]. ACM TODAES, 2000, 5(3):631-657.
121. C. Yang, M. Ciesielski. BDS: A BDD-based Logic Optimization System[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2002, 21(7): 866–876.
122. V. D. Agrawal, S. T. Chakradhar. Combinational ATPG Theorems for Identifying Untestable Faults in Sequential Circuits[J]. IEEE Trans. Computer-Aided Design, 1995, 14(9):1155-1160.
123. M. A. Iyer, M. .bramovici. Low Cost Redundancy Identification for Combinational Circuits[C]. Proceedings of the 7th IEEE VLSI Design, 1994, 315-318.
124. J. K. Zhao, E. M. Rudnick, J. H. Patel. Static logic implication with application to redundancy identification [C]. Proceedings of the15th IEEE VLSI Test, 1997, 288-293.
125. M. Syal, M. S. Hsiao. Untestable fault identificationusing recurrence relations and impossible value assignments[C]. Proc. of Int. VLSI Design, 2004, 481-486.
126. M. S. Hsiao. Maximizing Impossibilities for Untestable Fault Identification[C]. Proc. IEEE Design Automation and Test in Europe, 2002, 949-953.
127. J. Zhao, J. A. Newquist, J. Patel. A graph traversal based framework for sequential logic implication with an application to c-cycle redundancy identification[C]. Proc. VLSI Design, 2001, 163-169.
128. E. Gizdarski, H. Fujiwara. SPIRIT. A Highly Robust Combinational TestGeneration Algorithm[J]. IEEE Trans. Computers, 2002, 21(12):1446-1458.
129. M. R. Prasad, M. S. Hsiao, Jawahar Jain. Can SAT be used to Improve Sequential ATPG Methods[C]. Proceedings of the 17th IEEE VLSI Design, 2004, 585-590.
130. J. Kim, J. P. M. Silva, H. Savoj, et al. RID-GRASP: Redundancy identification and removal using grasp[C]. in Proceedings of the International Workshop on Logic Syn- thesis, 1997,131-134.
131. C. A. Wu, T. H. Lin, L. Huang. SAT- controlled redundancy addition and removal-a novel circuit estructuring technique[C]. In Proc. ASP-DAC, 2009, 191-196
132.俞龙江,彭喜源,彭宇.基于蚁群算法的测试集优化[J].电子学报, 2003, 31(8):1178-1181.
133. H. Fujiwara and S. Toda. The complexity of fault detection problems for combinational logic circuits[J] . IEEE Trans. Comput ., 1982, 31( 6):555-560.
134.杨士元.数字系统的故障诊断与可靠性设计[M].北京:清华大学出版社, 2000.
135. T. Y. Chen, M. F. Lau. Dividing strategies for the optimization of a test suite[J]. Information Processing Letters, 1996, 60(3):135-141.
136. T. Y. Chen, M. F. Lau. A new heuristic for test suite reduction[J]. Information and Software Technology, 1998, 40(5):347-354.
137. Y. Huang, W. B. Xu. A Multiobjective Heuristic for ICs Test Suite Reduction[C]. Proc. Of 2008 International Symposium on Distributed Computing and Applications for Business Engineering and Science, 2008, 2(2):1277-1281.
138. Radu Belea. Genetic algorithm convergence analysis using a unified representation of genes and the hamming distance[J]. International Journal of Knowledge based and Intelligent Engineering Systems, 2006, 10( 1): 29- 40.
139.乔家庆,付平,尹洪涛.基于遗传排序的测试集优化[J].电子学报, 2007, 36(12):2335-2338.
140. Bharti Suri. Implementing Ant Colony Optimization for Test Case Selection and Prioritization[J]. International Journal on Computer Science and Engineering, 2011, 3(5):1923-1932.
141.侯艳丽,赵春晖,胡佳伟.基于粒子群算法的故障测试集优化[J].电子测量与仪器学报, 2006, 22(4):21-25.
142.蒋荣华,王厚军,龙兵.基于离散粒子群算法的测试选择[J].电子测量与仪器学报, 2008, 22(2):11-15.
143.马飒飒,赵守伟,王光平.基于智能混合策略的测试集优化[J].测试技术学报, 2007, 21(4):307-312.
144.陈希祥,邱静,刘冠军.基于混合二进制粒子群-遗传算法的测试优化选择研究[J].仪器仪表学报, 2009, 30(8):1674-1680.
145.高燕.基于寄存器传输级层次模型的测试生成研究[D]:[博士学位论文].中国科学院计算技术研究所, 2003.
146.姚志江.异步时序电路测试生成研究[D]:[博士学位论文].中国科学院计算技术研究所, 2001.
147.刘歆.数字电路的故障测试模式生成方法研究[D]:[博士学位论文].华中科技大学, 2004.
148. J. Giraldi, M. L. Bushnell. EST: The New Frontier in Automatic Test Pattern Generation[C] Proceedings of the 27th ACM IEEE Design Automation Conference. Orlando, 1990, 667-672.
149. M. L. Bushnell, J. Giraldi. A Functional Decomposition Method for Redundancy Identification and Test Generation[J]. Journal of Electronic Testing: Theory and Applications, 1997, 10( 3):175-195.
150.刘晓东.数字集成电路测试生成算法研[D]:[博士学位论文].哈尔滨工业大学, 2003.
151. J. P. Marques-Silva, K. A. Sakallah. GRASP: A Search Algorithm for Propositional Satisability[J]. IEEE Transactions on Computers, 1999, 48(5):506-521.
152. G. R. Putzolu, J. P. Roth. A heuristic algorithm for the testing of asynchronous circuits[J]. IEEE Trans. Comput., 1971, C-20(7): 639-647.
153. H. Kubo. A Procedure for Generating Test Sequences to Detect Sequential circuit Failures[J]. NEC Res.& Dev, 1968, 12(4):69-78.
154. T. Kirkland, M. R. Mercer. A Topological Search Algorithm for ATPG[C]. in Proc. of the 24th Design Automation Conference, 1987, 502-508.
155. H. K. T. Ma, S. Devadas, A. R. Newton, et al. Test Generation for Sequential Circuits[J]. IEEE Trans. on Computer-Aided Design, 1988, 7(10):1081-1093.
156. A. Ghosh, S. Devadas, A. R. Newton. Sequential Logic Testing and Verication[M] Boston:Kluwer Academic Publishers, 1992.
157. W. T. Cheng, M. L. Yu. Differential fault simulation– a fast method using minimal memory[C]. Proc. Int. Conf. Computer-Aided Design, 1989, 424-428.
158. W. T. Cheng, J. H. Patel. PROOFS: A super fast fault simulation for sequential circuit test[C]. Proc. Euro. Design Automation Conf., 1990, 475-479.
159. T. M. Niermann, W. T. Cheng, J. H. Patel. PROOFS: A fast memory efficient sequential circuit fault simulator[J]. IEEE Trans. Computer-Aided Design, 1992, 11:198-207.
160. H. K. Lee, D. S. Ha. HOPE: An efficient parallel fault simulator for synchronous sequential circuits[J]. IEEE Trans. Computer-Aided Design, 1996, 15(9):1048–1058 .
161. Y. Takamatsu, K. Kinoshita. CONT: a concurrent test generation system[J]. IEEE Trans. on Computer-Aided Design, 1989, 8(9): 966-997.
162. U. Gl?ser, H. T. Vierhaus. Mixed Level Test Generation for Synchronous Sequential Circuits Using the FOGBUSTER Algorithm[J]. IEEE Trans. CAD, 1996, 15(4): 410-423.
163. Boolean satisfiability problem [EB/OL]. http://en.wikipedia.org/wiki/ Boolean_satisfiability_problem, 2012.
164. NTIME [EB/OL]. http://en.wikipedia.org/wiki/NTIME, 2011.
165. M. R. Garey, D. S. Johnson. Computers And Intractability A Guide To The Theory Of NP-Completeness[M]. San Francisco:W.H. Freeman, 1979.
166. Computer algebra system [EB/OL]. http://en.wikipedia.org/wiki/ Computer_algebra_system, 2011.
167. Berenard Kolman.离散数学结构(第四版影印版)[M].北京:高等教育出版社, 2001.
168.屈婉玲,耿素云,张立昂.离散数学(第三版)[M].北京:清华大学出版社, 2004.
169.焦加麟.一种高效、健壮的SAT程序与开发[D]:[硕士学位论文].上海交通大学, 2003.
170. The international SAT Competitions web page [EB/OL]. http://www.satcompetition.org/.
171. Detlovs, Vilnis, and Podnieks, Karlis.über die Vollst?ndigkeit des Logikkalküls[D]. University Of Vienna, 1929.
172.张效祥.计算机科学技术百科全书[M].北京:清华大学出版社, 2005.
173. J. P. Marques-Silva, K. A. Sakallah. GRASP-A New Search Algorithm for Satisfiability[C]. In Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, 1996, 220-227.
174.丁敏.可满足性问题算法研究以及在时序电路等价验证中的应用[D]:[博士学位论文].复旦大学, 2005.
175. P. Prosser. Hybrid Algorithms for the Constraint Satisfaction Problem[J]. Computational Intelligence, 1993, 9(3):268-299.
176. R. J. Bayardo, R. Schrag. Using CSP Look-Back Techniques to Solve Exceptionally Hard SAT Instances [C]. In Proc. Second Int. Conf. on Principles and Practice of Constraint Programming, 1996, 46-60.
177. R. J. Bayardo, R. C. Schrag. Using CSP Lookback Techniques to Solve Real-World SAT Instances[C]. In Proceedings of the Fourteenth National Conference on Articial Intelligence (AAAI-97), 1997, 203-208.
178. H. Zhang, M. E. Stickel. An Efficient Algorithm for Unit Propagation[C]. In Proceedings of the Fourth International Symposium on Articial Intelligence and Mathematics, 1996, 166-169.
179. H. Zhang. SATO: An Efficient Propositional Prover[C]. In Proceedings of the International Conference on Automated Deduction (CADE'97), 1997, 1249:272-275.
180.荆明娥,周电,唐璞山.启发式极性决策算法解SAT问题[J].中国科学E辑:信息科学, 2007, 37 (12): 1597-1606.
181. J. Kim, J. Whittemore, K. A. Sakallah. On Solving Stack-Based Incremental Satisfiability Problems[C]. In Proceedings of International Conference on Computer Design, 2000, 379-382,.
182. J. Whittemore, J. Kim, K. A. Sakallah. SATIRE: A New Incremental Satisability Engine[C]. In Proceedings of the 38th Design Automation Conference, 2001, 542-545.
183. B. Selman, H. Levesque, D. Mitchell. A New Method for Solving Hard Satisfiability Problems[C]. In Proceedings of the Tenth National Conference on Articial Intelligence (AAAI-92), 1992, 440-446.
184. B. Selman, H. A. Kautz, B. Cohen. Local Search Strategies for Satisfiabilty Testing[J]. DIMACS Series in Discrete mathematics and Theoretical Computer Science, 1993, 26:521-532.
185.赵宇.基于规划的密码协议自动化验证技术研究[D]:[硕士学位论文].中国人民解放军信息工程大学, 2007.
186. J. Gu. Local search for satisfiability(SAT)problem[J]. IEEE Trans. on Systems, Man and Cybemetics, 1993, 23(4):1108-1128.
187.黄文奇,金人超.求解SAT问题的拟物拟人算法—Solar[J].中国科学(E辑), 1997, 27(2):179-186.
188.梁东敏,吴晔,马绍汉.一个求解结构SAT问题的高效局部搜索算法[J].计算机学报, 1998, 21(增刊):92-97.
189.张德富,黄文奇,汪厚祥.求解SAT问题的拟人退火算法[J].计算机学报, 2002, 25(2):148-152.
190.凌应标,吴向军,姜云飞.基于子句权重学习的求解SAT问题的遗传算法[J].计算机学报, 2005, 28(9):1476-1481.
191. DPLL algorithm [EB/OL]. http://en.wikipedia.org/wiki/DPLL_algorithm, 2012.
192. H. Zhang, M. E. Stickel. Implementing the Davis- Putnam algorithm by tries[R]. Technical Report, University of Iowa ,1994.
193. H. Zhang, M. E. Stickel. Implementing the Davis-Putnam method[J]. Journal of Automated Resoning, 2000, 24(1-2):277-296.
194. T. Larrabee. Test pattern generation using Boolean satisfiability[J]. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., 1992, 11(1): 4–15.
195. J. N. Hooker. Solving the Incremental Satisfiability Problem[J]. Journal of Logic Programming, 1993, 15(1-2):177-186.
196. J. Shi, G. Fey, R. Drechsler, et al. PASSAT: Efficient SAT-based test pattern generation for industrial circuits[J]. In Proc. IEEE Annu. Symp. VLSI, 2005, 212–217.
197. R.Drechsler, S.Eggersglü?, G.Fey, et al. On acceleration of SAT- Based ATPG for industrial designs[J]. IEEE Trans. on CAD of Integrated Circuits and Systems, 2008, 27(7):1329-1333.
198. D.Tille, S.Eggersglü?, R.Drechsler. Incremental Solving Techniques for SAT-based ATPG[J]. IEEE Trans. on CAD of Integrated Circuits and Systems, 2010, 29(7):1125-1130.
199. D. R. Schertz, G. Metze. A New Representation for Faults in Combinational Digital Circuits[J]. IEEE Trans. on Computers, 1972, 21( 6): 858-866.
200. Vincentelli, A. Wang. Multilevel Logic Minimization Using Implicit Don't Cares[J]. IEEE Trans. on Computer-Aided Design, 1988, 7(6): 723-740.
201. Nripendra N. Biswas, C. Srikanth, James Jacob. Cubical CAMP for minimization of Boolean functions[C]. Proceedings of the 9th IEEE VLSI Design, 1996, 264-269.
202. S. C. Chang, L. V. Ginneken, M. Marek-Sadowska. Circuit optimization by rewiring[J]. IEEE Transaction on Computers, 1999, 48( 9): 962-970.
203. H. Fujiwara, S. Toida. The complexity of fault detection problems forcombinational logic circuits[J]. IEEE Trans. Computers, 1982, C-31(7):555-560.
204. Y. K. Wang. Data Structures, Minimization and Complexity of Boolean Functions[D]. University of Saskatchewan Electronic Thesis ,1995.
205. G. R. Putzolu, J. P. Roth. A heuristic algorithm for the testing of asynchronous circuits[J]. IEEE Trans. Comput., 1971, C-20(7): 639-647.
206. M. J. Harrold, R. Gupta, M. L. Soffa. A methodology for controllingthe size of a test suite[J]. ACM Transactions on Software Engineeringand Methodology, 1993, 2(3):270-285.
207. I. Hamzaoglu, J. H. Patel. Test Set Compaction Algorithms for Combinational Circuits[J]. IEEE Trans. Computer-Aided Design, 2000, 19(8):957-963.
208. S. B. Akers, C. Joseph, B. Krishnamurthy. On the role of independent fault sets in the generation of minimal test sets[C]. In Proc. Int. Test Conf., 1987, 1100–1107.
209. K. Kinoshita, S. M. Reddy. Cost effective generation of minimal test sets for stuck-at faults in combinational logic circuits[J]. IEEE Trans. Computer-Aided Design, 1995, 14:1496–1504.
210. I. Pomeranz, L. Reddy, S. M. Reddy. Compactest: A method to generate compact test sets for combinational circuits[C]. In Proc. Int. Test Conf., 1991, 194–203.
211. G. J. Tromp. Minimal test sets for combinational circuits[C]. In Proc. Int. Test Conf., 1991, 204–209.
212. L. N. Reddy, I. Pomeranz, and S. M. Reddy. ROTCO: A reverse order test compaction technique[C]. In Proc. IEEE EURO-ASIC Conf., 1992, 189–194.
213. M. C. Hansen, J. P. Hayes. High-level test generation using physically- induced faults[C]. In Proc. IEEE VLSI Test Symp., 1995, 20–28.
214. S. Kajihara, I. Pomeranz, K. Kinoshita, et al. Cost effective generation of minimal test sets for stuck-at faults in combinational logic circuits[C]. In Proc. Design Automation Conf., 1993, 102–106.
215. V. Chvatal. A Greedy Heuristic for the Set-Covering Problem[J]. Mathematics of Operations Research, 1979, 4(3):233-235.
216. M. J. Harreld, R. Gupta, M. L. Sofia. A methodology for controlling the size of a test suite[J]. ACM Transactions on Software Engineering and Methodology, 1993, 2(3):270-285.
217. T. Y. Chen, M. F. Lau. A simulation study on some heuristics for test suite reduction[J]. Information and Software Technology, 1998, 40(13):777-787.
218.王小港.遗传算法在VLSI设计自动化中应用研究[D]:[博士学位论文].中国科学院上海冶金研究所, 2001.