Theorems for Fault Collapsing in Combinational Circuits | Journal of Electronic Testing Skip to main content
Springer Nature Link
Log in

Theorems for Fault Collapsing in Combinational Circuits

  • Published:
Journal of Electronic Testing Aims and scope Submit manuscript

Abstract

This paper gives a mathematical approach to fault collapsing based on the stuck-at fault model for combinational circuits. The mathematical structure we work within is a Boolean ring of Boolean functions of several variables. The goal of fault collapsing for a given circuit is to reduce the number of stuck-at faults to be considered in test generation and fault diagnosis. For this purpose we need rules that let us eliminate faults from the considered fault set. In this paper some earlier known rules are proved in the new context, and several new rules are presented and proved. The most important of the new theorems deal with the relationship between stuck-at faults on a fanout stem and the branches. The concept of monotony of Boolean functions appears to be important in most of these new rules.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M. Abramovici, D.T. Miller, and R.K. Roy, “Dynamic Redundancy Identification in Automatic Test Generation,” IEEE Transactions on Computer-Aided Design, vol. 11, no. 3, pp. 404–407, March 1992.

    Article  Google Scholar 

  2. V.D. Agrawal, A.V.S.S. Prasad, and M.V. Atre, “Fault Collapsing via Functional Dominance,” in Proc. International Test Conference, 2003, pp. 274–280.

  3. M.E. Amyeen, W.K. Fuchs, I. Pomeranz, and V. Boppana, “Fault Equivalence Identification in Combinational Circuits Using Implication and Evaluation Techniques,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 22, no. 7, pp. 922–936, July 2003.

    Article  Google Scholar 

  4. G. Birkhoff, and T.C. Bartee. Modern Applied Algebra, Mcgraw-Hill Book Company, 1970.

  5. M.L. Bushnell, and V.D. Agrawal. Essentials of Electronic Testing for Digital, Memory & Mixed-Signal VLSI Circuits, Kluwer Academic Publishers group, 2000.

  6. J.E. Chen, C.L. Lee, and W.Z. Shen. “Circuit example to demonstrate that fan-out stems of primary inputs must be checkpoints,” Electronic Letters, vol. 25, pp. 1726–1728, 1989.

    Google Scholar 

  7. J.E. Chen, C.L. Lee, and W.Z. Shen, “Checkpoints in Irredundant Two-Level Combinational Circuits,” Journal of Electronic Testing: Theory and Applications”, vol. 2, pp. 395–397, 1991.

    Article  Google Scholar 

  8. J.E. Chen, C.L. Lee, W.Z. Shen, and B. Chen, “Fanout Fault Analysis for Digital Logic Circuits,” in Proc. The Fourth Asian Test Symposium, 1995, pp. 33–39.

  9. M. Davio, J.-P. Deschamps and A. Thayse, Discrete and Switching Functions, McGraw-Hill International Book Company, 1978.

  10. L.L. Dornhoff, and F.E. Hohn, Applied Modern Algebra, MacMillan Publishing Co., 1978.

  11. H. Fujiwara, Logic Testing and Design for Testability, MIT Press Series in Computer Systems, The MIT Press, 1985.

  12. I. Hartanto, V. Boppana, and W.K. Fuchs, “Diagnostic Fault Equivalence Identification Using Redundancy Information & Structural Analysis,” in Proc. International Test Conference, 1996, pp. 294–302.

  13. S.C. Lee, Modern Switching Theory and Digital Design, Prentice-Hall, 1978.

  14. A. Lioy, “Looking for Functional Fault Equivalence,” in Proc. International Test Conference, 1991, pp. 858–863.

  15. A. Lioy, “Advanced Fault Collapsing,” IEEE Design & Test of Computers, vol. 9, no. 1, pp. 64–71, March 1992.

    Article  Google Scholar 

  16. A. Lioy, “On the Equivalence of Fanout-Point Faults,” IEEE Transactions on Computers, vol. 42, no. 3, pp. 268–271, March 1993.

    Article  Google Scholar 

  17. A.V.S.S. Prasad, V.D. Agrawal, and M.V. Atre, “A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets,” in Proc. International Test Conference, 2002, pp. 391–397.

Download references

Author information

Authors and Affiliations

  1. Faculty of Engineering and Science, Agder University College, Agder

    Audhild Vaaje

Authors
  1. Audhild Vaaje
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Audhild Vaaje.

Additional information

Editor: M. Hsiao

Audhild Vaaje received the M.S. degree and the Ph.D. degree in mathematics from University of Oslo in 1971 and 1992, respectively. She is an associate professor of mathematics at Agder University College in Norway, where she has been employed since 1972. She has research interests in mathematics applied to fault detection in digital circuits.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vaaje, A. Theorems for Fault Collapsing in Combinational Circuits. J Electron Test 22, 23–36 (2006). https://doi.org/10.1007/s10836-006-6222-1

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10836-006-6222-1

Keywords