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

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

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

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.