Abstract
Several fault models are introduced for efficiently identifying the faults in the reversible circuits, where some of the fault models are borrowed from the conventional circuits. In this work, we consider the Missing Gate Fault Model (MGF) which is specifically used for reversible circuits. The proposed work provides a scheme for generating the complete test set for detecting the single and any number of consecutive multiple missing gate faults in k-CNOT based reversible circuits. The complete test set generation method is twofold. First, a local test pattern is applied to each level of k-CNOT gates and the reverse simulation method is used for identifying all the possible Single Missing Gate Faults (SMGFs). Second, using the complete test set for SMGFs and based on the structure of the k-CNOT based circuit, a test set is formulated. The generated test set is capable of detecting all the MMGFs and as well as the SMGFs in reversible circuits. However, the generated complete test set is not minimal. For achieving the minimality, a table is constructed covering row and column faults and an integer linear programming (ILP) problem is formulated to achieve the minimality of the test set. The experimental results demonstrate that the size of the generated minimized test set is smaller or similar as compared to the existing methods and attains 100% fault coverage.
Similar content being viewed by others
References
Schaller RR (1997) Moore’s law: past, present, and future. IEEE Spectr 34 (6):52–59. https://doi.org/10.1109/6.591665
Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5(8):183–191
Bennett C (1973) Logical reversibility of computation. IBM J Res Dev 17 (6):525–532. https://doi.org/10.1147/rd.176.0525
Patel KN, Hayes JP, Markov IL (2004) Fault testing for reversible circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 23(8):1220–1230
Rahaman H, Kole DK, Das DK, Bhattacharya BB (2007) Optimum test set for bridging fault detection in reversible circuits. In: Proc. of 16th asian test symposium (ATS’07). IEEE, pp 125–128
Handique M, Biswas S, Deka JK (2019) Test generation for bridging faults in reversible circuits using path-level expressions. J Electron Test 35(4):1–17
Hayes JP, Polian I, Becker B (2004) Testing for missing-gate faults in reversible circuits. In: Proc. of 13th asian test symposium. IEEE, pp 100–105
Polian I, Fiehn T, Becker B, Hayes JP (2005) A family of logical fault models for reversible circuits. In: Proc. of 14th asian test symposium. IEEE, pp 422–427
Zhong J, Muzio JC (2006) Analyzing fault models for reversible logic circuits. In: Proc. of IEEE congress on evolutionary computation, CEC 2006, pp 2422–2427
Jha NK, Gupta S (2003) Testing of digital systems. Cambridge University Press, Cambridge
Rice J (2013) An overview of fault models and testing approaches for reversible logic. In: Proc. of IEEE pacific rim conference on communications, computers and signal processing (PacRim). IEEE, pp 125–130
Xiaojun M, Huang J, Metra C, Lombardi F (2009) Detecting multiple faults in one-dimensional arrays of reversible qca gates quantum. J Electron Test 25:39–54
Ma X, Huang J, Metra C, Lombardi F (2008) Reversible gates and testability of one dimensional arrays of molecular qca. J Electron Test 24(1-3):297–311
Feynman RP (1961) Quantum mechanical computers. Optics InfoBase, Optics News 11(3):11–20
Toffoli T (1980) Reversible computing. Lecture Notes in Computer Science (LNCS) 85. Springer, Berlin
Fredkin E, Toffoli T (1982) Conservative logic. Int J Theor Phys 21:219–253
Maslov D (2015) Reversible logic synthesis benchmarks page. Online: http://webhome.cs.uvic.ca/dmaslov/
Loss D, DiVincenzo DP (1998) Quantum computation with quantum dots. Phys Rev A 57(1):120
Maslov DA (2003) Reversible logic synthesis. Ph.D. thesis, Fredericton, N.B., Canada, Canada. AAINQ98874
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: Proc. of IEEE congress on evolutionary computation, (IEEE World Congress on Computational Intelligence), CEC 2008, pp 131–135
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: Proc. of 21st international conference on VLSI design, VLSID. IEEE, pp 163–168
Kole DK, Rahaman H, Das DK, Bhattacharya BB (2010) Derivation of optimal test set for detection of multiple missing-gate faults in reversible circuits. In: Proc. of 19th asian test symposium. IEEE, pp 33–38
Zamani M, Tahoori MB, Chakrabarty K (2012) Ping-pong test: compact test vector generation for reversible circuits. In: Proc. of 30th VLSI test symposium (VTS). IEEE, pp 164–169
Rahaman H, Kole DK, Das DK, Bhattacharya BB (2011) Fault diagnosis in reversible circuits under missing-gate fault model. Computers & Electrical Engineering 37(4):475–485
Zhang H, Wille R, Drechsler R (2010) SAT-based ATPG for reversible circuits. In: Proc. of 5th international design and test workshop. IEEE, pp 149–154
Wille R, Zhang H, Drechsler R (2011) ATPG for reversible circuits using simulation, Boolean satisfiability, and pseudo Boolean optimization. In: Proc. of IEEE computer society annual symposium on VLSI. IEEE, pp 120–125
Zhang H, Frehse S, Wille R, Drechsler R (2011) Determining minimal testsets for reversible circuits using Boolean satisfiability. In: Proc. of IEEE Africon’11. IEEE, pp 1–6
Mondal J, Das DK, Kole DK, Rahaman H (2013) A design for testability technique for quantum reversible circuits. In: Proc. of East-West design & test symposium (EWDTS 2013). IEEE, pp 1–4
Kole A, Wille R, Datta K, Sengupta I (2017) Test pattern generation effort evaluation of reversible circuits. In: Proc. of international conference on reversible computation. Springer, Cham, pp 162–175
Nagamani AN, Anuktha SN, Nanditha N, Agrawal VK (2018) A genetic algorithm-based heuristic method for test set generation in reversible circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37(2):324–336
Mondal B, Kole DK, Das DK, Rahaman H (2014) Generator for test set construction of smgf in reversible circuit by boolean difference method. In: Proc. of 23rd asian test symposium. IEEE, pp 68–73
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
Surhonne AP, Chattopadhyay A, Wille R (2017) Automatic test pattern generation for multiple missing gate faults in reversible circuits. In: Proc. of international conference on reversible computation. Springer, Cham, pp 176–182
Zhang B, Agrawal VD (2017) Three-stage optimization of pre-bond diagnosis of TSV defects. J Electron Test 33(5):573–589
Wille R, Große D, Teuber L, Dueck GW, Drechsler R (2008) RevLib: an online resource for reversible functions and reversible circuits. In: Proc. of 38th international symposium on multiple valued logic (ismvl 2008). IEEE, pp 220–225
Author information
Authors and Affiliations
Corresponding author
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
About this article
Cite this article
Handique, M., Deka, J.K. & Biswas, S. An Efficient Test Set Construction Scheme for Multiple Missing-Gate Faults in Reversible Circuits. J Electron Test 36, 105–122 (2020). https://doi.org/10.1007/s10836-020-05855-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10836-020-05855-8