Could someone explain to me why the computation speed for the fast Fourier transform increases by padding the series with zeros to the point that its length is close to a power of 2? This is common in the matlab environment, for example:



Firstly the terminology: The thing that you are trying to compute is the Discrete Fourier Series (DFS). This the only flavor for Fourier Transforms that is discrete in both time and frequency and can thus be represented numerically inside a computer. The Fast Fourier Transform is a specific algorithm to computer the DFS (see for example http://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm ). The term FFT is often used to refer to the DFS but that's actually somewhat wrong and often confusing.

You can always calculate the DFS directly using it's definition but this will require $N^{2}$ complex multiplies. The FFT speeds this up by breaking splitting the vector N into smaller sub vectors and then using the symmetry properties of the transform coefficient (often referred to as "twiddle factors"). The vector needs to be split in equal pieces though and that works better the more prime factors N has. A power of two is the best since it has the most prime factors and the factors themselves are the smallest possible. Worst case are N's that are prime themselves.

Let's assume you want to calculate the DFS of sequence of 1021 points. Since it's a prime number you need to use the direct formula which requires 1021*1021 multiples, roughly a million. If you zero pad to 1024, you can use the most efficient FFT version and the number of complex multiplies is 2*log2(N)*N is only about 20000. Hence that's a lot faster.

FFT is efficient if your DFS length can be broken down into lots of small prime numbers. Large prime numbers are slower. In practice you can typically find a spot made our of 2s and 3s that's fairly close to where you want to be so there is no need to always go to a power of 2.


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.