McMaster University
New Algorithms for Constant Coefficient Multiplication in Custom Hardware
Abstract
dc:description.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>
Degree
thesis:*- Department dc:contributor.department
- Electrical and Computer Engineering
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Thong, Jason
- Advisor dc:contributor.advisor
-
- Nicolici, Nicola
Subjects
dc:subject × 1Identifiers
dc:identifier.*- Identifier URI
- https://doi.org/10.71548/12473
- Dc Identifier Other
-
opendissertations/4292
5311
2039208