0
$\begingroup$

I am currently working on a project that involves processing an audio signal by dividing it into chunks of size B. The buffer is then zero padded to have a size of 44100 points, after which FFT is applied so that the peak frequency of interest is detected. The reason why I'm zero-padding is to have a 1-Hz FFT resolution.

I would appreciate your input on two questions, please:

  • Given this process, what's the smallest FFT buffer B (before zero-padding) that I could have?
  • Is there a relationship between the size of the buffer B (before zero-padding) and the accuracy of detecting the peak?
$\endgroup$
1
$\begingroup$

Zero-padding an FFT interpolates more intermediate points. How many actual samples B are needed to provide a reasonable interpolation depends on what kind of resolution you need and the signal to noise ratio of the peaks of interest.

If there is more than 1 peak, and you need to separate them (with a clear visible gap of say around 3 dB between each peak in a line pair to be resolved, as per "photographic resolution"), then you will usually need slightly more than 2*Fs/dF samples represented by B to resolve 2 peaks of roughly equal magnitudes that are separated by dF in frequency. Otherwise adjacent peaks will blur together, no matter how much you interpolate, and you won't be able to resolve the pair (e.g. be able to tell if there are 1 or 2 or even more narrower peaks inside a big hump). If you use a non-rectangular window, the you may need more than 3*Fs/dF samples to resolve peak pairs. If 2 adjacent frequency peaks are of very different magnitudes then you will probably need far more samples than that, since interpolation (or zero-padding an FFT) won't pull the lower magnitude peak out of the skirt (or windowing artifacts) of the higher magnitude peak. And that might be required to have any resolution of the lower magnitude frequency peak at all.

But if there is only one single frequency peak (or it is very far apart from the nearest other frequency peak), then the number of samples you need depends on how far that isolated peak is above the local noise floor. With very high S/N, you can get by with less (and sometimes a lot less) than Fs/plot_resolution samples, since the peak can be interpolated (by either zero padding, or by windowed Sinc interpolation, etc.) between FFT result bins of a length B FFT. But as noise increases, you need more points to keep a narrow-band peak clearly above and not distorted by the statistical variations of the local noise floor.

In absolute zero noise, you may need as few as 3 or 4 non-aliased sample points to exactly determine the frequency (of a single peak representing a pure unmodulated sinusoid) approaching infinite resolution. See this answer: Confusion regarding Nyquist Sampling Theorem for references.

So your question can't be answered in more detail (size of B required) without knowledge of the S/N ratio.

(for strictly real data:) Note that near DC (0 Hz) and near Fs/2, you need to separate a frequency peak from its own complex conjugate image by a lot more than 3 dB to get reasonable frequency measurement resolution.

$\endgroup$
  • $\begingroup$ Thanks @hotpaw2 for the detailed answer. In my current project my goal is to detect frequency peaks of 10 tones having frequencies ranging from 17000Hz to 18800Hz, where each tone is separated by 200Hz (i.e. dF = 200) and have an equal amplitude. As I understand from your explanation, and since I use a Hamming Window, I need at least (3 * 44100 / 200) samples to be able to distinguish peaks. Is that correct? $\endgroup$ – Majed Mar 30 '17 at 19:53
  • $\begingroup$ @Majed : Due to possible non-zero background noise, you may want to experiment using more samples, maybe 1024 to 1100 samples (5x). $\endgroup$ – hotpaw2 Mar 30 '17 at 20:12
  • $\begingroup$ Thanks a lot. One last question: could you please point me to any useful reference (book, paper, etc.) that elaborates on this kind of calculation (i.e. alpha * Fs/dF)? $\endgroup$ – Majed Mar 30 '17 at 22:16
  • $\begingroup$ @Majed I believe the paper referenced in my response is exactly what you are looking for. $\endgroup$ – Dan Boschen Mar 31 '17 at 15:24
3
$\begingroup$

Zero padding does not increase frequency resolution, but interpolates the spectrum you have by adding more samples in between as an interpolation. The frequency resolution is well known to be set by the size of your buffer before zero padding with the relationship:

$$f_{res} = 1/T$$

Where T is the length of your buffer in time (notice that this relationship is independent of the sampling rate!). However this classic relationship is the width of each bin by their 3.0 dB bandwidths or half power point (viewed as a filter-- it is helpful and accurate to view the FFT as a bank of filters), while to completely resolve two frequencies of equal magnitude, due to their coherent addition in the FFT, the frequencies need to be separated by greater than the half magnitude width of each bin (or the 6.0 dB bandwidth). The 6.0 dB bandwidth for a rectangular window (no window) is 1.21, so to resolve two tones of equal magnitude and any arbitrary phase the length N must be greater than:

Minimum number of samples, two tones same magnitude (no Window):

$$N > 1.21 f_s/f_{\Delta}$$

Where $N$ is the number of samples, $f_s$ is the sampling rate and $f{\Delta}$ is the frequency separation both in Hz, using the relationship:

$$T = \frac{N}{f_s}$$

Note that using any window will decrease this resolution further (the best resolution is obtained with the rectangular window, which is no window) at the needed benefit of dynamic range. Thus choosing a window is always a trade between frequency resolution and dynamic range, and therefore the window is chosen based on the anticipated maximum power difference between closest frequencies and number of samples needed. For example, the 6.0 dB BW of the Hamming window is 1.81 which modifies the above formula accordingly:

Minimum number of samples, two tones same magnitude (Hamming Window):

$$N > 1.81 f_s/f_{\Delta}$$

