home · mobile · calendar · defenses · 2006-2007 · 

Thesis Defense - Hinds

Methodology for the Design of Linear Algorithms for Signal Processing Applications
Computer Science PhD Candidate

This thesis presents a methodology for designing fixed-point implementations of linear algorithms for digital signal processing applications. The algorithms targeted by this work are computation intensive algorithms whose definitions require the use of floating point constants, such as the Inverse and Forward Discrete Cosine Transforms (DCT). These constants make the algorithms difficult to implement in fixed precision, especially when both efficiency and accuracy are concurrent design requirements for their implementations. Implementations that can be characterized as both efficient and accurate are important in the context of general consumer electronics, in particular portable consumer electronics, which can have limited energy resources available for numerical computation. Our methodology consists of five steps that can be used to design fixed-point implementations that are both efficient and accurate. We demonstrate its use throughout this work by applying it to the DCT which is a pervasive algorithm, particularly in the areas of still image and digital video coding. Moreover, our methodology is the underlying technology used in a new ISO/IEC standard for fixed-point implementations of the 8x8 Inverse Discrete Cosine Transform (IDCT) and the 8x8 Forward Discrete Cosine Transform (FDCT). Specifically, our IDCT/FDCT implementations which are selected for this international standard are intended for use in video technologies by ISO/IEC JTC1/SC29/WG11, a working group within the ISO/IEC organization that is more widely known as the Moving Picture Experts Group or simply as MPEG. The flexibility of our methodology to be applied to other algorithms is shown also in our fixed-point design and implementation of a novel approach for performing 2x2 sub-sampling of Joint Photographic Experts Group (JPEG) formatted digital images. This thesis presents our five-step methodology and reviews the results of its application to create efficient and accurate fixed-point implementations of these algorithms.

Committee: Robert (Bobby) Schnabel, Professor (Chair)
Joan Mitchell, IBM Corporation
Richard Byrd, Professor
Harold (Hal) Gabow, Professor
Peter Mathys, Department of Electrical and Computer Engineering
Yuriy Reznik, QUALCOMM Incorporated
Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:20)