[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Multiplication by Constants

  • Chapter
  • First Online:
Application-Specific Arithmetic

  • 464 Accesses

Abstract

Multiplication by a constant is probably the most useful and best studied case of operator specialization, in particular for its importance in the construction of digital filters. There are two main families of constant multiplication techniques (shift-and-add and table-based), and there are several types of constants (integer/fixed-point, rational, or arbitrary real numbers). This chapter reviews the techniques that have been developed for each case. Some variants of the multiple constant multiplication problems are also addressed.

Being unable to trust my reasoning, I learnt by heart all the possible results of all the possible multiplications.Eugène Ionesco, La leçon

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 109.99
Price includes VAT (United Kingdom)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
GBP 139.99
Price includes VAT (United Kingdom)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Notes

  1. 1.

    http://www.spiral.net.

References

  1. IEEE Standard for Information technology– Telecommunications and information exchange between systems– Local and metropolitan area networks– Specific requirements– Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (WPANs). 2006.

    Google Scholar 

  2. Levent Aksoy, Paulo Flores, and José Monteiro. “Approximation of Multiple Constant Multiplications Using Minimum Look-Up Tables on FPGA”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2015, pp. 2884–2887.

    Google Scholar 

  3. Levent Aksoy, E. Gunes, and Paulo Flores. “An Exact Breadth- First Search Algorithm for the Multiple Constant Multiplications Problem”. In: NORCHIP (2008), pp. 41–46.

    Google Scholar 

  4. Levent Aksoy, E.O. Günes, and Paulo Flores. “Search Algorithms for the Multiple Constant Multiplications Problem: Exact and Approximate”. In: Microprocessors and Microsystems 34.5 (2010), pp. 151–162.

    Google Scholar 

  5. Ehud Artzy, James A. Hinds, and Harry J. Saal. “A Fast Division Technique for Constant Divisors”. In: Communications of the ACM 19 (1976), pp. 98–101.

    Google Scholar 

  6. A. V. Aho, S. C. Johnson, and J. D. Ullman. “Code generation for expressions with common subexpressions (Extended Abstract)”. In: ACM SIGACT-SIGPLAN Symposium on Principles on Programming Languages (POPL). 1976.

    Google Scholar 

  7. Levent Aksoy, Eduardo da Costa, Paulo Flores, and José Monteiro. “Optimization of Area in Digital FIR Filters using Gate-Level Metrics”. In: Design Automation Conference (DAC). ACM/IEEE, 2007, pp. 420–423.

    Google Scholar 

  8. Levent Aksoy, Eduardo da Costa, Paulo Flores, and José Monteiro. “Exact and Approximate Algorithms for the Optimization of Area and Delay in Multiple Constant Multiplications”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27.6 (2008), pp. 1013–1026.

    Google Scholar 

  9. Levent Aksoy, Eduardo Costa, Paulo Flores, and José Monteiro. “Design of Low-Power Multiple Constant Multiplications Using Low-Complexity Minimum Depth Operations”. In: Great Lakes Symposium on VLSI (GLSVLSI). ACM, 2011, pp. 79–84.

    Google Scholar 

  10. Levent Aksoy. “Optimization Algorithms for the Multiple Constant Multiplications Problem”. PhD thesis. Istanbul Technical University, 2009.

    Google Scholar 

  11. Algirdas Antanas Avižienis. “Signed-Digit Number Representations for Fast Parallel Arithmetic”. In: IRE Transactions on Electronic Computers EC-10.3 (1961), pp. 389–400.

    Google Scholar 

  12. Nicolas Brisebarre, Florent de Dinechin, and Jean-Michel Muller. “Integer and Floating-Point Constant Multipliers for FPGAs”. In: International Conference on Application-Specific Systems, Architectures and Processors (ASAP). IEEE, 2008, pp. 239–244.

    Google Scholar 

  13. Andrew D. Booth. “A Signed Binary Multiplication Technique”. In: The Quarterly Journal of Mechanics and Applied Mathematics (1951), pp. 236–240.

    Google Scholar 

  14. Ken D. Chapman. “Fast Integer Multipliers Fit in FPGAs”. In: Electronic Design News (1994).

    Google Scholar 

  15. Peter Cappello and Kenneth Steiglitz. “Some Complexity Issues in Digital Signal Processing”. In: IEEE Transactions onAcoustics, Speech and Signal Processing 32.5 (1984), pp. 1037–1041.

    Google Scholar 

  16. Süleyman S. Demirsoy, Andrew G. Dempster, and Izzet Kale. “Transition Analysis on FPGA for Multiplier-Block Based FIR Filter Structures”. In: International Symposium on Circuits and Systems (ISCAS). Vol. 2. IEEE, 2000, pp. 862–865.

    Google Scholar 

  17. Andrew G. Dempster, Süleyman S. Demirsoy, and Izzet Kale. “Designing Multiplier Blocks with Low Logic Depth”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2002, pp. 773–776.

    Google Scholar 

  18. Andrew G. Dempster, Oscar Gustafsson, and Jeffrey O. Coleman. “Towards an Algorithm for Matrix Multiplier Blocks”. In: European Conference on Circuit Theory and Design (ECCTD). 2003, pp. 1–4.

    Google Scholar 

  19. Florent de Dinechin, Silviu-Ioan Filip, Luc Forget, and Martin Kumm. “Table-Based versus Shift-And-Add Constant Multipliers for FPGAs”. In: Symposium on Computer Arithmetic (ARITH). IEEE, 2019.

    Google Scholar 

  20. Vassil Dimitrov, Laurent Imbert, and Andrew Zakaluzny. “Multiplication by a Constant is Sublinear”. In: Symposium on Computer Arithmetic (ARITH). IEEE, 2007, pp. 261–268.

    Google Scholar 

  21. Andrew G. Dempster and Malcolm D. Macleod. “Constant Integer Multiplication Using Minimum Adders”. In: IEE Proceedings of Circuits, Devices and Systems 141.5 (1994), pp. 407–413.

    Google Scholar 

  22. Andrew G. Dempster and Malcolm D. Macleod. “Use of Minimum-Adder Multiplier Blocks in FIR Digital Filters”. In: IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 42.9 (1995), pp. 569–577.

    Google Scholar 

  23. Mathias Faust and Chip-Hong Chang. “Minimal Logic Depth Adder Tree Optimization for Multiple Constant Multiplication”. In: International Symposium on Circuits and Systems (IS-CAS). IEEE, 2010, pp. 457–460.

    Google Scholar 

  24. Mathias Faust and Chip-Hong Chang. “Bit-parallel Multiple Constant Multiplication using Look-Up Tables on FPGA”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2011, pp. 657–660.

    Google Scholar 

  25. Oscar Gustafsson and Andrew G. Dempster. “On the Use of Multiple Constant Multiplication in Polyphase FIR Filters and Filter Banks”. In: Nordic Signal Processing Symposium (NOR-SIG). 2004, pp. 53–56.

    Google Scholar 

  26. Oscar Gustafsson, Andrew G. Dempster, and Lars Wanhammar. “Extended Results for Minimum-Adder Constant Integer Multipliers”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2002, pp. 73–76.

    Google Scholar 

  27. Oscar Gustafsson, Kenny Johansson, and Linda S. DeBrunner. “Techniques for Avoiding Sign-Extension in Multiple Constant Multiplication”. In: Asilomar Conference on Signals, Circuits and Systems. IEEE, 2009, pp. 740–743.

    Google Scholar 

  28. J. W. L. Glaisher. “Periods of Reciprocals of Integers Prime to 10”. In: Proceedings of the Cambridge Philosophical Society 3 (1878), pp. 185–206.

    Google Scholar 

  29. Oscar Gustafsson, Henrik Ohlsson, and Lars Wanhammar. “Low-Complexity Constant Coefficient Matrix Multiplication Using a Minimum Spanning Tree Approach”. In: 6th Nordic Signal Processing Symposium (NORSIG). 2004, pp. 141–144.

    Google Scholar 

  30. Oscar Gustafsson and Fahad Qureshi. “Addition Aware Quantization for Low Complexity and High Precision Constant Multiplication”. In: IEEE Signal Processing Letters 17.2 (2010), pp. 173–176.

    Google Scholar 

  31. Gurobi Optimization Inc. Gurobi Website. 2022. URL: http://www.gurobi.com.

  32. Oscar Gustafsson, Andrew G. Dempster, Kenny Johansson, and Malcolm D. Macleod. “Simplified Design of Constant Coefficient Multipliers”. In: Circuits, Systems, and Signal Processing 25.2 (2006), pp. 225–251.

    Google Scholar 

  33. Oscar Gustafsson. “A Difference Based Adder Graph Heuristic for Multiple Constant Multiplication Problems”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2007, pp. 1097–1100.

    Google Scholar 

  34. Oscar Gustafsson. “Lower Bounds for Constant Multiplication Problems”. In: IEEE Transactions on Circuits and Systems II: Express Briefs 54.11 (2007), pp. 974–978.

    Google Scholar 

  35. Oscar Gustafsson. “Towards Optimal Multiple Constant Multiplication: A Hypergraph Approach”. In: Asilomar Conference on Signals, Circuits and Systems. IEEE, 2008, pp. 1805–1809.

    Google Scholar 

  36. Remi Garcia and Anastasia Volkova. “Toward the Multiple Constant Multiplication at Minimal Hardware Cost”. In: IEEE Transactions on Circuits and Systems I: Regular Papers (2023), pp. 1–13.

    Google Scholar 

  37. Rémi Garcia, Anastasia Volkova, and Martin Kumm. “Truncated Multiple Constant Multiplication with Minimal Number of Full Adders”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2022, pp. 263–267.

    Google Scholar 

  38. Oscar Gustafsson and Lars Wanhammar. “A Novel Approach to Multiple Constant Multiplication Using Minimum Spanning Trees”. In: IEEE Midwest Symposium on Circuits and Systems (MWSCAS). Vol. 3. 2002.

    Google Scholar 

  39. Oscar Gustafsson and Lars Wanhammar. “Low-Complexity and High-Speed Constant Multiplications for Digital Filters Using Carry-Save Arithmetic”. In: Digital Filters. InTech, 2011.

    Google Scholar 

  40. Martin Hardieck, M Kumm, Konrad Möller, and Peter Zipf. “Reconfigurable Convolutional Kernels for Neural Networks on FPGAs”. In: International Symposium on Field Programmable Gate Arrays (FPGA). ACM, 2019, pp. 43–52.

    Google Scholar 

  41. Richard Hartley. “Optimization of Canonic Signed Digit Multipliers for Filter Design”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 1991, pp. 1992–1995.

    Google Scholar 

  42. Richard I. Hartley. “Subexpression Sharing in Filters Using Canonic Signed Digit Multipliers”. In: IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing 43.10 (1996), pp. 677–688.

    Google Scholar 

  43. Kai Hwang. Computer Arithmetic: Principles, Architecture, and Design. Wiley-Interscience, 1979.

    Google Scholar 

  44. Intel Stratix 10 Variable Precision DSP Blocks User Guide. Intel Corporation. 2018.

    Google Scholar 

  45. Miriam Guadalupe Cruz Jimenez, Uwe Meyer Baese, and Gordana Jovanovic Dolecek. “Theoretical Lower Bounds for Parallel Pipelined Shift-and-Add Constant Multiplications with N-Input Arithmetic Operators”. In: EURASIP Journal on Advances in Signal Processing 2017.1 (2017), pp. 1–13.

    Google Scholar 

  46. Kenny Johansson, Oscar Gustafsson, and Lars Wanhammar. “A Detailed Complexity Model for Multiple Constant Multiplication and an Algorithm to Minimize the Complexity”. In: European Conference on Circuit Theory and Design. Vol. 3. 2005, III/465–III/468 vol. 3.

    Google Scholar 

  47. Kenny Johansson, Oscar Gustafsson, and Lars Wanhammar. “Bit-Level Optimization of Shift-and-Add Based FIR Filters”. In: International Conference on Electronics, Circuits and Systems, (ICECS). IEEE, 2007, pp. 713–716.

    Google Scholar 

  48. Kenny Johansson. “Low Power and Low Complexity Shift-and-Add Based Computations”. PhD thesis. Linköping Studies in Science and Technology, 2008.

    Google Scholar 

  49. Martin Kumm, Martin Hardieck, and Peter Zipf. “Optimization of Constant Matrix Multiplication with Low Power and High Throughput”. In: IEEE Transactions on Computers 66.12 (2017), pp. 2072–2080.

    Google Scholar 

  50. Andrew Kinane, Valentin Muresan, and Noel O’Connor. “Optimisation of Constant Matrix Multiplication Operation Hardware Using a Genetic Algorithm”. In: Lecture Notes in Computer Science. Springer, 2006, pp. 296–307.

    Google Scholar 

  51. Andrew Kinane, Valentin Muresan, and Noel O’Connor. “Towards an Optimised VLSI Design Algorithm for the Constant Matrix Multiplication Problem”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2006, pp. 5111–5114.

    Google Scholar 

  52. Donald Knuth. The Art of Computer Programming, vol.2: Seminumerical Algorithms. 3rd ed. Addison Wesley, 1997.

    Google Scholar 

  53. Martin Kumm, Peter Zipf, Mathias Faust, and Chip-Hong Chang. “Pipelined Adder Graph Optimization for High Speed Multiple Constant Multiplication”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2012, pp. 49–52.

    Google Scholar 

  54. Martin Kumm, Diana Fanghänel, K Möller, Peter Zipf, and Uwe Meyer-Baese. “FIR Filter Optimization for Video Processing on FPGAs”. In: Springer EURASIP Journal on Advances in Signal Processing (2013), pp. 1–18.

    Google Scholar 

  55. Martin Kumm, Martin Hardieck, Jens Willkomm, Peter Zipf, and Uwe Meyer-Baese. “Multiple Constant Multiplication with Ternary Adders”. In: International Conference on Field Programmable Logic and Application (FPL). 2013, pp. 1–8.

    Google Scholar 

  56. Martin Kumm, Oscar Gustafsson, Mario Garrido, and Peter Zipf. “Optimal Single Constant Multiplication using Ternary Adders”. In: IEEE Transactions on Circuits and Systems II: Express Briefs 65.7 (2016), pp. 928–932.

    Google Scholar 

  57. Martin Kumm. “Multiple Constant Multiplication Optimizations for Field Programmable Gate Arrays”. PhD thesis. Springer Wiesbaden, 2015.

    Google Scholar 

  58. Martin Kumm. “Optimal Constant Multiplication using Integer Linear Programming”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2018.

    Google Scholar 

  59. Martin Kumm and Peter Zipf. “High Speed Low Complexity FPGA-Based FIR Filters Using Pipelined Adder Graphs”. In: International Conference on Field-Programmable Technology (FPT). IEEE, 2011, pp. 1–4.

    Google Scholar 

  60. Martin Kumm and Peter Zipf. “Hybrid Multiple Constant Multiplication for FPGAs”. In: International Conference on Electronics, Circuits and Systems, (ICECS). 2012, pp. 556–559.

    Google Scholar 

  61. Shuo-Yen Robert Li. “Fast Constant Division Routines”. In: IEEE Transactions on Computers C-34.9 (1985), pp. 866–869.

    Google Scholar 

  62. Xin Lou, Ya Jun Yu, and Pramod Kumar Meher. “High-Speed Multiplier Block Design Based on Bit-Level Critical Path Optimization”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2014, pp. 1308–1311.

    Google Scholar 

  63. Xin Lou, Ya Jun Yu, and Pramod Kumar Meher. “Fine-Grained Critical Path Analysis and Optimization for Area-Time Efficient Realization of Multiple Constant Multiplications”. In: IEEE Transactions on Circuits and Systems I 62.3 (2015), pp. 863–872.

    Google Scholar 

  64. Malcolm D. Macleod and Andrew G. Dempster. “Common Subexpression Elimination Algorithm for Low-Cost Multiplierless Implementation of Matrix Multipliers”. In: Electronics Letters 40.11 (2004), pp. 651–652.

    Google Scholar 

  65. Ahmed Can Mert, Hasan Azgın, Ercan Kalalı, and İlker Hamzaoğlu. “Efficient multiple constant multiplication using DSP blocks in FPGA”. In: International Conference on Field Programmable Logic and Application (FPL). IEEE, 2018.

    Google Scholar 

  66. Uwe Meyer-Baese, Jiajia Chen, Chip Hong Chang, and Andrew G. Dempster. “A Comparison of Pipelined RAG-n and DA FPGA-based Multiplierless Filters”. In: IEEE Asia Pacific Conference on Circuits and Systems (APCCAS). 2006, pp. 1555–1558.

    Google Scholar 

  67. Uwe Meyer-Baese. Digital Signal Processing with Field Programmable Gate Arrays. 4th ed. Springer, 2014.

    Google Scholar 

  68. Konrad Möller, Martin Kumm, Marco Kleinlein, and Peter Zipf. “Reconfigurable Constant Multiplication for FPGAs”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 36.6 (2017), pp. 927–937.

    Google Scholar 

  69. Konrad Möller, Martin Kumm, Mario Garrido, and Peter Zipf. “Optimal Shift Reassignment in Reconfigurable Constant Multiplication Circuits”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 37.3 (2018), pp. 710–714.

    Google Scholar 

  70. Konrad Möller. “Run-time Reconfigurable Constant Multiplication on Field Programmable Gate Arrays”. PhD thesis. Kassel University Press, 2017.

    Google Scholar 

  71. M. Potkonjak, M. B. Srivastava, and A. P. Chandrakasan. “Multiple Constant Multiplications: Efficient and Versatile Framework and Algorithms for Exploring Common Subexpression Elimination”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 15.2 (1996), pp. 151–165.

    Google Scholar 

  72. Narges Mohammadi Sarband, Oscar Gustafsson, and Mario Garrido. “Using Transposition to Efficiently Solve Constant Matrix-Vector Multiplication and Sum of Product Problems”. In: Journal of Signal Processing Systems 54.11 (July 2020), pp. 1–15.

    Google Scholar 

  73. P. Srinivasan and F.E. Petry. “Constant-division algorithms”. In: IEE Proc. Computers and Digital Techniques 141.6 (1994), pp. 334–340.

    Google Scholar 

  74. Dong Shi and Ya Jun Yu. “Design of Linear Phase FIR Filters With High Probability of Achieving Minimum Number of Adders”. In: IEEE Transactions on Circuits and Systems I: Regular Papers 58.1 (2011), pp. 126–136.

    Google Scholar 

  75. Richard H. Turner, Tim Courtney, and Roger Woods. “Implementation of Fixed DSP Functions using the Reduced Coefficient Multiplier”. In: IEEE International Conference on Acoustics, Speech, and Signal Processing 2 (2001), pp. 881–884.

    Google Scholar 

  76. Peter Tummeltshammer, James C. Hoe, and Markus Püschel. “Time-Multiplexed Multiple-Constant Multiplication”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 26.9 (2007), pp. 1551–1563.

    Google Scholar 

  77. David E. Troncoso Romero, Uwe Meyer-Baese, and Gordana Jovanovic Dolecek. “On the Inclusion of Prime Factors to Calculate the Theoretical Lower Bounds in Multiplierless Single Constant Multiplications”. In: EURASIP Journal on Advances in Signal Processing (2014).

    Google Scholar 

  78. Jason Thong and Nicola Nicolici. “A Novel Optimal Single Constant Multiplication Algorithm”. In: Design Automation Conference (DAC). ACM/IEEE, 2010.

    Google Scholar 

  79. Jason Thong and Nicola Nicolici. “An Optimal and Practical Approach to Single Constant Multiplication”. In: IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30.9 (2011), pp. 1373–1386.

    Google Scholar 

  80. Keith D. Tocher. “Techniques of Multiplication and Division for Automatic Binary Computers”. In: The Quarterly Journal of Mechanics and Applied Mathematics 11.3 (1958), pp. 364–384.

    Google Scholar 

  81. Anastasia Volkova, Matei Iştoan, Florent de Dinechin, and Thibault Hilaire. “Towards Hardware IIR Filters Computing Just Right: Direct Form I Case Study”. In: IEEE Transactions on Computers 68.4 (2019).

    Google Scholar 

  82. Yevgen Voronenko and Markus Püschel. “Multiplierless Multiple Constant Multiplication”. In: ACM Transactions on Algorithms 3.2 (2007).

    Google Scholar 

  83. Michael J. Wirthlin. “Constant Coefficient Multiplication Using Look-Up Tables”. In: Journal of VLSI Signal Processing 36.1 (2004), pp. 7–15.

    Google Scholar 

  84. Yao Fu, Ephrem Wu, Ashish Sirasao, Sedny Attia, Kamran Khan, and Ralph Wittig. Deep Learning with INT8 Optimization on Xilinx Devices (White Paper). Tech. rep. Xilinx, Inc., 2017.

    Google Scholar 

  85. Wen Bin Ye and Ya Jun Yu. “Switching Activity Analysis and Power Estimation for Multiple Constant Multiplier Block of FIR Filters”. In: International Symposium on Circuits and Systems (ISCAS). IEEE, 2011, pp. 145–148.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CITI laboratory, INSA-Lyon, Villeurbanne, France

    Florent de Dinechin

  2. Fulda University of Applied Sciences, Fulda, Germany

    Martin Kumm

Authors
  1. Florent de Dinechin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Martin Kumm
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

Copyright information

© 2024 Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

de Dinechin, F., Kumm, M. (2024). Multiplication by Constants. In: Application-Specific Arithmetic. Springer, Cham. https://doi.org/10.1007/978-3-031-42808-1_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-42808-1_12

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-42807-4

  • Online ISBN: 978-3-031-42808-1

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation