On complexity of fast convolution algorithms
- 24 March 2005
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Complexity analysis is highly recommended to be based on suitable sequential and parallel machines using arbitrary resources. Traditional complexity predicates are changed completely with respect to fast hardware multipliers, complex arithmetic processing units and the forthcoming VLSI technology. Both signal flow graph derivative and program based complexity analysis are proposed. It is shown that sequential complexity will decrease whereas parallel complexity will increase. The analysis of the last transform step in a transform convolution system carries out an increase of the time complexity at all. Consequently the reduction of the last transform step is resulting in an improved performance of fast transform filter algorithms, especially when the transform size is of moderate small size. This is applicable to the prime factor DFT computation via fast convolution, the WFTA transforms and arbitrary FFT transformations in general.Keywords
This publication has 5 references indexed in Scilit:
- Fast transform digital filtering using non-diagonal spectral operatorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A comparative study of time efficient FFT and WFTA programs for general purpose computersIEEE Transactions on Acoustics, Speech, and Signal Processing, 1978
- On Computing the Discrete Fourier TransformMathematics of Computation, 1978
- Hardware realization of a Fermat number transformIEEE Transactions on Acoustics, Speech, and Signal Processing, 1976
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965