Multiple constant multiplication

What is it about?

The hardware complexity of FIR filters is dominated by MCM. The latter is an arithmetic operation that multiplies a set of fixed-point constants with the same fixed-point variable X. To be efficiently implemented, i.e., rapid, compact, and low-power, MCM must avoid costly multipliers. The hardware alternative will be multiplierless, using only additions, subtractions, and left-shifts. We assume that addition and subtraction have the same area/speed cost, and that the shift is costless since it can be realized without any gates, i.e., just by using hardwiring. Therefore, the MCM problem is defined as the process of finding the minimum number of additions, and/or the minimum number of cascaded additions forming the critical path. The computational complexity of MCM is conjectured to be NP-hard [1]. But because the solution-space to explore is so huge, optimal solutions require excessive runtime and become impractical even for MCM operations of a medium complexity [1][2]. Only MCM heuristics can react in a reasonable amount of time, producing however, suboptimal solutions.

Featured Image

Why is it important?

Contrary to the claims in the literature, in this work we provide evidences that Hcub is not so unbeatable in area as it might appear. The reason is that Hcub solution requires a set of adders with longer bit-lengths. For high order filters, the total number of bit-adders outweighs the benefit of the lower adder-cost. Besides, we prove that Hcub is not near-optimal in cost for constant bitlength greater than 20 bits. We also prove that Hcub adder-depth increases with increasing filter length. In addition to the RADIX-2r advantages cited earlier, the central point of this paper is to demonstrate the superiority of RADIX-2r over the existing heuristics in speed, power, and area particularly. For this purpose, a number of benchmark FIR filters of different complexities have been implemented in 65nm CMOS. We also introduce the exact analytic bound of RADIX-2r at bit-level, which is a very strong result in MCM.

Perspectives