TY - JOUR

T1 - ILP-based bitwidth-aware subexpression sharing for area minimization in multiple constant multiplication

AU - Lin, Bu Ching

AU - Huang, Juinn-Dar

AU - Jou, Jing Yang

PY - 2014

Y1 - 2014

N2 - The notion of multiple constant multiplication (MCM) is extensively adopted in digital signal processing (DSP) applications such as finite impulse filter (FIR) designs. A set of adders is utilized to replace regular multipliers for the multiplications between input data and constant filter coefficients. Though many algorithms have been proposed to reduce the total number of adders in an MCM block for area minimization, they do not consider the actual bitwidth of each adder, which may not estimate the hardware cost well enough. Therefore, in this article we propose a bitwidth-aware MCM optimization algorithm that focuses on minimizing the total number of adder bits rather than the adder count. It first builds a subexpression graph based on the given coefficients, derives a set of constraints for adder bitwidth minimization, and then optimally solves the problem through integer linear programming (ILP). Experimental results show that the proposed algorithm can effectively reduce the required adder bit count and outperforms the existing state-of-the-art techniques.

AB - The notion of multiple constant multiplication (MCM) is extensively adopted in digital signal processing (DSP) applications such as finite impulse filter (FIR) designs. A set of adders is utilized to replace regular multipliers for the multiplications between input data and constant filter coefficients. Though many algorithms have been proposed to reduce the total number of adders in an MCM block for area minimization, they do not consider the actual bitwidth of each adder, which may not estimate the hardware cost well enough. Therefore, in this article we propose a bitwidth-aware MCM optimization algorithm that focuses on minimizing the total number of adder bits rather than the adder count. It first builds a subexpression graph based on the given coefficients, derives a set of constraints for adder bitwidth minimization, and then optimally solves the problem through integer linear programming (ILP). Experimental results show that the proposed algorithm can effectively reduce the required adder bit count and outperforms the existing state-of-the-art techniques.

KW - Bitwidth

KW - Finite impulse response (FIR) filter

KW - Integer linear programming (ILP)

KW - Multiple constant multiplication (MCM)

UR - http://www.scopus.com/inward/record.url?scp=84897401872&partnerID=8YFLogxK

U2 - 10.1587/transfun.E97.A.931

DO - 10.1587/transfun.E97.A.931

M3 - Article

AN - SCOPUS:84897401872

SN - 0916-8508

VL - E97-A

SP - 931

EP - 939

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 4

ER -