Structural diagnosis of interconnects by coloring

ABSTRACT

This paper presents a new approach for diagnosing shorts in interconnects in which the adjacencies between nets are known. This structural approach exploits different graph coloring techniques to generate a test set with no aliasing and confounding, i.e., full diagnosis (detection and location) is accomplished. Initially, a simple coloring approach based on a greedy condition of the adjacency graph is proposed for fault detection. Then, the conditions for aliasing and confounding are analyzed with respect to the sizes of the possible shorts. These results are used to generate new colors using a process called color mixing. Color mixing guarantees that additional tests, required in order to avoid aliasing/confounding, will use appropriate codes. The characteristics of unbalanced/balanced codes for encoding the colors in the vector-generation process of interconnect diagnosis are discussed and are proved to yield full diagnosis using a novel method. An algorithm for full diagnosis is then presented; this algorithm has an execution complexity of O(max{N 2, N×D 3}) where N is the number of nets and D is the maximum degree of the nodes in the adjacency graph. Simulation results show that the proposed approach requires a smaller number of test vectors than previous approaches.

REFERENCES

• 1: ACTEL CORP. 1994. FPGA Data Book and Design Guide. Actel Corp., Sunnyvale, CA.
• 2: ALTERA, 1993. Data Book. Altera, San Jose, CA.
• 3: APTIX CORP. 1993. System Data Book. Aptix Corp.
• 4: CHAN, J. C. 1992. Boundary walking test: An accelerated scan method for greater system reliability. IEEE Trans. Reliability 41, 4, 496-503.
• 5: CHEN, C. C. AND HWANG, F. 1989. Detecting and locating electrical shorts using group testing. IEEE Trans. Circ. Syst. 36, 8, 1113-1116.
• 6: CHENG, W.-T., LEWANDOWSKI, J. L., AND WU, E. 1990. Diagnosis for wiring interconnects. In Proceedings of the International Test Conference. 565-571.
• 7: CHENG, W. T., LEWANDOWSKI, J. L., AND WU, E. 1992. Optimal diagnostic methods for wiring interconnects. IEEE Trans. CAD 11, 9, 1161-1166.
• 8: Chao Feng , Wei Kang Huang , F. Lombardi, A New Diagnosis Approach for Short Faults in Interconnects, Proceedings of the Twenty-Fifth International Symposium on Fault-Tolerant Computing, p.331, June 27-30, 1995
• 9: GAREY, M., JOHNSON, D., AND So, g. 1976. An application of graph coloring to printed circuit testing. IEEE Trans. Circ. Syst. 23, 10, 591-599.
• 10: P. Goel , M. T. McMahon, Electronic Chip-in-Place Test, Proceedings of the 19th conference on Design automation, p.482-488, January 1982
• 11: HASSAN, A., RAJSKI, J., AND AGRAWAL, V. K. 1988. Testing and diagnosis of interconnects using boundary-scan. In Proceedings of the International Test Conference. 126-137.
• 12: JARWALA, N. AND YAU, C.W. 1989. A new framework for analyzing test generation and diagnosis algorithms for wiring interconnects. In Proceedings of the International Test Conference. 63-70.
• 13: KAUTZ, W. H. 1974. Testing for fault in wiring networks. IEEE Trans. Comput. C-23, 4, 358 -363.
• 14: Jung-Cheun Lien , Melvin A. Breuer, Maximal Diagnosis for Wiring Networks, Proceedings of the IEEE International Test Conference on Test: Faster, Better, Sooner, p.96-105, October 26-30, 1991
• 15: T. Liu , F. Lombardi , J. Salinas, Diagnosis of interconnects and FPICs using a structured walking-1 approach, Proceedings of the 13th IEEE VLSI Test Symposium (VTS'95), p.256, April 30-May 03, 1995
• 16: Tong Liu , Xiaotao Chen , F. Lombardi , J. Salinas, Layout-driven detection of bridge faults in interconnects, Proceedings of the 1996 Workshop on Defect and Fault-Tolerance in VLSI Systems, p.105, November 06-08, 1996
• 17: MCBEAN, D. AND MOORE, W. R. 1993. Testing interconnects: A pin adjacency approach. In Proceedings of the IEEE European Test Conference. 484-490.
• 18: PINEDA, J. AND DI, C. 1992. IC defect sensitivity for footprint-type spot defects. IEEE Trans. CAD 11, 5, 638-658.
• 19: Jose Salinas , Yinan Shen , Fabrizio Lombardi, A Sweeping Line Approach to Interconnect Testing, IEEE Transactions on Computers, v.45 n.8, p.917-929, August 1996 [doi>10.1109/12.536234]
• 20: Weiping Shi , W. Kent Fuchs, Optimal interconnect diagnosis of wiring networks, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.3, p.430-436, Sept. 1995 [doi>10.1109/92.407000]
• 21: STOPPER, g. 1993. An advanced version of the electrically programmable hybrid WSI substrate. In Proceedings of the IEEE International Conference on WSI. 289-298.
• 22: TUMMALA, R. R. 1992. Multichip packaging, a tutorial. Proc. IEEE 80, 12, 1924-1941.
• 23: WAGNER, P. T. 1987. Interconnect testing with boundary scan. In Proceedings of the International Test Conference. 52-57.
• 24: XILINX. 1994. The Programmable Logic Data Book. Xilinx, San Jose, CA.
• 25: YAO, S. Z., CHOU, N. C., CHENG, C. K., AND HU, T. C. 1994. A multi-probe approach for MCM substrate testing. IEEE Trans. CAD 13, 1, 110-121.
• 26: YAU, C. W. AND JARWALA, N. 1989. A unified theory for designing optimal test generation and diagnosis algorithms for board interconnects. In Proceedings of the International Test Conference. 71-77.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  J. Computer Applications

General Terms:
Reliability, Verification

Keywords:
balanced code, diagnosis, graph coloring, interconnect, syndrome