Skip to main content
Top
Published in: Journal of Electronic Testing 1/2020

04-02-2020

An Efficient Test Set Construction Scheme for Multiple Missing-Gate Faults in Reversible Circuits

Authors: Mousum Handique, Jantindra Kumar Deka, Santosh Biswas

Published in: Journal of Electronic Testing | Issue 1/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Show more products
Literature
2.
4.
go back to reference 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–1230CrossRef 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–1230CrossRef
5.
go back to reference 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 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
6.
go back to reference 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–17CrossRef 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–17CrossRef
7.
go back to reference 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 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
8.
go back to reference 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 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
9.
go back to reference 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 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
10.
go back to reference Jha NK, Gupta S (2003) Testing of digital systems. Cambridge University Press, CambridgeCrossRef Jha NK, Gupta S (2003) Testing of digital systems. Cambridge University Press, CambridgeCrossRef
11.
go back to reference 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 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
12.
go back to reference 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–54CrossRef 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–54CrossRef
13.
go back to reference 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–311CrossRef 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–311CrossRef
14.
go back to reference Feynman RP (1961) Quantum mechanical computers. Optics InfoBase, Optics News 11(3):11–20 Feynman RP (1961) Quantum mechanical computers. Optics InfoBase, Optics News 11(3):11–20
15.
go back to reference Toffoli T (1980) Reversible computing. Lecture Notes in Computer Science (LNCS) 85. Springer, Berlin Toffoli T (1980) Reversible computing. Lecture Notes in Computer Science (LNCS) 85. Springer, Berlin
18.
go back to reference Loss D, DiVincenzo DP (1998) Quantum computation with quantum dots. Phys Rev A 57(1):120CrossRef Loss D, DiVincenzo DP (1998) Quantum computation with quantum dots. Phys Rev A 57(1):120CrossRef
19.
go back to reference Maslov DA (2003) Reversible logic synthesis. Ph.D. thesis, Fredericton, N.B., Canada, Canada. AAINQ98874 Maslov DA (2003) Reversible logic synthesis. Ph.D. thesis, Fredericton, N.B., Canada, Canada. AAINQ98874
20.
go back to reference 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 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
21.
go back to reference 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 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
22.
go back to reference 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 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
23.
go back to reference 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 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
24.
go back to reference 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–485CrossRef 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–485CrossRef
25.
go back to reference 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 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
26.
go back to reference 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 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
27.
go back to reference 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 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
28.
go back to reference 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 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
29.
go back to reference 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 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
30.
go back to reference 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–336CrossRef 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–336CrossRef
31.
go back to reference 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 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
32.
go back to reference 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–196CrossRef 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–196CrossRef
33.
go back to reference 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 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
34.
go back to reference Zhang B, Agrawal VD (2017) Three-stage optimization of pre-bond diagnosis of TSV defects. J Electron Test 33(5):573–589CrossRef Zhang B, Agrawal VD (2017) Three-stage optimization of pre-bond diagnosis of TSV defects. J Electron Test 33(5):573–589CrossRef
35.
go back to reference 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 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
Metadata
Title
An Efficient Test Set Construction Scheme for Multiple Missing-Gate Faults in Reversible Circuits
Authors
Mousum Handique
Jantindra Kumar Deka
Santosh Biswas
Publication date
04-02-2020
Publisher
Springer US
Published in
Journal of Electronic Testing / Issue 1/2020
Print ISSN: 0923-8174
Electronic ISSN: 1573-0727
DOI
https://doi.org/10.1007/s10836-020-05855-8

Other articles of this Issue 1/2020

Journal of Electronic Testing 1/2020 Go to the issue