Multiplicative Complexity, Convolution, and the DFT
By: by Michael T. Heideman
Series: Signal Processing and Digital Filtering; Signal processing and digital filtering
Publisher: Springer New York
Published: 1988
Place of publication: New York, NY
Language: eng
Format: [electronic resource] /
Number of pages: 155
ISBN-13: 9781461283997; 9781461239123
Subjects: Surfaces (Physics)
Description: This book introduces multiplicative complexity theory and applies it to the computation of discrete convolutions and the discrete Fourier transform. A mathematical framework is established that enables the multiplicative complexity of many common bilinear systems to be determined. Semilinear systems are introduced as a means of determining the multiplicative complexity of the discrete Fourier transform. Complexity results are derived for other discrete transforms such as the cosine and Hartley transforms. Complete proofs of all the major results are included - the book is essentially self-contained. Many examples are provided to demonstrate the application of the theory.
Notes: Online full text is restricted to subscribers.

Also available in print.

Mode of access: World Wide Web.
Table of contents: title: Introduction; title: Multiplicative Complexity of Linear and Bilinear Systems; title: Convolution and Polynomial Multiplication; title: Constrained Polynomial Multiplication; title: Multiplicative Complexity of Discrete Fourier Transform; title: Restricted and Constrained DFTs; title: Appendix A. Cyclotomic Polynomials and Their Properties; title: Appendix B. Complexities of Multidimensional Cyclic Convolutions; title: Appendix C. Programs for Computing Multiplicative Complexity; title: Appendix D. Tabulated Complexities of the One-Dimensional DFT; title: Problems; title: Bibliography; title: Index.