In the paper it is shown that discrete Fourier transform can be computed using only 0(NlogN) operations even if N is prime, N is the transform size. A fast algorithm working for any prime N is presented, which worst case computational complexity is below 32N log/sub 2/(N) arithmetical operations, which can be compared to less than 4Nlog/sub 2/(N) operations for the best existing FFT for N being power of number 2. It is shown, however that by introducing few modifications the worst case computational complexity of the algorithm can be reduced to circa 16Nlog/sub 2/(N) arithmetical operations. In this way an interesting theoretical result is obtained that computational complexities of the DFT for 'most' and 'least' convenient N values do not differ by more than factor 4.
Universal fast Fourier transform algorithm for prime data vector sizes
2003-01-01
290269 byte
Conference paper
Electronic Resource
English
Universal Fast Fourier Transform Algorithm for Prime Data Vector Sizes
British Library Conference Proceedings | 2003
|British Library Online Contents | 1994
|The Fast Fourier Transform in Fourier Spectroscopy
NTIS | 1966
|The Fast Fourier Transform (FFT)
Springer Verlag | 2008
Fast Fourier Transform for Hexagonal Aggregates
British Library Online Contents | 2000
|