{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:08:48Z","timestamp":1760242128275,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2018,12,29]],"date-time":"2018-12-29T00:00:00Z","timestamp":1546041600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572109","11371003","61751110"],"award-info":[{"award-number":["61572109","11371003","61751110"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Special Fund for Bagui Scholars of Guangxi","award":["13000200230010"],"award-info":[{"award-number":["13000200230010"]}]},{"name":"Network and Data Security Key Laboratory of Sichuan Province Open Project","award":["NDSMS201603"],"award-info":[{"award-number":["NDSMS201603"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>In this paper, we address an NPN Boolean matching algorithm. The proposed structural difference signature (SDS) of a Boolean function significantly reduces the search space in the Boolean matching process. The paper analyses the size of the search space from three perspectives: the total number of possible transformations, the number of candidate transformations and the number of decompositions. We test the search space and run time on a large number of randomly generated circuits and Microelectronics Center of North Carolina (MCNC) benchmark circuits with 7\u201322 inputs. The experimental results show that the search space of Boolean matching is greatly reduced and the matching speed is obviously accelerated.<\/jats:p>","DOI":"10.3390\/sym11010027","type":"journal-article","created":{"date-parts":[[2018,12,31]],"date-time":"2018-12-31T07:22:30Z","timestamp":1546240950000},"page":"27","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A New Pairwise NPN Boolean Matching Algorithm Based on Structural Difference Signature"],"prefix":"10.3390","volume":"11","author":[{"given":"Juling","family":"Zhang","sequence":"first","affiliation":[{"name":"The School of Computer Science and Engineering, University of Xinjiang Finance and Economics, Urumqi 830012, China"},{"name":"The Big Data Research Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5133-0320","authenticated-orcid":false,"given":"Guowu","family":"Yang","sequence":"additional","affiliation":[{"name":"The Big Data Research Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China"},{"name":"Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China"}]},{"given":"William N. N.","family":"Hung","sequence":"additional","affiliation":[{"name":"Synopsys Inc., Mountain View, CA 94043, USA"}]},{"given":"Jinzhao","family":"Wu","sequence":"additional","affiliation":[{"name":"Guangxi Key Laboratory of Hybrid Computation and IC Design Analysis, Guangxi University for Nationalities, Nanning 530006, China"},{"name":"The School of Computer and Electronic Information, Guangxi University, Nanning 530004, China"}]},{"given":"Yixin","family":"Zhu","sequence":"additional","affiliation":[{"name":"The School of Computer Science and Engineering, University of Xinjiang Finance and Economics, Urumqi 830012, China"},{"name":"Network and Data Security Key Laboratory of Sichuan Province, University of Electronic Science and Technology of China, Chengdu 611731, China"}]}],"member":"1968","published-online":{"date-parts":[[2018,12,29]]},"reference":[{"key":"ref_1","first-page":"185","article-title":"On the number of symmetry types of Boolean functions of n variables","volume":"2","author":"Slepian","year":"1955","journal-title":"Can. J. Math."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Zhang, J., Yang, G., Hung, W.N.N., Liu, T., Song, X., and Perkowski, M.A. (2018). A group algebraic approach to NPN classification of Boolean functions. Theory Comput. Syst.","DOI":"10.1007\/s00224-018-9903-0"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3606","DOI":"10.1109\/TC.2016.2557329","article-title":"Computing affine equivalence classes of Boolean functions by group isomorphism","volume":"12","author":"Zhang","year":"2016","journal-title":"IEEE Trans. Comput."},{"key":"ref_4","unstructured":"Lai, Y.-T., Sastry, S., and Pedram, M. (1992, January 11\u201314). Boolean matching using binary decision diagrams with applications to logic synthesis and verification. Proceedings of the 1992 IEEE International Conference on Computer Design: VLSI in Computers and Processors, Cambridge, MA, USA."},{"key":"ref_5","first-page":"1","article-title":"An efficient NPN Boolean matching algorithm based on structural signature and Shannon expansion","volume":"6","author":"Zhang","year":"2018","journal-title":"Cluster Comput."},{"key":"ref_6","first-page":"1128","article-title":"Symmetry detection and Boolean matching utilizing a signature-based canonical form of Boolean functions","volume":"6","author":"Adbollahi","year":"2008","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Lee, S.Y., Lee, N.Z., and Jiang, J.H.R. (2018, January 5\u20138). Canonicalization of threshold logic representation and its applications. Proceedings of the International Conference on Computer-Aided Design, San Diego, CA, USA.","DOI":"10.1145\/3240765.3240785"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Asghar, A., Iqbal, M.M., Ahmed, W., Ali, M., Parvez, H., and Rashid, M. (2017, January 15\u201316). Logic algebra for exploiting shared SRAM-table based FPGAs for large LUT inputs. Proceedings of the Electrical Engineering and Computing Technologies, Karachi, Pakistan.","DOI":"10.1109\/INTELLECT.2017.8277632"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Soeken, M., Mishchenko, A., Petkovska, A., Sterin, B., Ienne, P., Brayton, R.K., and De Micheli, G. (2016, January 5\u20138). Heuristic NPN classification for large functions using AIGs and LEXSAT. Proceedings of the International Conference on Theory and Applications of Satisfiability Testing, Bordeaux, France.","DOI":"10.1007\/978-3-319-40970-2_14"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Huang, Z., Wang, L., Nasikovskiy, Y., and Mishchenko, A. (2013, January 9\u201311). Fast Boolean matching based on NPN classification. Proceedings of the International Conference on Field-Programmable Technology, Kyoto, Japan.","DOI":"10.1109\/FPT.2013.6718374"},{"key":"ref_11","unstructured":"Petkovska, A., Soeken, M., Micheli, G.D., Ienne, P., and Mishchenko, A. (September, January 29). Fast hierarchical NPN classification. Proceedings of the International Conference on Field Programmable Logic and Applications, Lausanne, Switzerland."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"805","DOI":"10.1109\/TCAD.2009.2016547","article-title":"A transform-parametric approach to Boolean matching","volume":"6","author":"Agosta","year":"2009","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."},{"key":"ref_13","unstructured":"Chen, K.C., and Yang, C.Y. (1993, January 12\u201314). Boolean matching algorithms. Proceedings of the International Symposium on VLSI Technology, Systems, and Applications, Taipei, Taiwan."},{"key":"ref_14","unstructured":"Kapoor, B. (1995, January 6\u20139). Improved technology mapping using a new approach to Boolean matching. Proceedings of the European Design and Test Conference, Paris, France."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"305","DOI":"10.3390\/sym3020305","article-title":"Symmetry groups for the decomposition of reversible computers, quantum computers, and computers in between","volume":"2","author":"Vos","year":"2011","journal-title":"Symmetry"},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Katebi, H., and Igor, I.L. (2010, January 8\u201312). Large-scale Boolean matching. Proceedings of the Conference on Design, Automation and Test in Europe, Dresden, Germany.","DOI":"10.1109\/DATE.2010.5456949"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Matsunaga, Y. (2015, January 19\u201322). Accelerating SAT-based Boolean matching for heterogeneous FPGAs using one-hot encoding and CEGAR technique. Proceedings of the Design Automation Conference of 20th Asia and South Pacifics, Chiba, Japan.","DOI":"10.1109\/ASPDAC.2015.7059014"},{"key":"ref_18","first-page":"1","article-title":"STABLE: Stress-Aware Boolean Matching to Mitigate BTI-Induced SNM Reduction in SRAM-Based FPGAs","volume":"99","author":"Ghaderi","year":"2018","journal-title":"IEEE Trans. Comput."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Cong, J., and Minkovich, K. (2007, January 18\u201320). Improved SAT-based Boolean matching using implicants for LUT-based FPGAs. Proceedings of the ACM\/sigda International Symposium on Field Programmable Gate Arrays, Monterey, CA, USA.","DOI":"10.1145\/1216919.1216944"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wang, K.H., Chan, C.M., and Liu, J.C. (2009, January 26\u201331). Simulation and SAT-based Boolean matching for large Boolean networks. Proceedings of the Design Automation Conference, San Francisco, CA, USA.","DOI":"10.1145\/1629911.1630016"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Moore, J., Fazel, K., Thornton, M.A., and Miller, D.M. (2006, January 29\u201330). Boolean function matching using Walsh Spectral decision diagrams. Proceedings of the Design, Applications, Integration and Software, Richardson, TX, USA.","DOI":"10.1109\/DCAS.2006.321050"},{"key":"ref_22","first-page":"53","article-title":"Logic circuit equivalence checking using Haar Spectral coefficients and partial BDDs","volume":"1","author":"Thornton","year":"2014","journal-title":"VLSI Des."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1011","DOI":"10.1109\/TCAD.2005.855951","article-title":"Linear cofactor relationships in Boolean functions","volume":"6","author":"Zhang","year":"2006","journal-title":"IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/1\/27\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:36:40Z","timestamp":1760197000000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/11\/1\/27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,29]]},"references-count":23,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2019,1]]}},"alternative-id":["sym11010027"],"URL":"https:\/\/doi.org\/10.3390\/sym11010027","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2018,12,29]]}}}