Efficient Arithmetic Sum-of-Product (SOP) based Multiple Constant Multiplication (MCM) for FFT Conference Paper uri icon

abstract

  • In this paper, we present an arithmetic sum-of-products (SOP) based realization of the general Multiple Constant Multiplication (MCM) algorithm. We alsoprqpose an enhanced SOP based algorithm, which uses Partial Max-SAT (PMSAT) to further optimize the SOP. The enhanced algorithm attempts to reduce the number of rows (partial products) of the SOP, by i) shifting coefficients to realize other coefficients when possible, ii) exploring multiple implementations of each coefficient using a Minimal Signed Digit (MSD) format and iii) exploiting the mutual exclusiveness within certain groups of partial products. Hardware implementations of the Fast Fourier Transform (FFT) algorithm require the incoming data to be multiplied by one of several constant coefficients. We test/validate it for FFT, which Is an important problem. We compare our SOP-based architectures with the best existing implementation of MCM for FFT (which utilizes a cascade of adders), and show that our approaches show a significant Improvement in area and delay. Our architecture was synthesized using 65nm technology libraries. 2010 IEEE.

name of conference

  • 2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

published proceedings

  • 2010 IEEE AND ACM INTERNATIONAL CONFERENCE ON COMPUTER-AIDED DESIGN (ICCAD)

author list (cited authors)

  • Karkala, V., Wanstrath, J., Lacour, T., & Khatri, S. P.

citation count

  • 5

complete list of authors

  • Karkala, Vinay||Wanstrath, Joseph||Lacour, Travis||Khatri, Sunil P

publication date

  • November 2010