Test Generation for Bridging Faults in Reversible Circuits Using Path-Level Expressions | Journal of Electronic Testing Skip to main content
Springer Nature Link
Log in

Test Generation for Bridging Faults in Reversible Circuits Using Path-Level Expressions

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

Abstract

Recently there has been a growing interest in the applicability of reversible circuits. Reversible circuits are designed using reversible gates, which can efficiently reconstruct the previous state of the computation from the current state. These circuits may find potential applications to the future generation of optical and quantum computers. To ensure the reliability of these circuits, testing is a mandatory phase of the design cycle. Several fault models have been introduced for reversible circuits among which some of them have been taken from the conventional circuits. In this paper, we consider the problem of testing bridging faults (such as single and multiple input bridging faults, single and multiple intra-level bridging faults) in a reversible circuit designed with the NOT, CNOT, Toffoli gates (NCT library) and generalized (n-bit) Toffoli gates (GT library). We propose an Automatic Test Pattern Generation (ATPG) method using the Path-Level expression for generating the minimal complete test set to detect the faults mentioned above. The analysis of the experimental results shows that the proposed method has 100% fault coverage, and test set size is smaller than the existing methods.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  1. Abramovici M, Breuer MA, Friedman AD (1995) Digital Systems Testing and Testable Design. IEEE Press, Piscataway

    Google Scholar 

  2. Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17(6):525–532

    Article  MathSciNet  MATH  Google Scholar 

  3. Bubna M, Goyal N, Sengupta I (2007) A DFT methodology for detecting bridging faults in reversible logic circuits. In: Proceedings of IEEE region 10 (TENCON), pp 1–4

  4. Chakraborty A (2005) Synthesis of Reversible Circuits for Testing with Universal Test Set and C-Testability of Reversible Iterative Logic Arrays. In: Proceedings of 18th International Conference on VLSI Design. IEEE, pp 249–254

  5. Fang-ying X, Han-wu C, Wen-jie L, Zhi-giang L (2008) Fault Detection for Single and Multiple Missing-gate Faults in Reversible circuits. In: Proceedings of IEEE Congress on Evolutionary Computation, (IEEE World Congress on Computational Intelligence), CEC 2008, pp 131–135

  6. Feynman RP (1986) Quantum mechanical computers. Found Phys 16(6):507–531

    Article  MathSciNet  Google Scholar 

  7. Frank MP (2017) Throwing computing into reverse. IEEE Spectr 54(9):32–37

    Article  Google Scholar 

  8. Frank MP (2018) Back to the Future: The Case for Reversible Computing. arXiv:1803.02789

  9. Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21:219–253

    Article  MathSciNet  MATH  Google Scholar 

  10. Ibrahim M, Chowdhury AR, Babu HMH (2008) Minimization of CTS of k-CNOT Circuits for SSF and MSF Model. In: Proceeidngs of IEEE International Symposium on Defect and Fault Tolerance of VLSI Systems, DFTVS’08, pp 290–298

  11. Jha N, Gupta S (2003) Testing of digital systems. Cambridge University Press, Cambridge

    Book  Google Scholar 

  12. Hayes JP, Polian I, Becker B (2004) Testing for Missing-Gate Faults in Reversible Circuits. In: Proceedings of 13th Asian Test Symposium. IEEE, pp 100–105

  13. Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5(8):183–191

    Article  MathSciNet  MATH  Google Scholar 

  14. Loss D, DiVincenzo DP (1998) Quantum computation with quantum dots. Phys Rev A 57(1):120–126

    Article  Google Scholar 

  15. Maslov D (2003) Reversible Logic Synthesis. Ph.D. diss. University of New Brunswick

  16. Maslov D (2015) Reversible Logic Synthesis Benchmarks Page. Online: http://webhome.cs.uvic.ca/dmaslov/

  17. Mei KCY (1974) Bridging and Stuck-At faults. IEEE Trans Comput 100(7):720–727

    Article  MathSciNet  MATH  Google Scholar 

  18. Nagamani AN, Abhishek B, Agrawal VK (2015) Deterministic approach for Bridging fault detection in Peres-Fredkin and Toffoli based Reversible circuits. In: Proceedings of International Conference on Computational Intelligence and Computing Research (ICCIC). IEEE, pp 1–6

  19. Nagamani AN, Ashwin S, Abhishek B, Agrawal VK (2016) An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits. J Electron Test 32(2):175–196

    Article  Google Scholar 

  20. Nayeem NM, Rice JE (2011) A simple Approach for Designing Online Testable Reversible Circuits. In: Proceedings of IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM). IEEE, pp 85–90

  21. Nielson MA, Chuang IL (2002) Quantum computation and quantum information. Am J Phys 70(5):558–559

    Article  Google Scholar 

  22. Patel KN, Hayes JP, Markov IL (2004) Fault testing for reversible circuits. IEEE Trans Comput-Aided Des Integr Circ Syst 23(8):1220–1230

    Article  Google Scholar 

  23. Peres A (1985) Reversible logic and quantum computers. Phys Rev 32(6):3266–3276

    Article  MathSciNet  Google Scholar 

  24. Polian I, Hayes JP, Fiehn T, Becker B (2005) A Family of Logical Fault Models for Reversible Circuits. In: Proceedings of 14th Asian Test Symposium. IEEE, pp 422–427

  25. Rahaman H, Kole DK, Das DK, Bhattacharya BB (2007) Optimum Test Set for Bridging Fault Detection in Reversible Circuits. In Proceedings of 16th Asian Test Symposium (ATS 2007). IEEE, pp 125–128

  26. Rahaman H, Kole DK, Das DK, Bhattacharya BB (2008) On the Detection of Missing-Gate Faults in Reversible Circuits by a Universal Test Set. In: Proceedings of 21st International Conference on VLSI design, VLSID. IEEE, pp 163– 168

  27. Rice JE (2013) An overview of fault models and testing approaches for reversible logic. In: Proceeidngs of IEEE pacific rim conference on communications, computers and signal processing, PACRIM. IEEE, pp 125–130

  28. Sarkar P, Chakrabarti S (2008) Universal Test Set for Bridging Fault Detection in Reversible circuit. In: Proceedings of 3rd International conference on Design and Test Workshop, IDT 2008. IEEE, pp 51–56

  29. Sarkar P, Mondal B, Chakraborty S (2011) Optimal universal test set for bridging faults detection in reversible circuit using unitary matrix. In: Proceedings of 2nd IEEE International Workshop on Reliability Aware System Design and TEST (RASDAT), pp 37–42

  30. Schaller RR (1997) MOORE’S LAW: past, present, and future. IEEE Spectr 34(6):52–59

    Article  Google Scholar 

  31. Shende VV, Prasad AK, Markov IL, Hayes JP (2003) Synthesis of reversible logic circuits. IEEE Trans Comput-Aided Des Integr Circ Syst 22(6):710–722

    Article  Google Scholar 

  32. Thapliyal H, Ranganathan N (2009) Design of efficient reversible binary subtractors based on a new reversible gate. In: Proceedings of IEEE computer society Annual symposium on VLSI, pp 229–234

  33. Toffoli T (1980) Reversible Computing. In: Proceedings of the 7th Colloquium on Automata, Languages and Programming, pp 632–644

  34. Wille R, Groe D, Teuber L, Dueck GW, Drechsler R (2008) Revlib: An Online Resource for Reversible Functions and Reversible Circuits. In: Proceedings of 38th International Symposium on Multiple Valued Logic (ISMVL 2008), pp 220–225

  35. Zhong J, Muzio JC (2006) Analyzing fault models for reversible logic circuits. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2006), pp 2422–2427

Download references

Author information

Authors and Affiliations

  1. Department of CSE, Indian Institute of Technology, Guwahati (IITG), Guwahati, 781039, Assam, India

    Mousum Handique & Jantindra Kumar Deka

  2. Department of EECS, Indian Institute of Technology, Chhattisgarh, Bhilai, India

    Santosh Biswas

Authors
  1. Mousum Handique
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Santosh Biswas
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jantindra Kumar Deka
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Santosh Biswas.

Additional information

Responsible Editor: B. B. Bhattacharya

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Handique, M., Biswas, S. & Deka, J.K. Test Generation for Bridging Faults in Reversible Circuits Using Path-Level Expressions. J Electron Test 35, 441–457 (2019). https://doi.org/10.1007/s10836-019-05811-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10836-019-05811-1

Keywords

Search

Navigation