Imperial College London > Talks@ee.imperial > CAS Talks > Multiplication Without Multipliers: Algorithms, Applications, and Extensions

Multiplication Without Multipliers: Algorithms, Applications, and Extensions

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact George A Constantinides.

General multipliers are often the most power and area consuming part of digital signal processing systems. During the years, much research have focused on either reducing the number of multipliers or replacing the multipliers with networks of shifts, adders, and subtracters. In this tutorial, we consider the second approach: when can we replace general multipliers with these networks and how do we do it efficiently? Such realizations are often referred to as multiplierless. The most common example in literature is transposed direct form FIR filters, where the input data is multiplied with several constant coefficients. By utilizing the redundancy between the constants, one can reduce the resource requirements such that often the multiplications are no longer the major part of the computation. This problem can be generalized to also include several inputs and shifts in other dimensions (typically time). This leads to that similar approaches can be used for e.g. DCTs, DFTs, and computations in finite fields. We discuss the major classes of algorithms, namely subexpression sharing and adder graph approaches, and their suitability for different problems and optimization criteria. Furthermore, we discuss the area, time, and energy trade-offs, and the lower bounds associated with the different problems.

Biography: Oscar Gustafsson received the M.Sc., Tekn.Lic., Ph.D., and Docent degrees in 1998, 2000, 2003, and 2008, respectively, all from Linkoping University, Sweden. He is currently an assistant professor at the same university. Dr. Gustafsson’s research interests include joint design and implementation of DSP algorithms, especially digital filters, computer arithmetic, optimization, and implementation of error-correcting codes, all with a focus on low power consumption. He is a member of the VLSI Systems and Applications Technical Committee and the Digital Signal Processing Technical Committee of the IEEE Circuits and Systems Society. Dr. Gustafsson is a Technical Programme Committee member of the International Workshop on Power and Timing Modeling, Optimization and Simulation (2008-), and a Review Committee member of IEEE International Symposium of Circuits and Systems (2008-). He is the author or co-author of around 100 papers published in international journals and conferences.

This talk is part of the CAS Talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Changes to Talks@imperial | Privacy and Publicity