Please refer to this paper by fred harris On the Use of Windows for Harmonic Analysis that provides detailed considerations for window selection and resolution bandwidth for resolving tones, particularly the section G on p 178 "Minimum Resolution Bandwidth" with reference to his figure copied below, along with Table 1 on page 176 that lists detailed metrics for all common windows.

figure from fred harris paper

In the case of multiple tones at different power levels and in the presence of background noise, it is helpful to look at the complete magnitude response of the kernel (frequency response of the "filter" for each bin). Note again, since the tones in different bins add coherently they will sum in magnitude based on their relative phases (and subtract!), while noise components will sum in power. This is shown below by comparing the normalized magnitude plots of the rectangular and Hamming kernel, with a horizontal line showing the -6 dB half magnitude point to relate to the relationships derived above. The width of the main lobe of the rectangular window is 1.21 and for the Hamming window it is 1.81, and with reference to the figure above we see how this is the minimum separation for two tones of equal magnitude, being the boundary condition where a single maxima can exist. But we also see the details related to dynamic range considerations.

Rectangular and Hamming Kernel

Specifically consider two tones separated by 20 dB, the rectangular window will require greater than 5.36 bins ($f_{\Delta} > 5.36 f_s/N$) while the Hamming window will be able to resolve with separations greater than 3.32 bins in this condition:

Minimum number of samples, two tones 20 dB difference (no Window):

$$N > 5.36 f_s/f_{\Delta}$$

Minimum number of samples, two tones 20 dB difference (Hamming Window):

$$N > 3.32 f_s/f_{\Delta}$$

The paper referenced above details this further with consideration to multiple tones and in the presence of noise, where due to the effect of the side-lobe roll-off the window chosen has a significant impact.

For consideration of noise, margin is added to your maximum separation in power between tones; theoretically for AWGN you can statistically always encounter a condition where the noise added to one tone in magnitude compared to the noise subtracted from the next is beyond your designed separation, therefore it becomes a probability of false detection problem, where you design a margin based on the probability of not separating two tones in your designed resolution. I suspect this would quickly be insignificant if you are working with high SNR's in a bin (and remember the FFT has a processing gain of 20LogN decreasing the noise in one bin compared to your overall noise). This is best demonstrated with an example: Consider the case of adjacent tones of equal magnitude with a noise limit we bound to 1.5 (which could also then reduce the adjacent tone by 0.5), this would result in a worst case separation in the tones of 20Log(1.5/5)= 9.5 dB. If we therefore added 9.5 dB to our total maximum designed separation in magnitude between adjacent tones (and then use the process we used above to compute number of FFT samples needed) we will ensure that we will always be able to detect the adjacent frequencies for all cases that the noise itself does not cause a 3x magnitude separation between bins. (Placeholder here to show awesome graph of SNR vs false alarm rate in this case: This would be an interesting joint probability problem to solve at some point if I or someone else has the time and energy to work through it assuming not readily available somewhere).

So to answer your question, your smallest buffer size is set by the actual frequency resolution you need, with consideration to total number of tones in close proximity and dynamic range needed (max distance in magnitude between tones). Zero padding is done if you want to interpolate more samples (without adding any more resolution; it is just a smoothing), which you may do for convenience (to get the FFT out to the closest power of 2 for example, or to fill in more samples on a plot.

In the case of detecting the frequency of a single tone, the zero padded FFT will more readily point out the precise frequency location (but this is not different from what you can do more efficiently through interpolation using the information derived from the closest bins if you did not zero pad), but if you had multiple frequencies together within the span of the frequency resolution defined above, you would not be able to resolve them (they would appear as one frequency).

As @OlliNiemitalo has correctly pointed out that zero padding WILL allow you to visibly observe the obtained frequency resolution described above (which is what I have done to plot the responses in between bins in the plot above).

In this post is an example plot showing the difference between zero padding to increase the number of samples versus adding more actual samples:

What happens when N increases in N-point DFT

$\endgroup$
  • 1
    $\begingroup$ I would add that without zero-padding, spectral leakage prevents resolving peak frequencies from two closest bins each. $\endgroup$ – Olli Niemitalo Mar 30 '17 at 13:49
  • $\begingroup$ @OlliNiemitalo That's a great point, which is demonstrated well in the link I gave where I had to go much more than 1/T to actually resolve, while what you suggest would allow visible resolution at the 1/T length. Thanks for that! I updated the detailed link referenced above with your input Olli. $\endgroup$ – Dan Boschen Mar 30 '17 at 13:56
  • $\begingroup$ @hotpaw2- Now I have to try it based on Olli's comment combining with zero padding but not sure the -1 is fair as I did not say in the answer about resolving adjacent peaks but only that the frequency resolution is 1/T; and you are not disputing that are you? $\endgroup$ – Dan Boschen Mar 30 '17 at 16:08
  • $\begingroup$ @hotpaw But even without simulating it I can almost see in my head that adjacent samples would not be resolvable as you suggest given the Sinc convolution that occurs- but being resolvable and frequency resolution are two different things. I'll check with a quick sim and fix my updated comment in the linked post (where the -1 would belong if not fixed)- Agree? $\endgroup$ – Dan Boschen Mar 30 '17 at 16:13
  • 1
    $\begingroup$ @hotpaw2 and thank you for commenting with the downvote explaining your thoughts! I notice a lot of questions and answers out there that get downvoted with no explanation which is not helpful. Kudos. $\endgroup$ – Dan Boschen Mar 30 '17 at 16:17

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.