This paper addresses the direct optimization of pipelined adder graphs (PAGs) for high speed multiple constant multiplication (MCM). The optimization opportunities are described and a definition of the pipelined multiple constant multiplication (PMCM) problem is given. It is shown that the PMCM problem is a generalization of the MCM problem with limited adder depth (AD). A novel algorithm to solve the PMCM problem heuristically, called RPAG, is presented. RPAG outperforms previous methods which are based on pipelining the solutions of conventional MCM algorithms. A flexible cost evaluation is used which enables the optimization for FPGA or ASIC targets on high or low abstraction levels. Results for both technologies are given and compared with the most recent methods. Even for the special case of limited AD it is shown that RPAG often produces better results compared to the prominent Hcubalgorithm with minimal total AD constraint.

The research on optimization of Multiple Constant Multiplication (MCM) during the last two decades has been focusing mainly on common subexpression elimination and reduced adder graph algorithms when bit-parallel computation is required. The advancement of FPGA technology enables the implementation of complex MCM instances on FPGA, but the shift-and-add network implementation does not make full use of the fundamental resources of FPGA, like the Look-Up Tables (LUT). Since bit-serial implementation optimized for FPGA is slow, an attempt for bit-parallel LUT-based implementation for single constant multiplication has been made. This paper extends this LUT-based method to multiple constant multiplications. It presents an interesting insight and unexpected outcome that the maximal number of LUTs required can be limited far below the theoretical number by mere enumeration without considering the legitimacy of all possible output combinations. Simulation results show that the required logic slices are comparable to the traditional adder-based MCM optimization methods while the delay is reduced by approximately 33%. The advantages are more prominent with increasing number of constants and the bit width used for their representation.

Research on optimization of fixed coefficient FIR filters modeled as Multiple Constant Multiplication (MCM) has been ongoing for two decades. An analysis of Minimal Signed Digit (MSD) reveals that potential good solutions are omitted by Common Subexpression Elimination (CSE) algorithms as they are hidden in the MSD representations. Some CSE algorithms ensure that all coefficients are implemented at minimal Logic Depth (LD) which is advantageous from power saving perspective. Imposing this requirement on a graph dependant (GD) algorithm reduces the search space as well as the runtime. It also eliminates the long critical path of GD algorithm. This paper presents a minimal logic depth GD algorithm which requires no lookup table. Simulation results show that it has lower number of adders than CSE algorithms while having the minimal logic depth. For all filters tested, it consumes less switching power than the latest LD constrained GD methods based on the Glitch Path Count and Glitch Path Score metrics.

A thorough analysis of the paper above revealed several controversial arguments about the superiority of binary representation over canonical signed digits (CSD) for common subexpression elimination (CSE). It was improper to model the number of logic operators (LO) required after CSE as a linear sum of independently weighted numbers of nonzero bits, common subexpressions and unpaired bits. The logic depth (LD) penalty of binary CSE had been deemphasized by the errors in the reported LD. This comment corrects the LD of contention resolution algorithm, and points out some contradictions with reference to the latest experimentation of binary, CSD and minimal signed digit number representations for CSE. Upon correcting the error in the reported filter lengths for different stopband attenuations of digital advanced mobile phone system specification, the LO and LD data of the CSE algorithms compared in the above paper are recalculated using the corrected filter coefficient sets.

Over the last two decades, fixed coefficient FIR filters were generally optimized by minimizing the number of adders required to implement the multiplier block in the transposed direct form filter structure. In this paper, an optimization method for the structural adders in the transposed tapped delay line is proposed. Although additional registers are required, an optimal trade-off can be made such that the overall combinational logic is reduced. For a majority of taps, the delay through the structural adder is shortened except for the last tap. The one full adder delay increase for the last optimized tap is tolerable as it does not fall in the critical path in most cases. The criterion for which area reduction is possible is analytically derived and an area reduction of up to 4.5% for the structural adder block of three benchmark filters is estimated theoretically. The saving is more prominent as the number of taps grows. Actual synthesis results obtained by synopsys design compiler with 0.18 mum TSMC CMOS libraries show a total area reduction of up to 13.13% when combined with common subexpression elimination. In all examples, up to 11.96% of the total area saved were due to the reduction of structural adder costs by our proposed method.