Abstract: Considering the fact that special interconnects begin to exist in new Field Programmable Gate Array(FPGA) architectures. This paper proposes an algorithm based on improved depth-first search. Each programmable interconnecting point is equally treated. After a graph representation of interconnects is got, a weight parameter for each edge is set and the edge with the minimum weight is picked to be part of a test net, thereby testing open faults and short faults of interconnects. Experimental results show that the proposed algorithm can be utilized to cover special interconnects of FPGA architectures and exhibits high automation.

Key words: depth-first search, Field Programmable Gate Array(FPGA), interconnect test, automation, wiring resource graph, Switch Matrix(SM)

摘要： 针对FPGA结构中出现特殊互连资源的现状，提出一种基于改进型深度优先搜索的测试算法。该算法将所有可编程互连开关等价对待，互连资源以图的形式表示，给每条边设定权重并选择最小权重边连入测试线网，对互连资源进行遍历搜索，以测试互连资源开路和短路故障。实验结果表明，该算法能够覆盖FPGA结构中出现的特殊互连资源，具有高度自动化的特点。

关键词: 深度优先搜索, 现场可编程门阵列, 互连测试, 自动化, 布线资源图, 开关盒

CLC Number: 

• TP301.6