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
01.01.2003
290269 byte
Aufsatz (Konferenz)
Elektronische Ressource
Englisch
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