{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:58Z","timestamp":1750309438973,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NRRP MUR program funded by the EU - NGEU","award":["PE00000014"],"award-info":[{"award-number":["PE00000014"]}]},{"DOI":"10.13039\/501100011033","name":"Spanish Agencia Estatal de Investigaci\u00f3n","doi-asserted-by":"crossref","award":["PID2020-112581GB-C21 (MOTION)"],"award-info":[{"award-number":["PID2020-112581GB-C21 (MOTION)"]}],"id":[{"id":"10.13039\/501100011033","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003030","name":"AGAUR","doi-asserted-by":"crossref","award":["2021-SGR-01419 (ALBCOM)"],"award-info":[{"award-number":["2021-SGR-01419 (ALBCOM)"]}],"id":[{"id":"10.13039\/501100003030","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MIUR, Project","award":["INdAM, GNCS 2023"],"award-info":[{"award-number":["INdAM, GNCS 2023"]}]},{"name":"Project","award":["INdAM, GNCS 2024"],"award-info":[{"award-number":["INdAM, GNCS 2024"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2025,1,31]]},"abstract":"<jats:p>Bi-decomposition rewrites logic functions as the composition of simpler components. It is related to Boolean division, where a given function is rewritten as the product of a divisor and a quotient, but bi-decomposition can be defined for any Boolean operation of two operands. The key questions are how to find a good divisor and then how to compute the quotient. In this article, we select the divisor by approximation of the original function and then characterize by an incompletely specified function the full flexibility of the quotient for each binary operator. We target area-driven exact bi-decomposition, and we apply it to the bi-decomposition of Sum-of-Products (SOP) forms. We report experiments that exhibit significant gains in literals of SOP forms when rewritten as bi-decompositions with respect to the product operator. This suggests the application of this framework to other logic forms and binary operations, both for exact and approximate implementations.<\/jats:p>","DOI":"10.1145\/3698879","type":"journal-article","created":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T15:45:05Z","timestamp":1728402305000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Area-driven Boolean bi-decomposition by function approximation"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0263-5221","authenticated-orcid":false,"given":"Anna","family":"Bernasconi","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0469-4201","authenticated-orcid":false,"given":"Valentina","family":"Ciriani","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Milano, Milano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8114-250X","authenticated-orcid":false,"given":"Jordi","family":"Cortadella","sequence":"additional","affiliation":[{"name":"Universitat Politecnica de Catalunya, Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-8397-7580","authenticated-orcid":false,"given":"Marco","family":"Costa","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Pisa, Pisa, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9671-8804","authenticated-orcid":false,"given":"Tiziano","family":"Villa","sequence":"additional","affiliation":[{"name":"Universit\u00e0 degli Studi di Verona, Verona, Italy"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_1_2_2","DOI":"10.1109\/TC.2008.165"},{"key":"e_1_3_1_3_2","first-page":"72","volume-title":"Proceedings of the Euromicro Conference on Digital System Design, DSD","author":"Bernasconi Anna","year":"2015","unstructured":"Anna Bernasconi, Robert K. Brayton, Valentina Ciriani, Gabriella Trucco, and Tiziano Villa. 2015. Bi-decomposition using boolean relations. In Proceedings of the Euromicro Conference on Digital System Design, DSD. IEEE Computer Society, 72\u201378."},{"key":"e_1_3_1_4_2","first-page":"214","volume-title":"Further Improvements in the Boolean Domain","author":"Bernasconi Anna","year":"2018","unstructured":"Anna Bernasconi, Robert K. Brayton, Valentina Ciriani, Gabriella Trucco, and Tiziano Villa. 2018. Synthesis of complemented circuits. In Further Improvements in the Boolean Domain. Cambridge Scholars Publishing, 214\u2013239."},{"key":"e_1_3_1_5_2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1109\/DSD.2014.21","volume-title":"Proceedings of the 17th Euromicro Conference on Digital System Design (DSD\u201914)","author":"Bernasconi Anna","year":"2014","unstructured":"Anna Bernasconi and Valentina Ciriani. 2014. 2-SPP approximate synthesis for error tolerant applications. In Proceedings of the 17th Euromicro Conference on Digital System Design (DSD\u201914). 411\u2013418."},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1109\/DSD.2014.21","volume-title":"Proceedings of the 17th Euromicro Conference on Digital System Design (DSD\u201914)","author":"Bernasconi Anna","year":"2014","unstructured":"Anna Bernasconi and Valentina Ciriani. 2014. 2-SPP approximate synthesis for error tolerant applications. In Proceedings of the 17th Euromicro Conference on Digital System Design (DSD\u201914). 411\u2013418."},{"key":"e_1_3_1_7_2","first-page":"580","volume-title":"Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201920)","author":"Bernasconi Anna","year":"2020","unstructured":"Anna Bernasconi, Valentina Ciriani, Jordi Cortadella, and Tiziano Villa. 2020. Computing the full quotient in bi-decomposition by approximation. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201920). IEEE, 580\u2013585."},{"key":"e_1_3_1_8_2","first-page":"1655","volume-title":"Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201919)","author":"Bernasconi Anna","year":"2019","unstructured":"Anna Bernasconi, Valentina Ciriani, and Tiziano Villa. 2019. Approximate logic synthesis by symmetrization. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201919). 1655\u20131660."},{"doi-asserted-by":"publisher","key":"e_1_3_1_9_2","DOI":"10.1109\/TC.2020.3043476"},{"key":"e_1_3_1_10_2","first-page":"586","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201910)","author":"Choudhury Mihir","year":"2010","unstructured":"Mihir Choudhury and Kartik Mohanram. 2010. Bi-decomposition of large Boolean functions using blocking edge graphs. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201910). 586\u2013591."},{"doi-asserted-by":"publisher","key":"e_1_3_1_11_2","DOI":"10.1109\/TCAD.2003.811447"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","first-page":"545","DOI":"10.1109\/ASPDAC.1997.600332","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Debnath D.","year":"1997","unstructured":"D. Debnath and T. Sasao. 1997. An optimization of AND-OR-EXOR three-level networks. In Proceedings of the Asia and South Pacific Design Automation Conference. 545\u2013550."},{"key":"e_1_3_1_13_2","first-page":"45","volume-title":"Proceedings of the 3rd International Workshop on the Applications of the Reed-Muller Expansion in Circuit Design","author":"Debnath D.","year":"1997","unstructured":"D. Debnath and T. Sasao. 1997. Exclusive-OR of two sum-of-products expressions: Simplification and an upper bound on the number of products. In Proceedings of the 3rd International Workshop on the Applications of the Reed-Muller Expansion in Circuit Design. 45\u201360."},{"issue":"10","key":"e_1_3_1_14_2","first-page":"1001","article-title":"Minimization of AND-OR-EXOR three-level networks with AND gate sharing","volume":"80","author":"Debnath D.","year":"1997","unstructured":"D. Debnath and T. Sasao. 1997. Minimization of AND-OR-EXOR three-level networks with AND gate sharing. IEICE Trans. Inf. Syst. E80-D, 10 (1997), 1001\u20131008.","journal-title":"IEICE Trans. Inf. Syst."},{"key":"e_1_3_1_15_2","first-page":"69","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Debnath D.","year":"1998","unstructured":"D. Debnath and T. Sasao. 1998. A heuristic algorithm to design AND-OR-EXOR three-level networks. In Proceedings of the Asia and South Pacific Design Automation Conference. 69\u201374."},{"key":"e_1_3_1_16_2","first-page":"99","volume-title":"Proceedings of the IEEE International Symposium on Multiple-Valued Logic","author":"Debnath D.","year":"1999","unstructured":"D. Debnath and T. Sasao. 1999. Multiple\u2013valued minimization to optimize PLAs with output EXOR gates. In Proceedings of the IEEE International Symposium on Multiple-Valued Logic. 99\u2013104."},{"key":"e_1_3_1_17_2","first-page":"251","volume-title":"Proceedings of the International Workshop on Logic Synthesis","author":"Dubrova E.","year":"1999","unstructured":"E. Dubrova and P. Ellervee. 1999. A fast algorithm for three-level logic optimization. In Proceedings of the International Workshop on Logic Synthesis. 251\u2013254."},{"doi-asserted-by":"publisher","key":"e_1_3_1_18_2","DOI":"10.1049\/el:19950377"},{"key":"e_1_3_1_19_2","first-page":"209","volume-title":"Proceedings of the 3rd International Workshop on the Applications of the Reed-Muller Expansion in Circuit Design","author":"Dubrova E.","year":"1997","unstructured":"E. Dubrova, D. Miller, and J. Muzio. 1997. AOXMIN: A three-level heuristic AND-OR-XOR minimizer for boolean functions. In Proceedings of the 3rd International Workshop on the Applications of the Reed-Muller Expansion in Circuit Design. 209\u2013218."},{"key":"e_1_3_1_20_2","first-page":"37","volume-title":"Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in circuit Design","author":"Dubrova E.","year":"1999","unstructured":"E. Dubrova, D. Miller, and J. Muzio. 1999. AOXMIN-MV: A heuristic algorithm for AND-OR-XOR minimization. In Proceedings of the 4th International Workshop on the Applications of the Reed Muller Expansion in circuit Design. 37\u201354."},{"key":"e_1_3_1_21_2","volume-title":"Computer and Intractability: A Guide to the Theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computer and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman & Company."},{"doi-asserted-by":"publisher","key":"e_1_3_1_22_2","DOI":"10.1007\/978-3-319-99322-5_7"},{"key":"e_1_3_1_23_2","first-page":"1458","volume-title":"Proceedings of the Design, Automation and Test in Europe (DATE\u201909)","author":"Kravets Victor N.","year":"2009","unstructured":"Victor N. Kravets and Alan Mishchenko. 2009. Sequential logic synthesis using symbolic bi-decomposition. In Proceedings of the Design, Automation and Test in Europe (DATE\u201909). IEEE, 1458\u20131463."},{"key":"e_1_3_1_24_2","first-page":"773","volume-title":"Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201918)","author":"Lai Yung-An","year":"2018","unstructured":"Yung-An Lai, Chia-Chun Lin, Chia-Cheng Wu, Yung-Chih Chen, and Chun-Yao Wang. 2018. Efficient synthesis of approximate threshold logic circuits with an error rate guarantee. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition (DATE\u201918). 773\u2013778."},{"key":"e_1_3_1_25_2","first-page":"636","volume-title":"Proceedings of the 45th Design Automation Conference (DAC\u201908)","author":"Lee Ruei-Rung","year":"2008","unstructured":"Ruei-Rung Lee, Jie-Hong R. Jiang, and Wei-Lun Hung. 2008. Bi-decomposing large boolean functions via interpolation and satisfiability solving. In Proceedings of the 45th Design Automation Conference (DAC\u201908). 636\u2013641."},{"key":"e_1_3_1_26_2","first-page":"143","volume-title":"Proceedings of the Great Lakes Symposium on VLSI","author":"Machado Lucas","year":"2017","unstructured":"Lucas Machado and Jordi Cortadella. 2017. Boolean decomposition for AIG optimization. In Proceedings of the Great Lakes Symposium on VLSI. ACM, 143\u2013148."},{"key":"e_1_3_1_27_2","first-page":"628","volume-title":"Proceedings of the IEEE International Conference on Computer Design: VLSI in Computer & Processors (ICCD\u201991)","author":"Malik A. A.","year":"1991","unstructured":"A. A. Malik, D. Harrison, and R. K. Brayton. 1991. Three-level decomposition with application to PLDs. In Proceedings of the IEEE International Conference on Computer Design: VLSI in Computer & Processors (ICCD\u201991). 628\u2013633."},{"doi-asserted-by":"publisher","key":"e_1_3_1_28_2","DOI":"10.1145\/157485.165069"},{"key":"e_1_3_1_29_2","first-page":"779","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913)","author":"Miao Jin","year":"2013","unstructured":"Jin Miao, A. Gerstlauer, and M. Orshansky. 2013. Approximate logic synthesis under general error magnitude and frequency constraints. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201913). 779\u2013786."},{"key":"e_1_3_1_30_2","first-page":"504","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201914)","author":"Miao Jin","year":"2014","unstructured":"Jin Miao, A. Gerstlauer, and M. Orshansky. 2014. Multi-level approximate logic synthesis under general error constraints. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201914). 504\u2013510."},{"key":"e_1_3_1_31_2","first-page":"103","volume-title":"Proceedings of the ACM\/IEEE 38th Design Automation Conference (DAC\u201901)","author":"Mishchenko A.","year":"2001","unstructured":"A. Mishchenko, B. Steinbach, and M. Perkowski. 2001. An algorithm for bi-decomposition of logic functions. In Proceedings of the ACM\/IEEE 38th Design Automation Conference (DAC\u201901). 103\u2013108."},{"doi-asserted-by":"publisher","key":"e_1_3_1_32_2","DOI":"10.1109\/ISQED.2019.8697679"},{"key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"1118","DOI":"10.1109\/ISCAS.1990.112313","volume-title":"Proceedings of the IEEE International Symposium on Circuits and Systems","author":"Perkowski Marek","year":"1990","unstructured":"Marek Perkowski. 1990. A program for exact synthesis of three-level NAND networks. In Proceedings of the IEEE International Symposium on Circuits and Systems. 1118\u20131121."},{"key":"e_1_3_1_34_2","first-page":"143","volume-title":"Proceedings of the IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion","author":"Perkowski Marek","year":"1995","unstructured":"Marek Perkowski. 1995. A new representation of strongly unspecified switching functions and its application to multi-level AND\/OR\/EXOR synthesis. In Proceedings of the IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion. 143\u2013151."},{"doi-asserted-by":"publisher","key":"e_1_3_1_35_2","DOI":"10.1109\/TC.1981.1675861"},{"key":"e_1_3_1_36_2","first-page":"8:11\u20138:20","volume-title":"Proceedings of the International Workshop on Logic Synthesis","author":"Sasao T.","year":"1995","unstructured":"T. Sasao. 1995. A design method for AND-OR-EXOR three level networks. In Proceedings of the International Workshop on Logic Synthesis. 8:11\u20138:20."},{"key":"e_1_3_1_37_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-1385-4","volume-title":"Representation of Discrete Functions","author":"Sasao T.","year":"1996","unstructured":"T. Sasao. 1996. OR-AND-OR three-level networks. In Representation of Discrete Functions, T. Sasao and M. Fujita (Eds.). Kluwier Academic."},{"volume-title":"Proceedings of the International Workshop on Logic and Synthesis (IWLS\u201997)","author":"Sasao Tsutomu","unstructured":"Tsutomu Sasao and Jon T. Butler. [n.d.]. On bi-decompositions of logic functions. In Proceedings of the International Workshop on Logic and Synthesis (IWLS\u201997).","key":"e_1_3_1_38_2"},{"key":"e_1_3_1_39_2","first-page":"1","volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201911)","author":"Shin Doochul","year":"2011","unstructured":"Doochul Shin and S. K. Gupta. 2011. A new circuit simplification method for error tolerant applications. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201911). 1\u20136."},{"key":"e_1_3_1_40_2","first-page":"957","volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201910)","author":"Shin Doochul","year":"2010","unstructured":"Doochul Shin and Sandeep K. Gupta. 2010. Approximate logic synthesis for error tolerant applications. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE\u201910). 957\u2013960."},{"doi-asserted-by":"publisher","key":"e_1_3_1_41_2","DOI":"10.1109\/TCAD.2018.2890532"},{"key":"e_1_3_1_42_2","first-page":"74","volume-title":"Proceedings of the 56th Annual Design Automation Conference (DAC\u201919)","author":"Testa Eleonora","year":"2019","unstructured":"Eleonora Testa, Mathias Soeken, Luca G. Amar\u00f9, and Giovanni De Micheli. 2019. Reducing the multiplicative complexity in logic networks for cryptography and security applications. In Proceedings of the 56th Annual Design Automation Conference (DAC\u201919). 74."},{"doi-asserted-by":"publisher","key":"e_1_3_1_43_2","DOI":"10.23919\/DATE48585.2020.9116467"},{"key":"e_1_3_1_44_2","first-page":"1367","volume-title":"Proceedings of the Design, Automation and Test in Europe, (DATE\u201913)","author":"Venkataramani Swagath","year":"2013","unstructured":"Swagath Venkataramani, Kaushik Roy, and Anand Raghunathan. 2013. Substitute-and-simplify: A unified design paradigm for approximate and quality configurable circuits. In Proceedings of the Design, Automation and Test in Europe, (DATE\u201913). 1367\u20131372."},{"key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1145\/2228360.2228504","volume-title":"Proceedings of the 49th ACM\/EDAC\/IEEE Design Automation Conference (DAC\u201912)","author":"Venkataramani S.","year":"2012","unstructured":"S. Venkataramani, A. Sabne, V. Kozhikkottu, K. Roy, and A. Raghunathan. 2012. SALSA: Systematic logic synthesis of approximate circuits. In Proceedings of the 49th ACM\/EDAC\/IEEE Design Automation Conference (DAC\u201912). 796\u2013801."},{"key":"e_1_3_1_46_2","first-page":"675","volume-title":"Boolean Methods and Models in Mathematics, Computer Science and Engineering, Encyclopedia of Mathematics and its Applications 134","author":"Villa Tiziano","year":"2010","unstructured":"Tiziano Villa, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. 2010. Synthesis of multi-level boolean networks. In Boolean Methods and Models in Mathematics, Computer Science and Engineering, Encyclopedia of Mathematics and its Applications 134, Yves Crama and Peter L. Hammer (Eds.). Cambridge University Press, 675\u2013722."},{"key":"e_1_3_1_47_2","first-page":"59","volume-title":"Proc. of the Asia and South Pacific Design Automation Conference","author":"Yamashita S.","year":"1998","unstructured":"S. Yamashita, H. Sawada, and A. Nagoya. 1998. New methods to find optimal non-disjoint bi-decompositions. In Proc. of the Asia and South Pacific Design Automation Conference. 59\u201368."},{"key":"e_1_3_1_48_2","volume-title":"Logic Synthesis and Optimization Benchmarks User Guide Version 3.0","author":"Yang S.","year":"1991","unstructured":"S. Yang. 1991. Logic Synthesis and Optimization Benchmarks User Guide Version 3.0. User Guide. Microelectronic Center."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698879","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698879","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:44Z","timestamp":1750295384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698879"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1,31]]}},"alternative-id":["10.1145\/3698879"],"URL":"https:\/\/doi.org\/10.1145\/3698879","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2024-06-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-18","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}