New Algorithms for Constant Coefficient Multiplication in Custom Hardware

Abstract

<p>Multiplying by known constants is a common operation in many digital signal processing (DSP) algorithms. High performance DSP systems are implemented in custom hardware, in which the designer has the ability to choose which logic elements will be used to perform the computation. By exploiting the properties of binary multiplication, it is possible to realize constant multiplication with fewer logic resources than required by a generic multiplier. In this thesis, we present several new algorithms for solving the constant multiplication problem - <em>given</em> a set of constants, <em>find</em> a low-cost logic circuit that realizes multiplication by each of the constants.</p> <p>In this thesis, a thorough analysis of the existing algorithms, the underlying frameworks, and the associated properties is provided. We also propose new strategies which are fundamentally different from the existing methods, such as the integration of a heuristic algorithm within an optimal algorithm. In our proposed optimal exhaustive algorithms, we introduce aggressive pruning methods to improve the compute efficiency (compared to existing optimal exhaustive algorithms). Our proposed heuristics attempt to address the weaknesses of the existing heuristics. By extending the analysis of prior work and providing new insight, we are often able to improve both the run time and the performance (in terms of minimizing logic resources).</p>