APPLICATIONS OF MULTIPLICATIVE COMPLEXITY THEORY TO CONVOLUTION AND THE DISCRETE FOURIER TRANSFORM (FAST, COMPUTATIONAL, DIGITAL FILTERING, SIGNAL PROCESSING, ALGORITHMS)
HEIDEMAN, MICHAEL THOMAS
Doctor of Philosophy thesis
A review of the theory of multiplicative complexity and its application to common signal processing operations is presented. This review collects results on the multiplicative complexity of polynomial multiplication, products in extension fields, multivariate polynomial multiplication, and multiple products in the same extension field with one or more fixed polynomials. In addition, new results are obtained for the multiplicative complexity of multidimensional cyclic convolution, the one-dimensional discrete Fourier transform (DFT), and convolutions and DFTs with input constraints or output restrictions. The multiplicative complexity of multidimensional cyclic convolution is determined for any possible combination of lengths in any number of dimensions, extending a result of Winograd for one- and two-dimensional cyclic convolution. This result is shown to be applicable in determining the multiplicative complexity of the one-dimensional discrete Fourier transform (DFT). The multiplicative complexity of the DFT for all possible lengths is determined starting with Winograd's result for odd prime lengths and then extending it to power-of-prime lengths, power-of-two lengths, and finally to arbitrary lengths. The multiplicative complexity of systems of polynomial multiplication with constrained inputs is considered. An input constraint must imply a nontrivial factorization of one input polynomial for which one factor has coefficients only in the ground field if the multiplicative complexity is to be reduced over unconstrained polynomial multiplication. This result is applied to symmetric polynomial multiplication. The multiplicative complexity of polynomial products for which only selected outputs are needed is analyzed. Complexities are derived for polynomial products with decimated and truncated outputs, but no general rule is apparent for arbitrary output restrictions. The effect of input constraints and output restrictions on the multiplicative complexity of the discrete Fourier transform are considered. Specifically, restrictions to one input or output are analyzed as are even- or odd-symmetric inputs.
Engineering, Electronics and Electrical