{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:32:16Z","timestamp":1756384336854,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T00:00:00Z","timestamp":1594252800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T00:00:00Z","timestamp":1594252800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sign Process Syst"],"published-print":{"date-parts":[[2020,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work, we present an approach to alleviate the potential benefit of adder graph algorithms by solving the transposed form of the problem and then transposing the solution. The key contribution is a systematic way to obtain the transposed realization with a minimum number of cascaded adders subject to the input realization. In this way, wide and low constant matrix multiplication problems, with sum of products as a special case, which are normally exceptionally time consuming to solve using adder graph algorithms, can be solved by first transposing the matrix and then transposing the solution. Examples show that while the relation between the adder depth of the solution to the transposed problem and the original problem is not straightforward, there are many cases where the reduction in adder cost will more than compensate for the potential increase in adder depth and result in implementations with reduced power consumption compared to using sub-expression sharing algorithms, which can both solve the original problem directly in reasonable time and guarantee a minimum adder depth.<\/jats:p>","DOI":"10.1007\/s11265-020-01560-z","type":"journal-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T12:05:05Z","timestamp":1594296305000},"page":"1075-1089","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Using Transposition to Efficiently Solve Constant Matrix-Vector Multiplication and Sum of Product Problems"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7074-3676","authenticated-orcid":false,"given":"Narges Mohammadi","family":"Sarband","sequence":"first","affiliation":[]},{"given":"Oscar","family":"Gustafsson","sequence":"additional","affiliation":[]},{"given":"Mario","family":"Garrido","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,9]]},"reference":[{"issue":"11","key":"1560_CR1","doi-asserted-by":"publisher","first-page":"974","DOI":"10.1109\/TCSII.2007.903212","volume":"54","author":"O Gustafsson","year":"2007","unstructured":"Gustafsson, O. (2007). Lower bounds for constant multiplication problems. IEEE Transactions on Circuits and Systems II, 54(11), 974\u2013978.","journal-title":"IEEE Transactions on Circuits and Systems II"},{"key":"1560_CR2","doi-asserted-by":"crossref","unstructured":"Meher, P.K., Chang, C.H., Gustafsson, O., Vinod, A.P., & Faust, M. (2017). Shift-add circuits for constant multiplications. In Meher, P.K., & Stouraitis, T. (Eds.) Arithmetic circuits for DSP applications (pp. 33\u201376). Wiley.","DOI":"10.1002\/9781119206804.ch2"},{"key":"1560_CR3","unstructured":"Dempster, A.G., Gustafsson, O., & Coleman, J.O. (2003). Towards an algorithm for matrix multiplier blocks. In Proceedings of european conference circuit theory design (pp. 1\u20134)."},{"issue":"11","key":"1560_CR4","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1049\/el:20040436","volume":"40","author":"M Macleod","year":"2004","unstructured":"Macleod, M., & Dempster, A. (2004). Common subexpression elimination algorithm for low-cost multiplierless implementation of matrix multipliers. Electronics Letters, 40(11), 651\u2013652.","journal-title":"Electronics Letters"},{"issue":"10","key":"1560_CR5","doi-asserted-by":"publisher","first-page":"1271","DOI":"10.1109\/TC.2005.168","volume":"54","author":"N Boullis","year":"2005","unstructured":"Boullis, N., & Tisserand, A. (2005). Some optimizations of hardware multiplication by constant matrices. IEEE Transactions on Computers, 54(10), 1271\u20131282.","journal-title":"IEEE Transactions on Computers"},{"key":"1560_CR6","doi-asserted-by":"crossref","unstructured":"Gustafsson, O., Khursheed, K., Imran, M., & Wanhammar, L. (2010). Generalized overlapping digit patterns for multi-dimensional sub-expression sharing. In IEEE International conference green circuits systems (pp. 65\u201368).","DOI":"10.1109\/ICGCS.2010.5543096"},{"issue":"12","key":"1560_CR7","doi-asserted-by":"publisher","first-page":"2072","DOI":"10.1109\/TC.2017.2701365","volume":"66","author":"M Kumm","year":"2017","unstructured":"Kumm, M., Hardieck, M., & Zipf, P. (2017). Optimization of constant matrix multiplication with low power and high throughput. IEEE Transactions on Computers, 66(12), 2072\u20132080.","journal-title":"IEEE Transactions on Computers"},{"key":"1560_CR8","doi-asserted-by":"crossref","unstructured":"Gustafsson, O. (2007). A difference based adder graph heuristic for multiple constant multiplication problems. In Proceedings of IEEE international symposium on circuits and systems (pp. 1097\u20131100): IEEE.","DOI":"10.1109\/ISCAS.2007.378201"},{"issue":"10","key":"1560_CR9","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/82.539000","volume":"43","author":"RI Hartley","year":"1996","unstructured":"Hartley, R.I. (1996). Subexpression sharing in filters using canonic signed digit multipliers. IEEE transactions on circuits and systems ii, 43(10), 677\u2013688.","journal-title":"IEEE transactions on circuits and systems ii"},{"issue":"2","key":"1560_CR10","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1109\/43.486662","volume":"15","author":"M Potkonjak","year":"1996","unstructured":"Potkonjak, M., Srivastava, M.B., & Chandrakasan, A.P. (1996). Multiple constant multiplications: Efficient and versatile framework and algorithms for exploring common subexpression elimination. IEEE transactions on computers-aided design integrated circuits systems, 15(2), 151\u2013165.","journal-title":"IEEE transactions on computers-aided design integrated circuits systems"},{"key":"1560_CR11","unstructured":"Dempster, A.G., & Macleod, M.D. (2004). Using all signed-digit representations to design single integer multipliers using subexpression elimination. In Proceedings of IEEE international symposium on circuits and systems, (Vol. 3 pp. 165\u2013168): IEEE."},{"issue":"2","key":"1560_CR12","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s00034-005-2505-5","volume":"25","author":"O Gustafsson","year":"2006","unstructured":"Gustafsson, O., Dempster, A.G., Johansson, K., Macleod, M.D., & Wanhammar, L. (2006). Simplified design of constant coefficient multipliers. Circuits, Systems, and Signal Processing, 25(2), 225\u2013251.","journal-title":"Circuits, Systems, and Signal Processing"},{"issue":"9","key":"1560_CR13","doi-asserted-by":"publisher","first-page":"1353","DOI":"10.1109\/TVLSI.2008.2003004","volume":"17","author":"J Thong","year":"2009","unstructured":"Thong, J., & Nicolici, N. (2009). Time-efficient single constant multiplication based on overlapping digit patterns. IEEE Transactions on Very Large Scale Integration, 17(9), 1353\u20131357.","journal-title":"IEEE Transactions on Very Large Scale Integration"},{"key":"1560_CR14","doi-asserted-by":"crossref","unstructured":"Gustafsson, O. (2008). Towards optimal multiple constant multiplication: a hypergraph approach. In Proceedings of Asilomar conference on signals, systems, and computers (pp. 1805\u20131809): IEEE.","DOI":"10.1109\/ACSSC.2008.5074738"},{"issue":"6","key":"1560_CR15","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1109\/TCAD.2008.923242","volume":"27","author":"L Aksoy","year":"2008","unstructured":"Aksoy, L., Da Costa, E., Flores, P., & Monteiro, J. (2008). Exact and approximate algorithms for the optimization of area and delay in multiple constant multiplications. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(6), 1013\u20131026.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"issue":"5","key":"1560_CR16","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1109\/TCSII.2018.2823780","volume":"65","author":"M Kumm","year":"2018","unstructured":"Kumm, M. (2018). Optimal constant multiplication using integer linear programming. IEEE Transactions on Circuits and Systems II, 65(5), 567\u2013571.","journal-title":"IEEE Transactions on Circuits and Systems II"},{"key":"1560_CR17","doi-asserted-by":"crossref","unstructured":"Kumm, M., Zipf, P., Faust, M., & Chang, C. (2012). Pipelined adder graph optimization for high speed multiple constant multiplication. In Proceedings of IEEE international symposium on circuits and systems (pp. 49\u201352).","DOI":"10.1109\/ISCAS.2012.6272072"},{"key":"1560_CR18","doi-asserted-by":"crossref","unstructured":"Sarband, N.M., Gustafsson, O., & Garrido, M. (2018). Obtaining minimum depth sum of products from multiple constant multiplication. In Proceedings of IEEE workshop on signal processing systems (pp. 1\u20136).","DOI":"10.1109\/SiPS.2018.8598365"},{"key":"1560_CR19","unstructured":"Gustafsson, O., Ohlsson, H., & Wanhammar, L. (2001). Minimum-adder integer multipliers using carry-save adders. In Proceedings of IEEE international symposium on circuits and systems, (Vol. 2 pp. 709\u2013712): IEEE."},{"key":"1560_CR20","unstructured":"Gustafsson, O., Dempster, A.G., & Wanhammar, L. (2004). Multiplier blocks using carry-save adders. In Proceedings of IEEE international symposium on circuits and systems, (Vol. 2 pp. II\u2013473): IEEE."},{"key":"1560_CR21","doi-asserted-by":"crossref","unstructured":"Gustafsson, O., & Wanhammar, L. (2011). Low-complexity and high-speed constant multiplications for digital filters using carry-save arithmetic. In Marquez, F.P.G. (Ed.) Digital filters (pp. 241\u2013256). IntechOpen.","DOI":"10.5772\/16081"},{"key":"1560_CR22","doi-asserted-by":"crossref","unstructured":"Kumm, M., Hardieck, M., Willkomm, J., Zipf, P., & Meyer-Baese, U. (2013). Multiple constant multiplication with ternary adders. In Proceedings of international conference on field-programmable logic applications (pp. 1\u20138): IEEE.","DOI":"10.1109\/FPL.2013.6645543"},{"issue":"7","key":"1560_CR23","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1109\/TCSII.2016.2631630","volume":"65","author":"M Kumm","year":"2018","unstructured":"Kumm, M., Gustafsson, O., Garrido, M., & Zipf, P. (2018). Optimal single constant multiplication using ternary adders. IEEE Transactions on Circuits and Systems II, 65(7), 928\u2013932.","journal-title":"IEEE Transactions on Circuits and Systems II"},{"issue":"1","key":"1560_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02920362","volume":"6","author":"JL Bordewijk","year":"1957","unstructured":"Bordewijk, J.L. (1957). Inter-reciprocity applied to electrical networks. Applied Scientific Research, 6(1), 1\u201374.","journal-title":"Applied Scientific Research"},{"issue":"3","key":"1560_CR25","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1109\/TCT.1971.1083285","volume":"18","author":"B Bhattacharyya","year":"1971","unstructured":"Bhattacharyya, B., & Swamy, M. (1971). Network transposition and its application in synthesis. IEEE Transactions on Circuit Theory, 18(3), 394\u2013397.","journal-title":"IEEE Transactions on Circuit Theory"},{"key":"1560_CR26","doi-asserted-by":"crossref","unstructured":"Schmid, H. (2002). Circuit transposition using signal-flow graphs. In Proceedings of IEEE international symposium on circuits and systems, (Vol. 2 pp. 25\u201328).","DOI":"10.1109\/ISCAS.2002.1010914"},{"key":"1560_CR27","unstructured":"Gustafsson, O., & Dempster, A.G. (2004). On the use of multiple constant multiplication in polyphase FIR filters and filter banks. In Proceedings of IEEE nordic signal processing symposium (pp. 53\u201356)."},{"key":"1560_CR28","unstructured":"Gustafsson, O., Johansson, H., & Wanhammar, L. (2001). An MILP approach for the design of linear-phase FIR filters with minimum number of signed-power-of-two terms. In Proceedings of european conference on circuit theory and design."}],"container-title":["Journal of Signal Processing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11265-020-01560-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11265-020-01560-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11265-020-01560-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,8]],"date-time":"2021-07-08T23:40:05Z","timestamp":1625787605000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11265-020-01560-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,9]]},"references-count":28,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["1560"],"URL":"https:\/\/doi.org\/10.1007\/s11265-020-01560-z","relation":{},"ISSN":["1939-8018","1939-8115"],"issn-type":[{"type":"print","value":"1939-8018"},{"type":"electronic","value":"1939-8115"}],"subject":[],"published":{"date-parts":[[2020,7,9]]},"assertion":[{"value":"30 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 December 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}