3
$\begingroup$

I heard that the padding with zeros is mainly for efficiency and speed, other than that, is there a downside to use fft(signal) instead of fft(signal, N) where N is a power of 2 assuming signal length is not a power of 2. Thank you

$\endgroup$
  • 3
    $\begingroup$ Assuming a proper implementation, and discarding the small rounding differences that you'll get just by doing a different sequence of operations, no, there's no substantive drop in accuracy if you slightly pad your DFT length to the next power of 2. Whether it ends up actually being any faster is dependent upon your implementation. $\endgroup$ – Jason R Apr 16 '13 at 16:57
5
$\begingroup$

Assuming a proper implementation, and discarding the small rounding differences that you'll get just by doing a different sequence of operations, no, there's no substantive drop in accuracy if you slightly pad your DFT length to the next power of 2. Whether it ends up actually being any faster is dependent upon your implementation, however. Why is that?

It's a very common misconception that there is a single Fast Fourier Transform algorithm and that you must use a power-of-2 size for best performance. If you look for a description of an FFT algorithm, you'll often see the radix-2 decimation-in-time or decimation-in-frequency techniques explained, likely because they're the easiest to illustrate. However, even the seminal FFT technique, the Cooley-Tukey algorithm, generically factorizes the FFT size into smaller numbers, not just powers of 2.

Using a good FFT library, you'll get the best performance if your FFT size can be factored into a number of small prime factors. The FFT library will then have optimized implementations of DFT kernels for each of these primes, which can then be recombined appropriately to yield the full set of DFT outputs. As I alluded to in a comment on another question, modern libraries will often give good performance for all prime factors ~13 and below.

With that said, you may find that by padding up to the next power of 2, it's possible that your transform might become slower. If you're already using an FFT size that your library implementation is well-suited for, you're just adding extra work for yourself by padding the size out. The best way to judge this is to benchmark a few candidate sizes and see which does best on your platform. If you have to make an automated choice of a good FFT size, then based on the characteristics of the radixes that your library supports, you can choose the next size that has an appropriate set of prime factors.

$\endgroup$
  • $\begingroup$ Thank you so much for the in depth explanation...I really should learn some of these stuff, I do not want my understanding of the FFT to be shallow. If you have any book suggestions please be kind and link it to me. $\endgroup$ – user3723 Apr 17 '13 at 15:11
2
$\begingroup$

Well I guess I can give a suitable answer for this question because i am working on a task in LTE 3ggp in which I have to calculate the FFT of 1536 which is not a power of 2. If your input length is a power of 2 it means you can easily use radix2 fft algorithm to compute the dft. But if your length is not a multiple of any number directly like in my case its 1536 you can't use one algorithm, you have to split it and used several algorithms and yeah it may increase the computational cost. You have to look for it in detail. I would recommend you to go this document and have a look if you are really interested because its quite time consuming to understand and more cumbersome to program in C. http://www.freescale.com/files/dsp/doc/app_note/AN3680.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.