An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

详细信息    查看全文

• 作者：A. N. Nagamani ; S. Ashwin ; B. Abhishek ; V. K. Agrawal
• 关键词：Exact algorithms ; Testing ; Redundant faults ; Stuck ; at faults ; Missing gate faults
• 刊名：Journal of Electronic Testing
• 出版年：2016
• 出版时间：April 2016
• 年：2016
• 卷：32
• 期：2
• 页码：175-196
• 全文大小：2,819 KB
• 参考文献：1.Bennett C (1973) Logical reversibility of computation. IBM J Res Dev 17 (6):525–532. doi:10.​1147/​rd.​176.​0525 MathSciNet CrossRef MATH <br>2.Bushnell M, Agrawal VD (2000) Essentials of electronic testing for digital, memory and mixed-signal VLSI circuits, vol 17. Springer Science & Business Media<br>3.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, VLSID. IEEE, pp 249–254<br>4.Chaves JF, Silva DS, Camargos VV, Vilela Neto OP (2015) Towards reversible QCA computers: reversible gates and ALU. In: Proceedings of IEEE 6th Latin American symposium on circuits & systems, (LASCAS). IEEE, pp 1–4<br>5.Donald J, Jha NK (2008) Reversible logic synthesis with fredkin and peres gates. J Emerg Technol Comput Syst 4(1):2:1–2:19CrossRef <br>6.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). doi:10.​1109/​CEC.​2008.​4630787 , pp 131–135<br>7.Hayes J, Polian I, Becker B (2004) Testing for missing-gate faults in reversible circuits. In: Proceedings of 13th Asian test symposium. doi:10.​1109/​ATS.​2004.​84 , pp 100–105<br>8.Ibrahim M, Chowdhury A, Babu H (2008) Minimization of cts of k-cnot circuits for ssf and msf model. In: Proceedings of IEEE International Symposium on Defect and Fault Tolerance of VLSI Systems, DFTVS’08. doi:10.​1109/​DFT.​2008.​38 , pp 290–298<br>9.Ibrahim M, Chowdhury A, Babu H (2008) On the minimization of complete test set of reversible k-cnot circuits for stuck-at fault model. In: Proceedings of 11th international conference on computer and information technology, ICCIT 2008. doi:10.​1109/​ICCITECHN.​2008.​4803009 , pp 7–12<br>10.Kole DK, Rahaman H, Das DK, Bhattacharya BB (2010) Synthesis of online testable reversible circuit. In: Proceedings IEEE 13th international symposium on design and diagnostics of electronic circuits and systems (DDECS). IEEE, pp 277– 280<br>11.Kole DK, Rahaman H, Das DK, Bhattacharya BB (2013) Derivation of test set for detecting multiple missing-gate faults in reversible circuits. Comput Electr Eng 39(2):225– 236CrossRef <br>12.Landauer R (1961) Irreversibility and heat generation in the computing process. IBM J Res Dev 5(3):183–191MathSciNet CrossRef MATH <br>13.Lo HK, Popescu S, Spiller T (eds) (2002) Introduction to quantum computation information. World Scientific Publishing Co., Inc., River Edge<br>14.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 <br>15.Mahammad S, Veezhinathan K (2010) Constructing online testable circuits using reversible logic. IEEE Trans Instrum Meas 59(1):101–109. doi:10.​1109/​TIM.​2009.​2022103 CrossRef <br>16.Maslov D (2015) Reversible logic synthesis benchmarks page. Online: http://​webhome.​cs.​uvic.​ca/​dmaslov/​span> <br>17.Maslov D, Dueck G, Miller D (2005) Synthesis of fredkin-toffoli reversible networks. IEEE Trans Very Large Scale Integr VLSI Syst 13(6):765–769. doi:10.​1109/​TVLSI.​2005.​844284 CrossRef <br>18.Mishchenko A, Perkowski M (2002) Logic synthesis of reversible wave cascades. In: Proceedings of international workshop on logic synthesis, pp 197–202<br>19.Mondal B, Kole D, Das D, Rahaman H (2014) Generator for test set construction of smgf in reversible circuit by boolean difference method. In: Proceedings of IEEE 23rd Asian test symposium (ATS). doi:10.​1109/​ATS.​2014.​24 , pp 68–73<br>20.Nayeem N, Rice J (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<br>21.Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press<br>22.Perumalla KS (2013) Introduction to reversible computing<br>23.Polian I, Fiehn T, Becker B, Hayes JP (2005) A family of logical fault models for reversible circuits. In: Proceedings of 14th Asian test symposium. IEEE, pp 422–427<br>24.Polian I, Hayes JP (2010) Advanced modeling of faults in reversible circuits. In: Proceedings of East-West design & test symposium (EWDTS). IEEE, pp 376–381<br>25.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<br>26.Rahaman H, Kole DK, Das DK, Bhattacharya BB (2011) Fault diagnosis in reversible circuits under missing-gate fault model. Comput Electr Eng 37(4):475–485CrossRef MATH <br>27.Soeken M, Chattopadhyay A (2015) Fredkin-enabled transformation-based reversible logic synthesis. In: Proceedings of IEEE international symposium on multiple-valued logic (ISMVL). doi:10.​1109/​ISMVL.​2015.​37 , pp 60–65<br>28.Taraphdar C, Chattopadhyay T, Roy JN (2010) Mach–zehnder interferometer-based all-optical reversible logic gate. Opt Laser Technol 42(2):249–259CrossRef <br>29.Thapliyal H, Vinod AP (2007) Designing efficient online testable reversible adders with new reversible gate. In: Proceedings of IEEE international symposium on circuits and systems, ISCAS. IEEE, pp 1085–1088<br>30.Vasudevan DP, Lala PK, Di J, Parkerson JP (2006) Reversible-logic design with online testability. IEEE Trans Instrum Meas 55(2):406–414CrossRef <br>31.Wille ADVR (2010) Reversible computation. Springer<br>32.Wille R, Zhang H, Drechsler R (2011) Atpg for reversible circuits using simulation, boolean satisfiability, and pseudo boolean optimization. In: Proceedings of IEEE computer society annual symposium on VLSI (ISVLSI). IEEE, pp 120– 125<br>33.Woeginger GJ (2003) Exact algorithms for NP-hard problems: a survey. Springer<br>34.Zamani M, Tahoori MB (2011) Online missing/repeated gate faults detection in reversible circuits. In: Proceedings of IEEE international symposium on defect and fault tolerance in VLSI and nanotechnology systems (DFT). IEEE, pp 435– 442<br>35.Zamani M, Tahoori MB, Chakrabarty K (2012) Ping-pong test: Compact test vector generation for reversible circuits. In: Proceedings of IEEE 30th VLSI test symposium (VTS). IEEE, pp 164– 169<br>
• 作者单位：A. N. Nagamani (1) <br> S. Ashwin (1) <br> B. Abhishek (1) <br> V. K. Agrawal (2) <br><br>1. Department of ECE, PES University Campus, PES Institute of Technology, Bangalore, Karnataka, India <br> 2. Department of Information science and Engineering, PES University Campus, PES Institute of Technology, Bangalore, Karnataka, India <br>
• 刊物类别：Engineering
• 刊物主题：Circuits and Systems<br>Electronic and Computer Engineering<br>Computer-Aided Engineering and Design<br>
• 出版者：Springer Netherlands
• ISSN：1573-0727

文摘

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS’s indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.