# disadvantages of FFT, it can not extract enough frequencies without enough samples

Let's say sampling rate is $Fs = 44\mathtt{kHz}$, now I have $N = 2048$ samples, then I can get $N/2 + 1 = 1025$ frequencies.

I'm confused by Matlab's FFT documentation that says the frequencies are present at:

(Fs/2) * linspace(0, 1, N/2+1)

It is very probable that the real frequencies are not among the frequencies generated. What should we do to get the real frequencies?

• What restrictions are present? It sounds like you're limited to sampling adaptively or collecting more samples. – Scott Aug 11 '14 at 5:37
• The restriction is that we only have limited numbers of samples. How can we get the real frequency, is it OK to add series of 0 just to increase the sample number? – new_comer_forever Aug 11 '14 at 6:32

Any measurement has a finite precision. You can't find real frequency exactly in general. You can evaluate it with necessary precision instead. In the case of FFT if the real frequency doesn't match FFT frequency grid exactly, power spectrum is spreading mostly among neighbouring frequency bins (among all bins in general, but most of it is focused in a few adjacent ones). Nevertheless you can estimate the real frequency by finding maximum of such a spectrum. Dealing with FFT you can improve the precision of frequency search by increasing the number of samples. If you can't, you should use another power spectrum estimation techniques but it's the separate question.

Hope this helps.

• Let's say we press one key on piano which only lasts for 1/16 seconds. Then samples we have is Fs x 1/16. Our ear knows what key it is, just say D4 key (293HZ), However, based on (Fs/2)⋅linspace(0,1,N/2+1), frequency can not map to 293HZ, the range is like 260HZ, 310HZ, it skips 293HZ. – new_comer_forever Aug 11 '14 at 6:28
• With such an input neighbouring frequency bins are 288Hz (18th) and 304Hz (19th). So the most of energy will spread among these bins with maximum at 18th bin. You can say, let it be 288Hz and 5Hz error is neglectable. Or you can estimate frequency more precisely using all non-zero frequency bins and some kind of averaging (if the signal strength is low this approach won't work). Or you can try to increase signal duration. – Serj Aug 11 '14 at 7:25
• About adding zeros: if you add zeros in the end of your sample sequence you can find more FFT points, but precision states the same. In such a case all FFT frequencies will grow in width (you'll see sinc function in the case of harmonic input). With this approach you can find maximum that is between 288Hz and 304Hz, but there will be no more sharp peak. You probably should try this method in MATLAB, may be it will work for you – Serj Aug 11 '14 at 7:41
• Nitpick: energy smears over all frequency bins, ones that are closest are affected most. – jojek Aug 11 '14 at 7:51
• I can't provide you some math about this on a fly, but look here: dsp.stackexchange.com/questions/741/…, maybe it'll help. Also look at fine Doppler estimation topics (e.g. Richards "Fundamentals of radar signal processing", chap 5.3.4). If you are interesting in only few frequencies these methods may be better for your task (in the sense of computations required) – Serj Aug 12 '14 at 7:34

For computing a few frequency components the Goertzel algorithm is usually used. Note that the frequencies do not need to lie on a grid (as is the case with the FFT).

This is not an inherent disadvantage of the FFT. This is an inherent disadvantage more related to the limited length window or number of samples and any a-priori assumptions or analysis of the S/N ratio. In low noise, narrow-band "real" frequency peaks can be estimated between FFT result bins by interpolation. See: Number of FFT points required for a specific frequency resolution for an oversampled signal

• From 1024 samples, human ear can recognise the frequency, but FFT can not choose out this frequency. No doubt ear is a very powerful filter. Basically, this disadvantage is limited by FFT theorem or computer computing ability? – new_comer_forever Aug 12 '14 at 5:35
• Neither. Instead by the length of the sample window and the S/N ratio around the desired frequency being estimated. – hotpaw2 Aug 12 '14 at 7:28