Back to search

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 × 1

Identifiers

dc:identifier.*
Dc Identifier Other
opendissertations/4292
5311
2039208

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Thong, Jason. New Algorithms for Constant Coefficient Multiplication in Custom Hardware. 2009. http://hdl.handle.net/11375/9143