一种改进的GNS互连测试算法

分析了GNS(Group sequence, Net sequence and Shifted net sequence)算法存在故障混淆的可能性；对于3个网络短路的情况，论述并证明了通过适当的网络分组能够避免故障混淆的发生；进而提出了降低故障混淆发生概率的网络分组原则：使易发生短路故障的网络尽可能位于同一组内；在此基础上，提出了一种基于网络短路关系图的启发式分组方法。该分组方法首先建立了反映网络间相互短路概率的网络短路关系图，然后利用图论的相关知识对分组问题进行了描述，并引入了分组的最优目标函数。考虑到多项式复杂程度的非确定性（NP）完全问题的复杂性，提出了一种启发式的分组算法。结果表明：该分组方法能够在较短的时间内寻找到较优的分组结果，减小GNS算法发生故障混淆的概率，从而提高了它的测试性能。

An Improved GNS Algorithm for Interconnect Test

The probable confounding-syndrome occurring in the group sequence, net sequence and shifted net sequence (GNS) algorithm is first analyzed. Then, a proper net-grouping process which can avoid the confounding-syndrome on the condition of the three nets shorted together is presented and proved. Furthermore, a net-group rule which can decrease the probability of the confounding-syndrome is proposed, which requires putting the nets with a higher probability to be shorted together in a group. According to this r...