最小权点覆盖的扫描测试向量生成算法  

Minimum Point Coverage Test Vector Generation Algorithm Based on PCB Structure Information

作　　者：王力 穆东旭 WANG Li;MU Dong-xu(School of Vocational and Technical Engineering,China Civil Aviation University,Tianjin 300300,China;School of Electronic Information and Automation,China Civil Aviation University,Tianjin 300300,China)

机构地区：[1]中国民航大学通用航空学院,天津300300 [2]中国民航大学电子信息与自动化学院,天津300300

出　　处：《计算机仿真》2019年第7期251-256,共6页Computer Simulation

基　　金：国家自然科学基金项目(U1733119);国家自然科学基金项目(U1333111);中央高校基本科研业务费项目(3122017018)

摘　　要：现有的边界扫描测试算法,多数主要通过建立无限制短路故障模型来生成测试向量,但以此方法构造的测试矩阵紧凑性指标较差。提出了一种利用可能性理论下有限制故障模型的最小权点覆盖集进行测试向量生成。首先,通过分析ProtelDXP提供的电路板网表信息建立网络近邻关系图,即赋权图。然后结合Dijkstra算法求取初始点到其余各点的最短路径,并根据最短路径的最大值依照相关准则确定点覆盖集,并给出了具体的算法步骤;最后根据所得出的最小权点覆盖集生成测试矩阵。最后以某大型机载电路板为研究样例,进行理论分析及实验验证表明,上述方法与传统方法相比,获得的测试矩阵具有较好的紧凑性,算法性能有了大幅度提升。Most of the existing boundary scan test algorithms generate test vectors by establishing an unrestricted short-circuit fault model, but the compactness index of the test matrix constructed by this method is poor. This paper proposes a test vector generation using the set of minimum weight points of the limited fault model under the possibility theory. First of all, by analyzing the circuit board netlist information provided by Protel DXP, we established a network neighbor graph, which was a weighted graph. Then Dijkstra algorithm was used to find the shortest path from the initial point to the remaining points, and the point coverage set was determined according to the relevant criterion based on the maximum value of the shortest path, and the specific algorithm steps were given. Finally, the minimum weight point coverage set was obtained according to Generate a test matrix. At the end of the paper, a large-scale airborne circuit board was taken as a research sample. Theoretical analysis and experimental verification show that compared with the traditional method, the test matrix obtained has a better compactness, and the algorithm performance has been greatly improved.

关 键 词：测试向量 可能性理论 有限制故障模型 最短路径 最小点覆盖 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP306[自动化与计算机技术—计算机科学与技术]