# FFT of size not a power of 2

My question is regarding the input size of a signal which is not a power of 2 and we have to take the fft of it. Some solutions say that suppose if we want to take the fft of 1800 we should zero pad it till the length of 2048 to make it power of 2 and then apply the radix 2 algorithm. But there are other solutions as well which applies a combination of different algorithms without zero padding and then calculating the required FFT. My question is Does zero padding a signal to length of 2048 in case we have to take fft of 1800 makes any difference in results , if we use a combination of different algorithms to calculate the fft of size 1800. Would there be any difference or the result would be same.

• The resulting FFT will be different: instead of calculating the FFT at the frequencies $2\pi n/1800$ for $n=0\ldots 1799$, you will be calculating them at $2\pi n/2048$ for $n=0\ldots 2047$. However, there is no degradation of the information. – Peter K. Apr 22 '13 at 15:08
• So, it means both approaches are correct? But which one you recommend to be more good in terms of practicality ? – D X Apr 22 '13 at 15:09
• Yes, both approaches are correct. I'd use the "minimum energy solution" (i.e. the simplest, the laziest solution). This would usually be using the 2048 length transform. – Peter K. Apr 22 '13 at 15:11
• I have seen in the literature and books people are recommending that zero pad it to make it power of 2.. Why they never insist on implementing some combination of other algorithms for good results. – D X Apr 22 '13 at 15:12
• Assume your data is in x. Form X = fft(x,123456); (or some other strange length). Find xx = ifft(X);. See what sum(abs(x-xx(1:length(x)))); is. – Peter K. Apr 22 '13 at 15:23

## 2 Answers

The resulting FFT will be different: instead of calculating the FFT at the frequencies $2\pi n/1800\ \$ for $n=0\ldots 1799\ \$, you will be calculating them at $2\pi n/2048\ \$ for $n=0\ldots 2047\ \$. However, there is no degradation of the information.

Both approaches are correct: using 1800 or 2048. I'd use the "minimum energy solution" (i.e. the simplest, the laziest solution). This would usually be using the 2048 length transform.

People tend to use radix-2 transforms because they don't know any better. There seems to be much mis-information about FFTs HAVING to be power-of-2. There is no such constraint. Also, they probably don't know about about decent non-radix-2 algorithms, such as those available in FFTW and other libraries.

To see that the FFT of any length is information-preserving:

Assume your data of length 1800 is in x. Form X = fft(x,2048); (or some other length different from 1800).
Find xx = ifft(X);.
See what sum(abs(x-xx(1:1800))); is.

See also this question and its answers.

• When i do it ... it just gives me a number but no comparison through graphs. I am sorry but i am not very good in matlab because I implemented everything in C. – D X Apr 23 '13 at 7:49

One needs to understand that since the result (and the source) are discreet, FFT is not really a Fourier transform, but is in reality Fourier Series development. This means that the result of any FFT is not the the transform of a single block of data, but is the tranform of a periodic signal consisting of an infinite concatenation of the same block of data, with or without a separation consisting of the padding length. (Assuming that my analysed data looks like «m», the transform will be the the development of «...mmmmm...» or of «... m m m m m ...», which are not the same signal.)

As a consequence, having no padding means one will implicitly add or remove the high frequency glitch in the source data coming from the discontinuity in the joining of the end of one bloc and the beginning of the next one (which is the same). The extreme example would be to analyse a block containing all the same value. Padding of not padding will make the difference between a continuous signal and a rectangular one.

The other consequence of this, is that the longer the padding, the nearer the result will be from the transform of a single burst of data, and the higher will be the resolution of the transform. It is not completely accurate to say that wathever the passing, there will be no degradation of information. There will (in a limited way), because of the rounding errors and using a longer buffer might help prevent it (again, in a very limited way).