Presented at the 1996 IEEE Asilomar Conference on Signals, Systems, and Computers

Optimization of Signal Processing Algorithms

Raza Ahmed (1) and Brian L. Evans (2)

(1) Cable Network Analysis, Measurement Business Division, Tektronix Inc., 625 SE Salmon Avenue, Redmond, Oregon 97756-0227 USA
razaa@master.cna.tek.com

(2) Department of Electrical and Computer Engineering, Engineering Science Building, The University of Texas at Austin, Austin, TX 78712-1084 USA
bevans@ece.utexas.edu

Abstract

We optimize implementations of signal processing algorithms by rewriting subexpressions according to a set of algebraic identities. We encode the algebraic identities as conditional rules, and program hill climbing and simulated annealing search techniques to apply the rules. Both of these search techniques avoid an exponential explosion in memory usage because they only keep a single state in memory instead of building the entire tree of possible equivalent forms. We compare the effectiveness of these search techniques in optimizing implementations of several one-dimensional and multidimensional multirate signal processing algorithms. Our prototype environment is written in Mathematica.

The complete paper is available in PDF format.

Last Updated 02/06/99.