Selectively improve the frequency resolution of FFT (DFT)

Question

I have a digitally sampled signal(sampling frequency = 4000 Hz) which contains analog frequencies from 0 to 1000 Hz. I wish to have a frequency resolution of 100 Hz(like 0,100,200,300 Hz .. 1000 Hz) and I have to improve the frequency resolution at the 0 to 100 Hz range by 10 Hz. That is at the frequencies 0,10,20,30,... 100. So the frequency components I wish to detect are [0,10,20,...,100,200,300,...,1000]. In other words, I want more frequency resolution at the 0-100Hz range and less resolution at 100-1000Hz range. How this is possible through FFT or related methods.

Answer 1

You can compute any single FFT result bin using a complex Goertzel algorithm or filter.

Realize however that if you want to compute a number of bins on the order of log N or greater (such as 10 extra bins with 10 Hz bandwidth and spacing), it may be faster to do the full longer FFT and throw away all the extra FFT result bins.

So just compute 2 FFTs of 2 different lengths and ignore all the unwanted results.

Answer 2

I know it's a bit late to answer the original person who posted the question but just in case anybody finds this and wants an idea for a clever solution... The FFT algorithm is built ultilising a divide and conquer approach, so one could perhaps adjust it to calculate certain parts more accurately and others less so... During the FFT the frequency spectra are combined in stages from 2^x single point frequency domains to a single 2^x point frequency domain. During the algorithm I think there is a way to combine some of the bins together to get less resolution at one end than the other. Due to the 'butterfly' structure of the result at each stage, there are some limits to what one can achieve bit I think that in theory, one might be able to get it to produce bins in a exponential fashion such as [1hz, 2hz, 4hz, 8hz, 16hz, etc...] Just combine the last (s-1) bins together at each stage s! I haven't tried this yet myself but it looks pretty simple to give it a go, provided you are able to access and understand the code at guts of your particular FFT to begin with!

Thinking about it as a table of the bin bandwidth multipliers of frequency domains at each stage of the FFT, you would have:

[1] * 2^x;
[1, 1] * 2^(x-1);
[1, 1, 1, 1] -> [1, 1, 2] * 2^(x-2);
[1, 1, 2, 1, 1, 2] -> [1, 1, 2, 4] * 2^(x-3);
[1, 1, 2, 4, 1, 1, 2, 4] -> [1, 1, 2, 4, 8] * 2^(x-4);
etc... until (x-s) = 0.

Sorry this is hard to understand! Each [] is a frequency domain. The numbers inside the [] correspond to bins and show the relative size of the bandwidth that each bin represents. E.g. If 1 means 10hz then 2 means 20hz. -> is meant to be an arrow symbol which represents the transformation of these domains as bins are combined, and * 2^z means there are 2^z of these frequency domains at a particular stage. x is the total number of stages minus 1, and s is the current stage counting up from s = 0, the first stage. (The first stage is usually represented by a bit reversal sorted time domain in the FFT, and some sort of main processing loop then takes over and transforms it into the subsequent stages, but it depends on your exact version of the algorithm and it's design)

Is it worth it? Well because each bin is double the frequency of the last, such a set of bins will only perfectly match all octaves of a single pitch, so my guess it that it might be pretty useless unless you have some quite special requirements which could instead make it very useful... Would it be much faster to calculate? At each stage you would be calculating 2^(x-s) more bins than the last time instead of 2^x more bins every time, so I think that yes it should be substantislly faster for large FFTs as it scales far better.

The real question is, can such an approach be adapted to the kind of real world problem that the original question poses? There are multiple ways to produce bins in various other complex patterns, any one of which may be be more suitable, however some of these are not much more efficient than calculating a full high resolution FFT and combining bins afterwards. Also, designing an algorithm to create a pattern of bandwidths that makes any logical sense isn't so easy, although I cannot prove that it's an impossible task.

There are of course other simpler possibilities which might have quite interesting specific uses... One could manage to obtain something like [16hz, 24hz, 28hz, 30hz, 31hz] by combining the first (s-1) bins together at each stage. Or a pattern something like [1hz, 2hz, 4hz, 8hz, 12hz, 14hz, 15hz, 16hz] by combining some bins together around the middle at each suitable stage.

Answer 3

The frequency resolution of the FFT is Fs/N where N is the FFT size. The FFT gives you a uniform resolution at all frequencies. Therefore, you require N >= 400 points to get 10 Hz resolution.

Answer 4

I haven't seen this answer here, so I'll post it. You can resample the signal to a lower sample rate before doing the FFT, which reduces the size of the FFT.

If you know that the only frequencies that you are interested in are from 0..1000Hz, you can safely resample the original signal to an FS of 2000Hz and then do the FFT. This decreases the required FFT by a factor of 2 for the higher frequencies.

For the 10Hz divisions, resample the original signal again to an FS of 200Hz, and do the same FFT on the result to get your results from 0..100Hz.

Resampling the signal first increases the frequency resolution for the same size FFT, by limiting the FFT to only the frequencies you are interested in. It effectively increases the length of the FFT over the lower frequencies while throwing out the higher frequencies.

In your case: Input signal 4000Hz. Resample to 2000Hz and use FFT of size 64 gives a resolution of 2000/64 or 31.25Hz. Resample to 200Hz and use FFT of size 64 gives a resolution of 200/64 or 3.125Hz.

Answer 5

You can't improve frequency resolution in a given frequency region without increasing a number of samples to be analysed. The picture is for example:

There are two input signals of the same frequency, but one is 64us duration while other is 256us duration. Their Fourier transforms are represented in the picture by blue and green curves respectively. Now we say that DFT (and also FFT) is sampling of the Fourier transform. Red line and circles in the picture are DFT bins of the short signal. They are obviously uniformly spaced, but changing coefficients of DFT matrix we can of course sample the spectrum in the interesting region more precisely. But the main idea is: the frequency resolution stays the same. It's dependent on signal duration (or number of samples under processing). It's clearly seen from the picture: green curve shows greater frequency resolution because it was calculated from more signal samples.