eesti teaduste
akadeemia kirjastus
Estonian Journal of Engineering

Hierarchical physical defect reasoning in digital circuits; pp. 185–200

Full article in PDF format | doi: 10.3176/eng.2011.3.02

Sergei Kostin, Raimund Ubar, Jaan Raik, Marina Brik


We propose a hierarchical physical defect-oriented approach for fault diagnosis in combinational digital circuits. We present the circuit as a network of modules. As modules we consider either library components (e.g. complex gates) of digital circuits or arbitrary subcircuits. The higher level fault diagnosis is carried out in two phases. In the first phase, faulty modules are located by cause–effect analysis using high-level faulty module dictionary. The size of the dictionary depends linearly on the number of modules in the circuit. In the second phase, the set of suspected faulty modules is pruned by reasoning of the defective behaviour. At the lower level, the physical defects are directly located in suspected faulty modules using defect libraries of the modules or by effect–cause reasoning inside the module. The proposed approach to fault diagnosis helps to cope with the growing complexities of digital circuits. The experimental results show high module-level diagnostic resolution of the proposed approach.


  1. Venkataraman, S. and Drummonds, S. B. Poirot: Applications of a logic fault diagnosis tool. IEEE Trans. Design Test Computers, 2001, 18, 19–29.

  2. Huisman, L. M. Diagnosing arbitrary defects in logic designs using single location at a time (SLAT). IEEE Trans. CAD, 2004, 23, 91–101.

  3. Holst, S. and Wunderlich, H.-J. Adaptive debug and diagnosis without fault dictionaries. In Proc. 12th European Test Symposium. Freiburg, 2007, 7–12.

  4. Rousset, A., Bosio, A., Girard, P., Landrault, C., Pravossoudovitch, S. and Virazel, A. Derric: A tool for unified logic diagnosis. In Proc. 12th European Test Symposium. Freiburg, 2007, 13–20.

  5. Wang, L. T., Wu, C. W. and Wen, X. VLSI test principles and architectures. In Design for Testability. Elsevier, 2006.

  6. Zhuo, L., Lu, X., Qiu, W., Shi, W. and Walker, D. M. H. A circuit level fault model for resistive opens and bridges. In Proc. VLSI Test Symp. Napa, CA, 2003, 379–384.

  7. Liu, C. Compact dictionaries for fault diagnosis in scan-BIST. IEEE Trans. Computers, 2004, 53, 775–780.

  8. Acken, J. M. and Millman, S. D. Accurate modeling and simulating of bridge faults. In Proc. Custom Integrated Circuits Conference. San Diego, CA, 1991, 17.4.1–17.4.4.

  9. Jain, S. K. and Agrawal, V. D. Modeling and test generation algorithms for MOS circuits. IEEE Trans. Computers, 1985, C-34, 426–433.

10. Lee, H. K. and Ha, D. S. SOPRANO: An efficient automatic test pattern generator for stuck-open faults in CMOS combinational circuits. In Proc. Design Automation Conference. Orlando, FL, 1990, 660–666.

11. Kristic, A. and Cheng, K. T. Delay Fault Testing for VLSI Circuits. Kluwer, Boston, MA, 1998.

12. Roth, J. P. Diagnosis of automata failures: A calculus and a method. IBM J. Res. Developm., 1966, 10, 278–291.

13. Blanton, R. D. and Hayes, J. P. On the properties of the input pattern fault model. ACM Trans. Des. Automat. Electron. Syst., 2003, 8, 108–124.

14. Keller, K. B. Hierarchical pattern faults for describing logic circuit failure mechanisms. US Patent 5546408, Aug. 13, 1994.

15. Ubar, R. Detection of suspected faults in combinational circuits by solving boolean differential equations. Automation and Remote Control, 1980, 40, 1693–1703 (Plenum Publ. Corp., USA).

16. Ubar, R., Devadze, S., Raik, J. and Jutman, A. Fast fault simulation for extended class of faults in scan-path circuits. In Proc. 5th IEEE International Symposium DELTA. Ho Chi Minh City, Vietnam, 2010, 14–19.

17. Mahlstedt, U., Alt, J. and Hollenbeck, I. Deterministic test generation for non-classical faults on the gate level. In Proc. 4th Asian Test Symposium. Bangalore, 1995, 244–251.

18. Holst, S. and Wunderlich, H.-J. Adaptive debug and diagnosis without fault dictionaries. In Proc. 13th European Test Symposium. Verbania, Italy, 2008, 199–204.

19. Ubar, R., Kuzmicz, W., Pleskacz, W. and Raik, J. Defect-oriented fault simulation and test generation in digital circuits. In Proc. 2nd International Symposium on Quality of Electronic Design. San Jose, CA, 2001, 365–371.

Back to Issue