{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:00Z","timestamp":1750308600174,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T00:00:00Z","timestamp":1466985600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"EU COST Action","award":["IC1405"],"award-info":[{"award-number":["IC1405"]}]},{"name":"European Commission in the framework of the Erasmus Mundus cLINK project"},{"name":"PPEC-grant to Nanotechnology Research Triangle received from the Indian Statistical Institute, Kolkata"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2016,7,26]]},"abstract":"<jats:p>\n            In this article, we introduce a novel method of synthesizing symmetric Boolean functions with reversible logic gates. In contrast to earlier approaches, the proposed technique deploys a simple, regular, and cascaded structure consisting of an array of Peres and CNOT gates, which results in significant reduction with respect to the quantum cost. However, the number of circuit inputs may increase slightly when such cascades are used. In order to reduce their number, we next propose a postsynthesis optimization phase that allows judicious reuse of circuit lines. In addition to offering a cost-effective synthesis methodology, the proposed reversible logic structure supports elegant testability properties. With respect to all single or partial missing gate faults (SMGFs and PMGFs), or repeated gate faults (RGFs) in such an\n            <jats:italic>n<\/jats:italic>\n            -input circuit module, we show that it admits a universal test set of constant cardinality (=3) for any value of\n            <jats:italic>n<\/jats:italic>\n            . Thus, considering both the cost and testability issues, this approach provides a superior option for synthesizing symmetric functions compared to existing designs.\n          <\/jats:p>","DOI":"10.1145\/2894757","type":"journal-article","created":{"date-parts":[[2016,6,27]],"date-time":"2016-06-27T15:39:29Z","timestamp":1467041969000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Reversible Synthesis of Symmetric Functions with a Simple Regular Structure and Easy Testability"],"prefix":"10.1145","volume":"12","author":[{"given":"Arighna","family":"Deb","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Bremen, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Debesh K.","family":"Das","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering, Jadavpur University, Kolkata, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hafizur","family":"Rahaman","sequence":"additional","affiliation":[{"name":"Information Technology, Indian Institute of Engineering Science and Technology, Howrah, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Wille","sequence":"additional","affiliation":[{"name":"Institute for Integrated Circuits, Johannes Kepler University, Linz, Austria Cyber-Physical Systems, DFKI GmbH, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rolf","family":"Drechsler","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Bremen, Bremen, Germany Cyber-Physical Systems, DFKI GmbH, Bremen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bhargab B.","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"Nanotechnology Research Triangle, Indian Statistical Institute, Kolkata, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,6,27]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_2_1_1_1","DOI":"10.1103\/PhysRevA.52.3457"},{"doi-asserted-by":"publisher","key":"e_1_2_1_2_1","DOI":"10.1364\/OL.12.000542"},{"doi-asserted-by":"publisher","key":"e_1_2_1_3_1","DOI":"10.1145\/2629543"},{"doi-asserted-by":"publisher","key":"e_1_2_1_4_1","DOI":"10.1145\/2483028.2483138"},{"doi-asserted-by":"publisher","key":"e_1_2_1_5_1","DOI":"10.1007\/978-3-642-38986-3_15"},{"doi-asserted-by":"publisher","key":"e_1_2_1_6_1","DOI":"10.1016\/S0167-9260(02)00051-2"},{"volume-title":"Proceedings of the Reed Muller Workshop. 53--62","author":"Ghosh S.","unstructured":"S. Ghosh , B. B. Bhattacharya , and S. Sensarma . 2009. Reversible synthesis of symmetric functions: A hierarchical approach . In Proceedings of the Reed Muller Workshop. 53--62 . S. Ghosh, B. B. Bhattacharya, and S. Sensarma. 2009. Reversible synthesis of symmetric functions: A hierarchical approach. In Proceedings of the Reed Muller Workshop. 53--62.","key":"e_1_2_1_7_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_8_1","DOI":"10.1109\/ATS.2004.84"},{"volume-title":"International Conference on VLSI. 25--30","author":"Keren O.","unstructured":"O. Keren , I. Levin , and S. R. Stankovic . 2007. Use of gray decoding for implementation of symmetric functions . In International Conference on VLSI. 25--30 . O. Keren, I. Levin, and S. R. Stankovic. 2007. Use of gray decoding for implementation of symmetric functions. In International Conference on VLSI. 25--30.","key":"e_1_2_1_9_1"},{"doi-asserted-by":"crossref","unstructured":"E. Knill R. Laflamme and G. J. Milburn. 2001. A scheme for efficient quantum computation with linear optics. Nature 46--52.  E. Knill R. Laflamme and G. J. Milburn. 2001. A scheme for efficient quantum computation with linear optics. Nature 46--52.","key":"e_1_2_1_10_1","DOI":"10.1038\/35051009"},{"doi-asserted-by":"crossref","unstructured":"C. Lauradoux and M. Videau. 2008. Matriochka symmetric Boolean functions. In IEEE ISIT. 1631--1635.  C. Lauradoux and M. Videau. 2008. Matriochka symmetric Boolean functions. In IEEE ISIT. 1631--1635.","key":"e_1_2_1_11_1","DOI":"10.1109\/ISIT.2008.4595264"},{"doi-asserted-by":"publisher","key":"e_1_2_1_12_1","DOI":"10.1049\/ip-cds:20045213"},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1088\/0957-4484\/4\/1\/002"},{"volume-title":"Proceedings of the International Workshop on Boolean Problems.","author":"Moraga C.","unstructured":"C. Moraga and F. Z. Hadjam . 2012. On double gates for reversible computing circuits . In Proceedings of the International Workshop on Boolean Problems. C. Moraga and F. Z. Hadjam. 2012. On double gates for reversible computing circuits. In Proceedings of the International Workshop on Boolean Problems.","key":"e_1_2_1_14_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_15_1","DOI":"10.2298\/FUEE1103385N"},{"unstructured":"M. Nielsen and I. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press New York NY.   M. Nielsen and I. Chuang. 2000. Quantum Computation and Quantum Information. Cambridge University Press New York NY.","key":"e_1_2_1_16_1"},{"volume-title":"EUROMICRO Symposium on Digital Systems Design. 245--252","author":"Perkowski M.","unstructured":"M. Perkowski , P. Kerntopf , A. Buller , M. Chrzanowska-Jeske , A. Mishchenko , X. Song , A. Al-Rabadi , L. Jozwiak , A. Coppola , and B. Massey . 2001b. Regular realization of symmetric functions using reversible logic . In EUROMICRO Symposium on Digital Systems Design. 245--252 . M. Perkowski, P. Kerntopf, A. Buller, M. Chrzanowska-Jeske, A. Mishchenko, X. Song, A. Al-Rabadi, L. Jozwiak, A. Coppola, and B. Massey. 2001b. Regular realization of symmetric functions using reversible logic. In EUROMICRO Symposium on Digital Systems Design. 245--252.","key":"e_1_2_1_17_1"},{"unstructured":"M. Perkowski P. Kerntopf A. Buller M. Chrzanowska-Jeske A. Mishchenko X. Song A. Al-Rabadi L. Jozwiak A. Coppola and B. Massey. 2001a. Regularity and symmetry as a base for efficient realization of reversible logic circuits. In IWLS. 245--252.  M. Perkowski P. Kerntopf A. Buller M. Chrzanowska-Jeske A. Mishchenko X. Song A. Al-Rabadi L. Jozwiak A. Coppola and B. Massey. 2001a. Regularity and symmetry as a base for efficient realization of reversible logic circuits. In IWLS. 245--252.","key":"e_1_2_1_18_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_19_1","DOI":"10.1016\/0026-2692(94)90068-X"},{"doi-asserted-by":"publisher","key":"e_1_2_1_20_1","DOI":"10.1109\/ATS.2005.9"},{"doi-asserted-by":"publisher","key":"e_1_2_1_21_1","DOI":"10.1007\/s10836-006-6674-3"},{"doi-asserted-by":"publisher","key":"e_1_2_1_22_1","DOI":"10.1007\/s12095-011-0054-2"},{"doi-asserted-by":"publisher","key":"e_1_2_1_23_1","DOI":"10.1145\/2431211.2431220"},{"doi-asserted-by":"publisher","key":"e_1_2_1_24_1","DOI":"10.1145\/1877745.1877747"},{"unstructured":"M. Soeken L. Tague G. W. Dueck and R. Drechsler. 2014. Ancilla-free synthesis of large reversible functions using binary decision diagrams. CoRR abs\/1408.3955.  M. Soeken L. Tague G. W. Dueck and R. Drechsler. 2014. Ancilla-free synthesis of large reversible functions using binary decision diagrams. CoRR abs\/1408.3955.","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of SPIE, Optomechatronic Micro\/Nano Devices and Components.","author":"Thapliyal H.","unstructured":"H. Thapliyal and M. B. Srinivas . 2005. The need of DNA computing: Reversible designs of adders and multipliers using Fredkin gate . In Proceedings of SPIE, Optomechatronic Micro\/Nano Devices and Components. H. Thapliyal and M. B. Srinivas. 2005. The need of DNA computing: Reversible designs of adders and multipliers using Fredkin gate. In Proceedings of SPIE, Optomechatronic Micro\/Nano Devices and Components.","key":"e_1_2_1_26_1"},{"volume-title":"MIT Lab for Computer Science","author":"Toffoli T.","unstructured":"T. Toffoli . 1980. Reversible computing. Tech Memo MIT\/LCS\/TM-151 , MIT Lab for Computer Science , Cambridge , MA. T. Toffoli. 1980. Reversible computing. Tech Memo MIT\/LCS\/TM-151, MIT Lab for Computer Science, Cambridge, MA.","key":"e_1_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_2_1_28_1","DOI":"10.1145\/1629911.1629984"},{"doi-asserted-by":"crossref","unstructured":"R. Wille R. Drechsler C. Oswald and A. Garcia-Ortiz. 2012. Automatic design of low-power encoders using reversible circuit synthesis. In DATE. 1036--1041.   R. Wille R. Drechsler C. Oswald and A. Garcia-Ortiz. 2012. Automatic design of low-power encoders using reversible circuit synthesis. In DATE. 1036--1041.","key":"e_1_2_1_29_1","DOI":"10.1109\/DATE.2012.6176648"},{"doi-asserted-by":"publisher","key":"e_1_2_1_30_1","DOI":"10.1109\/ISVLSI.2011.77"},{"doi-asserted-by":"publisher","key":"e_1_2_1_31_1","DOI":"10.1109\/ISMVL.2013.28"},{"volume-title":"IEEE International Symposium on Multiple Valued Logic. 141--146","author":"Yanushekvich S. N.","unstructured":"S. N. Yanushekvich , J. T. Butler , G. W. Dueck , and V. P. Shmerko . 2000. Experiments on FPRM expressions for partially symmetric logic functions . In IEEE International Symposium on Multiple Valued Logic. 141--146 . S. N. Yanushekvich, J. T. Butler, G. W. Dueck, and V. P. Shmerko. 2000. Experiments on FPRM expressions for partially symmetric logic functions. In IEEE International Symposium on Multiple Valued Logic. 141--146.","key":"e_1_2_1_32_1"}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2894757","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2894757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:40Z","timestamp":1750273540000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2894757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,6,27]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,7,26]]}},"alternative-id":["10.1145\/2894757"],"URL":"https:\/\/doi.org\/10.1145\/2894757","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"type":"print","value":"1550-4832"},{"type":"electronic","value":"1550-4840"}],"subject":[],"published":{"date-parts":[[2016,6,27]]},"assertion":[{"value":"2014-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-06-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}