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
(2) Department of Electrical and Computer Engineering,
Engineering Science Building,
The University of Texas at Austin,
Austin, TX 78712-1084 USA
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.