Approximation of multiple constant multiplications using minimum look-up tables on FPGA

In many digital signal processing (DSP) systems, computations can be carried out within a tolerable error range rather than finding the exact output, enabling significant reductions in area, delay, or power dissipation of the design. This paper addresses the problem of approximating the multiple constant multiplications (MCM) operation which frequently occurs in DSP applications. We consider the realization of constant multiplications using look-up tables (LUTs) on field programmable gate arrays (FPGA) and introduce an exact algorithm, called THETIS, that can find a minimum number of distinct LUTs required to realize the partial products of constant multiplications, satisfying an error constraint. Experimental results show that THETIS can achieve significant reductions in number of LUTs on MCM instances and its solutions lead to less complex filter designs on FPGA than those realized using original filter coefficients.