多值故障字典的测点选择与序测试设计

Journal of Systems Engineering and Electronics ›› 2009, Vol. 31 ›› Issue (9): 2271-2275.

多值故障字典的测点选择与序测试设计

杨成林, 田书林, 龙兵

电子科技大学自动化工程学院, 四川, 成都, 610054

收稿日期:2008-09-10 修回日期:2008-11-10 出版日期:2009-09-20 发布日期:2010-01-03
作者简介:杨成林(1977- ),男,博士研究生,主要研究方向为混合电路故障诊断及可测性设计.E-mail:yangclin@yahoo.com.cn
基金资助:
国家自然科学基金(60772145);国防基础科研计划基金(A1420061264);高等学校博士学科点专项科研基金(20070614018);电子科技大学青年基金重点项目资助课题

Design of test points selection and test sequencing problem of multivalued fault dictionary

YANG Cheng-lin, TIAN Shu-lin, LONG Bing

Coll. of Automation Engineering, Univ. of Electronics Science and Technology of China, Chengdu 610054, China

Received:2008-09-10 Revised:2008-11-10 Online:2009-09-20 Published:2010-01-03

摘要/Abstract

摘要： 序贯测试问题是目前的一个研究热点。由于时间复杂度太高,传统的序贯测试算法对于测点数大于12的系统无能为力。为此,将序贯测试问题拆分为测点选择与序测试设计两个问题。测点选择问题用A^*算法解决:运用M进制编码规则,首先给出了启发函数的计算方法,然后给出了能够得到所有最小测点集的改进的A^*算法。序测试设计问题用AO^*算法解决:对二值哈夫曼编码规则进行推广得到了多值编码规则,根据此规则给出了AO^*算法启发函数的计算方法。提出的方法更符合可测性设计的设计流程,试验和复杂度分析表明该方法能显著降低传统方法的时间复杂度。

Abstract: 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.

中图分类号:

TN710

杨成林, 田书林, 龙兵. 多值故障字典的测点选择与序测试设计[J]. Journal of Systems Engineering and Electronics, 2009, 31(9): 2271-2275.

YANG Cheng-lin, TIAN Shu-lin, LONG Bing. Design of test points selection and test sequencing problem of multivalued fault dictionary[J]. Journal of Systems Engineering and Electronics, 2009, 31(9): 2271-2275.

参考文献

[1] Pattipati K R,Alexandridis M G.Application of heuristic search and information theory to sequential fault diagnosis[J].IEEE Trans.on System,Man,Cybernetics,1990,20(4):872-887.
[2] Martelli A,Montanari U.Optimizing decision trees through heuristically guided search[J].Communication of the ACM,1978,21(12):1025-1039.
[3] Raghavan V,Shakeri M,Pattipati K R.Test sequencing problems arising in test planning and design for testability[J].IEEE Trans.on System,Man,Cybernetics Part A:System,Humans,1999,29(2):153-163.
[4] Tu F,Pattipati K R.Rollout strategies for sequential fault diagnosis[J].IEEE Trans.on System,Man,Cybernetics Part A:System,Humans,2003,33(1):86-99.
[5] Kundakcioglu O Erhun,Ünl·uyurt T.Bottom-up construction of minimum-cost AND/OR trees for sequential fault diagnosis[J].IEEE Trans.on System,Man,Cybernetics Part At System,Humans,2007,37(5):621-628.
[6] Yang ChengLin,Tian ShuLin,Long Bing.Application of heuristic graph search to test points selection for analog fault dictionary techniques[J].IEEE Trans.on Instrumentation Measurement Magazine,2009,58(7):2145-2158.
[7] Starzyk J A,Liu Dong,Liu Zhihong,et al.Entropy-based optimum test nodes selection for analog fault dictionary techniques[J].IEEE Trans.on Instrumentation Measurement,2004,37(53):754 -761.
[8] Prasad V C,Babu N S C.Selection of test nodes for analog fault diagnosis in dictionary approach[J].IEEE Trans.on Instrumentation.Measurement.,2000,49:1289-1297.
[9] Yang Chenglin,Tian Shulin,Long Bing.Test points selection of integer-coded fault wise table[J].Journal of Electronic Testing:Theory and Application,2009,25(2):157-168.
[10] 尼尔森N J.人工智能原理[M].郑扣根,译.1版.北京:机械工业出版社,2003:86-91.
[11] Gallager R G.Information theory and reliable communication[M].New York:Wiley,1968.