{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T17:10:07Z","timestamp":1741281007940,"version":"3.38.0"},"reference-count":22,"publisher":"Walter de Gruyter GmbH","issue":"4-5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,8,26]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p xml:lang=\"en\">Two-level logic minimization is a well-established process that efficiently minimizes functions described in the Sum-of-Products (SOP) form. Current two-level SOP minimizes, like Espresso and Boom, produce optimum or near-optimum results regarding the SOP size. However, in this article we show that an SOP minimization conducted in the standard, multi-output way, significantly worsens the result of the subsequent multi-level synthesis, especially for sparsely-specified functions, regardless of the optimization process and the tool used. In conclusion, we propose using a single-output two-level SOP minimization for sparsely specified functions. In this way, the obtained circuits are sometimes multiple times smaller, while no significant deterioration has been observed for any other functions.<\/jats:p>","DOI":"10.1515\/itit-2024-0071","type":"journal-article","created":{"date-parts":[[2025,2,8]],"date-time":"2025-02-08T03:50:49Z","timestamp":1738986649000},"page":"103-113","source":"Crossref","is-referenced-by-count":0,"title":["Structural bias in synthesis of sparsely-specified functions"],"prefix":"10.1515","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5306-6343","authenticated-orcid":false,"given":"Petr","family":"Fi\u0161er","sequence":"first","affiliation":[{"name":"Faculty of Information Technology, Department of Digital Design , Czech Technical University in Prague , Prague , Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3221-7370","authenticated-orcid":false,"given":"Jan","family":"Schmidt","sequence":"additional","affiliation":[{"name":"Faculty of Information Technology, Department of Digital Design , Czech Technical University in Prague , Prague , Czech Republic"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2025,2,10]]},"reference":[{"key":"2025030616183065575_j_itit-2024-0071_ref_001","doi-asserted-by":"crossref","unstructured":"R. K. Brayton, A. L. Sangiovanni-Vincentelli, C. T. McMullen, and G. D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Norwell, MA, USA, Kluwer Academic Publishers, 1984.","DOI":"10.1007\/978-1-4613-2821-6"},{"key":"2025030616183065575_j_itit-2024-0071_ref_002","doi-asserted-by":"crossref","unstructured":"R. Rudell and A. Sangiovanni-Vincentelli, \u201cMultiple-valued minimization for PLA optimization,\u201d IEEE Trans. Comput. Aided Des. Integrated Circ. Syst., vol. 6, no. 5, pp. 727\u2013750, 1987. https:\/\/doi.org\/10.1109\/tcad.1987.1270318.","DOI":"10.1109\/TCAD.1987.1270318"},{"key":"2025030616183065575_j_itit-2024-0071_ref_003","doi-asserted-by":"crossref","unstructured":"J. Hlavi\u010dka and P. Fi\u0161er, \u201cBOOM \u2013 a heuristic Boolean minimizer,\u201d in IEEE\/ACM International Conference on Computer Aided Design. ICCAD 2001. IEEE\/ACM Digest of Technical Papers (Cat. No.01CH37281), 2001, pp.\u00a0439\u2013442.","DOI":"10.1109\/ICCAD.2001.968667"},{"key":"2025030616183065575_j_itit-2024-0071_ref_004","unstructured":"P. Fi\u0161er and J. Hlavi\u010dka, \u201cBOOM \u2013 a heuristic Boolean minimizer,\u201d Comput. Inf., vol.\u00a022, no.\u00a01, p.\u00a019, 2003."},{"key":"2025030616183065575_j_itit-2024-0071_ref_005","doi-asserted-by":"crossref","unstructured":"P. Fi\u0161er and H. Kub\u00e1tov\u00e1, \u201cFlexible two-level Boolean minimizer BOOM-II and its applications,\u201d in Euromicro Conference on Digital System Design, Architectures, Methods and Tools, 2006, p.\u00a0369.","DOI":"10.1109\/DSD.2006.53"},{"key":"2025030616183065575_j_itit-2024-0071_ref_006","unstructured":"E. Sentovich, et al.., \u201cSIS: a system for sequential circuit synthesis,\u201d EECS Department, University of California, Berkeley, Tech. Rep. UCB\/ERL M92\/41, 1992."},{"key":"2025030616183065575_j_itit-2024-0071_ref_007","unstructured":"A. Mishchenko, et al.., \u201cBerkeley Logic Synthesis and Verification Group, ABC: A System for Sequential Synthesis and Verification,\u201d 2012, https:\/\/people.eecs.berkeley.edu\/~alanmi\/abc\/."},{"key":"2025030616183065575_j_itit-2024-0071_ref_022","doi-asserted-by":"crossref","unstructured":"R. Brayton and A. Mishchenko, \u201cABC: an academic industrial-strength verification tool,\u201d in Proceedings of the 22nd International Conference on Computer Aided Verification (CAV\u201910), Edinburgh, UK., Berlin, Heidelberg, Springer-Verlag, 2010, pp. 24\u201340.","DOI":"10.1007\/978-3-642-14295-6_5"},{"key":"2025030616183065575_j_itit-2024-0071_ref_008","unstructured":"G. D. Hachtel and F. Somenzi, Logic Synthesis and Verification Algorithms, Norwell, MA, USA, Kluwer Academic Publishers, 1996."},{"key":"2025030616183065575_j_itit-2024-0071_ref_009","unstructured":"S. Yang, \u201cLogic synthesis and optimization benchmarks user guide: version 3.0,\u201d Tech. Rep., MCNC Technical Report, 1991."},{"key":"2025030616183065575_j_itit-2024-0071_ref_010","unstructured":"K. McElvain, \u201cIWLS\u201993 benchmark set: version 4.0,\u201d Tech. Rep., 1993."},{"key":"2025030616183065575_j_itit-2024-0071_ref_011","unstructured":"L. Amaru, \u201cThe EPFL combinational benchmark suite,\u201d Integrated Systems Laboratory, EPFL, Lausanne, Switzerland, Tech. Rep., 2016."},{"key":"2025030616183065575_j_itit-2024-0071_ref_012","unstructured":"P. Fi\u0161er and J. Schmidt, \u201cA comprehensive set of logic synthesis and optimization examples,\u201d in 12th. Int. Workshop on Boolean Problems (IWSBP), 2016, pp.\u00a0151\u2013158."},{"key":"2025030616183065575_j_itit-2024-0071_ref_013","unstructured":"M. Nazemi, G. Pasandi, and M. Pedram, \u201cNullaNet: training deep neural networks for reduced-memory-access inference,\u201d ArXiv, 2018. https:\/\/doi.org\/10.48550\/arXiv.1807.08716."},{"key":"2025030616183065575_j_itit-2024-0071_ref_014","doi-asserted-by":"crossref","unstructured":"M. Nazemi, G. Pasandi, and M. Pedram, \u201cEnergy-efficient, low-latency realization of neural networks through boolean logic minimization,\u201d in 24th Asia and South Pacific Design Automation Conference, 2019, pp.\u00a0274\u2013279.","DOI":"10.1145\/3287624.3287722"},{"key":"2025030616183065575_j_itit-2024-0071_ref_015","unstructured":"P. Fi\u0161er and J. Schmidt, \u201cSmall but nasty logic synthesis examples,\u201d in 8th. Int. Workshop on Boolean Problems (IWSBP), 2008, pp.\u00a0183\u2013189."},{"key":"2025030616183065575_j_itit-2024-0071_ref_016","doi-asserted-by":"crossref","unstructured":"P. Fi\u0161er, J. Schmidt, and J. Balc\u00e1rek, \u201cSources of bias in EDA tools and its influence,\u201d in IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems, 2014, pp.\u00a0258\u2013261.","DOI":"10.1109\/DDECS.2014.6868803"},{"key":"2025030616183065575_j_itit-2024-0071_ref_017","doi-asserted-by":"crossref","unstructured":"C.-C. Chi and J.-H. R. Jiang, \u201cLogic synthesis of binarized neural networks for efficient circuit implementation,\u201d in 37th IEEE\/ACM International Conference on Computer-Aided Design, 2018, pp.\u00a01\u20137.","DOI":"10.1145\/3240765.3240822"},{"key":"2025030616183065575_j_itit-2024-0071_ref_018","doi-asserted-by":"crossref","unstructured":"L. Deng, \u201cThe MNIST database of handwritten digit images for machine learning research,\u201d IEEE Signal Process. Mag., vol.\u00a029, no.\u00a06, pp.\u00a0141\u2013142, 2012. https:\/\/doi.org\/10.1109\/msp.2012.2211477.","DOI":"10.1109\/MSP.2012.2211477"},{"key":"2025030616183065575_j_itit-2024-0071_ref_019","doi-asserted-by":"crossref","unstructured":"H. Savoj and R. K. Brayton, \u201cThe use of observability and external don\u2019t cares for the simplification of multi-level networks,\u201d in Proceedings of the 27th ACM\/IEEE Design Automation Conference, DAC \u201990, New York, NY, USA, Association for Computing Machinery, 1991, pp.\u00a0297\u2013301.","DOI":"10.1145\/123186.123280"},{"key":"2025030616183065575_j_itit-2024-0071_ref_020","doi-asserted-by":"crossref","unstructured":"K.-H. Chang, V. Bertacco, I. L. Markov, and A. Mishchenko, \u201cLogic synthesis and circuit customization using extensive external don\u2019t-cares,\u201d ACM Trans. Des. Autom. Electron. Syst., vol. 15, no. 3, pp. 1\u201324, 2010. https:\/\/doi.org\/10.1145\/1754405.1754411.","DOI":"10.1145\/1754405.1754411"},{"key":"2025030616183065575_j_itit-2024-0071_ref_021","doi-asserted-by":"crossref","unstructured":"T. Sasao and J. Butler, \u201cWorst and best irredundant sum-of-products expressions,\u201d IEEE Trans. Comput., vol.\u00a050, no.\u00a09, pp.\u00a0935\u2013948, 2001. https:\/\/doi.org\/10.1109\/12.954508.","DOI":"10.1109\/12.954508"}],"container-title":["it - Information Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0071\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0071\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,6]],"date-time":"2025-03-06T16:18:59Z","timestamp":1741277939000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/itit-2024-0071\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,1]]},"references-count":22,"journal-issue":{"issue":"4-5","published-online":{"date-parts":[[2025,3,3]]},"published-print":{"date-parts":[[2024,8,26]]}},"alternative-id":["10.1515\/itit-2024-0071"],"URL":"https:\/\/doi.org\/10.1515\/itit-2024-0071","relation":{},"ISSN":["1611-2776","2196-7032"],"issn-type":[{"type":"print","value":"1611-2776"},{"type":"electronic","value":"2196-7032"}],"subject":[],"published":{"date-parts":[[2024,8,1]]}}}