摘要
序贯测试问题是目前的一个研究热点。由于时间复杂度太高,传统的序贯测试算法对于测点数大于12的系统无能为力。为此,将序贯测试问题拆分为测点选择与序测试设计两个问题。测点选择问题用A*算法解决:运用M进制编码规则,首先给出了启发函数的计算方法,然后给出了能够得到所有最小测点集的改进的A*算法。序测试设计问题用AO*算法解决:对二值哈夫曼编码规则进行推广得到了多值编码规则,根据此规则给出了AO*算法启发函数的计算方法。提出的方法更符合可测性设计的设计流程,试验和复杂度分析表明该方法能显著降低传统方法的时间复杂度。
The test sequencing problem have raised a great deal of interest. Traditional test sequencing algorithms are impractical for large systems that contain more than 12 test points because of their high time complexity. Based on these considerations, the test sequencing problem is decomposed into test points selection problem and test sequence arrange problem. The test points selection problem is solved by A＊ algorithm. The method of calculating heuristic evaluation function is given by using an M-ary code rule first. Then, an improved heuristic graph search algorithm A＊ that can obtain all minimum test point sets is given. The test sequence arrange problem is solved by AO＊ algorithm. The heuristic evaluation function of AO＊ is given based on the generalization of Huffman coding. The given method is more fit for the process of DFT （design for test）. Experiment and time complexity analysis show that this new algorithm can decrease the time complexities dramatically.
出处
《系统工程与电子技术》
EI
CSCD
北大核心
2009年第9期2271-2275,共5页
Systems Engineering and Electronics
基金
国家自然科学基金(60772145)
国防基础科研计划基金(A1420061264)
高等学校博士学科点专项科研基金(20070614018)
电子科技大学青年基金重点项目资助课题
关键词
多值故障字典
测点选择
序贯测试问题
可测性设计
multivalued fault dictionary
test point selection
test sequencing problem
design for test
