{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:25:20Z","timestamp":1750307120977,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["PTDC\/EIA-EIA\/103532\/2008"],"award-info":[{"award-number":["PTDC\/EIA-EIA\/103532\/2008"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>This article addresses the problem of finding the fewest numbers of addition and subtraction operations in the multiplication of a constant matrix with an input vector---a fundamental operation in many linear digital signal processing transforms. We first introduce an exact common subexpression elimination (CSE) algorithm that formalizes the minimization of the number of operations as a 0-1 integer linear programming problem. Since there are still instances that the proposed exact algorithm cannot handle due to the NP-completeness of the problem, we also introduce a CSE heuristic algorithm that iteratively finds the most common 2-term subexpressions with the minimum conflicts among the expressions. Furthermore, since the main drawback of CSE algorithms is their dependency on a particular number representation, we propose a hybrid algorithm that initially finds promising realizations of linear transforms using a numerical difference method, and then applies the proposed CSE algorithm to utilize the common subexpressions iteratively. The experimental results on a comprehensive set of instances indicate that the proposed approximate algorithms find competitive results with those of the exact CSE algorithm and obtain better solutions than the prominent, previously proposed, heuristics. It is also observed that our solutions yield significant area reductions in the design of linear transforms after circuit synthesis, compared to direct realizations of linear transforms.<\/jats:p>","DOI":"10.1145\/2071356.2071359","type":"journal-article","created":{"date-parts":[[2012,1,31]],"date-time":"2012-01-31T14:49:20Z","timestamp":1328021360000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Optimization Algorithms for the Multiplierless Realization of Linear Transforms"],"prefix":"10.1145","volume":"17","author":[{"given":"Levent","family":"Aksoy","sequence":"first","affiliation":[{"name":"INESC-ID"}]},{"given":"Eduardo","family":"Costa","sequence":"additional","affiliation":[{"name":"Universidade Cat\u00f3lica de Pelotas"}]},{"given":"Paulo","family":"Flores","sequence":"additional","affiliation":[{"name":"INESC-ID\/IST TU Lisbon"}]},{"given":"Jose","family":"Monteiro","sequence":"additional","affiliation":[{"name":"INESC-ID\/IST TU Lisbon"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1278480.1278588"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923242"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2009.10.001"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/774572.774638"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1629980"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Avizienis A. 1961. Signed-digit number representation for fast parallel arithmetic. IRE Trans. Electronic Comput. EC-10 389--400. Avizienis A. 1961. Signed-digit number representation for fast parallel arithmetic. IRE Trans. Electronic Comput. EC-10 389--400.","DOI":"10.1109\/TEC.1961.5219227"},{"volume-title":"A Davis-Putnam based enumeration algorithm for linear pseudo-Boolean optimization. Tech. rep","author":"Barth P.","key":"e_1_2_1_7_1","unstructured":"Barth , P. 1995. A Davis-Putnam based enumeration algorithm for linear pseudo-Boolean optimization. Tech. rep ., Max-Planck-Institut fur Informatik . Barth, P. 1995. A Davis-Putnam based enumeration algorithm for linear pseudo-Boolean optimization. Tech. rep., Max-Planck-Institut fur Informatik."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.168"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1984.1164433"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/240518.240555"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","DOI":"10.1109\/82.466647","article-title":"Use of minimum-adder multiplier blocks in FIR digital filters","author":"Dempster A.","year":"1995","unstructured":"Dempster , A. and Macleod , M. 1995 . Use of minimum-adder multiplier blocks in FIR digital filters . IEEE Trans. Circuits Syst. II 42, 9, 569--577. Dempster, A. and Macleod, M. 1995. Use of minimum-adder multiplier blocks in FIR digital filters. IEEE Trans. Circuits Syst. II 42, 9, 569--577.","journal-title":"IEEE Trans. Circuits Syst."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/78.815498"},{"volume-title":"Proceedings of IEEE European Conference on Circuit Theory and Design. IEEE","author":"Dempster A.","key":"e_1_2_1_13_1","unstructured":"Dempster , A. , Gustafsson , O. , and Coleman , J . 2003. Towards an algorithm for matrix multiplier blocks . In Proceedings of IEEE European Conference on Circuit Theory and Design. IEEE , Los Alamitos, CA, 1--4. Dempster, A., Gustafsson, O., and Coleman, J. 2003. Towards an algorithm for matrix multiplier blocks. In Proceedings of IEEE European Conference on Circuit Theory and Design. IEEE, Los Alamitos, CA, 1--4."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190014"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Ercegovac M. and Lang T. 2003. Digital Arithmetic. Morgan Kaufmann. Ercegovac M. and Lang T. 2003. Digital Arithmetic . Morgan Kaufmann.","DOI":"10.1016\/B978-155860798-9\/50011-7"},{"volume-title":"Proceedings of IEEE International Symposium on Circuits and Systems. IEEE","author":"Faust M.","key":"e_1_2_1_16_1","unstructured":"Faust , M. and Chang , C . -H. 2010. Minimal logic depth adder tree optimization for multiple constant multiplication . In Proceedings of IEEE International Symposium on Circuits and Systems. IEEE , Los Alamitos, CA, 457--460. Faust, M. and Chang, C.-H. 2010. Minimal logic depth adder tree optimization for multiple constant multiplication. In Proceedings of IEEE International Symposium on Circuits and Systems. IEEE, Los Alamitos, CA, 457--460."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60420-9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2007.903212"},{"volume-title":"Proceedings of IEEE International Symposium on Circuits and Systems. 73--76","author":"Gustafsson O.","key":"e_1_2_1_19_1","unstructured":"Gustafsson , O. , Dempster , A. , and Wanhammar , L . 2002. Extended results for minimum-adder constant integer multipliers . In Proceedings of IEEE International Symposium on Circuits and Systems. 73--76 . Gustafsson, O., Dempster, A., and Wanhammar, L. 2002. Extended results for minimum-adder constant integer multipliers. In Proceedings of IEEE International Symposium on Circuits and Systems. 73--76."},{"volume-title":"Proceedings of Nordic Signal Processing Symposium. 141--144","author":"Gustafsson O.","key":"e_1_2_1_20_1","unstructured":"Gustafsson , O. , Ohlsson , H. , and Wanhammar , L . 2004. Low-complexity constant coefficient matrix multiplication using a minimum spanning tree . In Proceedings of Nordic Signal Processing Symposium. 141--144 . Gustafsson, O., Ohlsson, H., and Wanhammar, L. 2004. Low-complexity constant coefficient matrix multiplication using a minimum spanning tree. In Proceedings of Nordic Signal Processing Symposium. 141--144."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","DOI":"10.1109\/82.539000","article-title":"Subexpression sharing in filters using canonic signed digit multipliers","author":"Hartley R.","year":"1996","unstructured":"Hartley , R. 1996 . Subexpression sharing in filters using canonic signed digit multipliers . IEEE Trans. Circuits Syst. II 43, 10, 677--688. Hartley, R. 1996. Subexpression sharing in filters using canonic signed digit multipliers. IEEE Trans. Circuits Syst. II 43, 10, 677--688.","journal-title":"IEEE Trans. Circuits Syst."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120725.1120953"},{"key":"e_1_2_1_23_1","first-page":"1444","article-title":"A fast recursive algorithm for computing the discrete cosine transform","volume":"35","author":"Hou H.","year":"1987","unstructured":"Hou , H. 1987 . A fast recursive algorithm for computing the discrete cosine transform . IEEE Trans. Acoustics, Speech, Signal Process. 35 , 10, 1444 -- 1461 . Hou, H. 1987. A fast recursive algorithm for computing the discrete cosine transform. IEEE Trans. Acoustics, Speech, Signal Process. 35, 10, 1444--1461.","journal-title":"IEEE Trans. Acoustics, Speech, Signal Process."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.108614"},{"volume-title":"Multiplication by an integer constant. Tech. rep","author":"Lefevre V.","key":"e_1_2_1_25_1","unstructured":"Lefevre , V. 2001. Multiplication by an integer constant. Tech. rep ., Institut National de Recherche en Informatique et en Automatique . Lefevre, V. 2001. Multiplication by an integer constant. Tech. rep., Institut National de Recherche en Informatique et en Automatique."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.980259"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.863621"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.378564"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.486662"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2008.2003004"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240234"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2005.852208"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008125221674"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071356.2071359","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2071356.2071359","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:48:24Z","timestamp":1750240104000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2071356.2071359"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2071356.2071359"],"URL":"https:\/\/doi.org\/10.1145\/2071356.2071359","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}