Performing DFT of streaming audio problem. Is there a limit?

Question

I am trying to write software that will perform the discrete fourier transform of real time data coming from the microphone into the sound card on a computer. I am using Java with the javax.sound APIs.

I am capturing 250 ms of data each time. That means, as the sampling rate is 44100, I am buffering 11025 of 16-bit shorts and performing the DFT on this data in each iteration.

My DFT code correlates this window of data with sine and cosine waves from 19 Hz up to 198 Hz in steps of 1, so as this window is 250 ms of data , this means it is actually correlating the incoming audio with frequencies from 76 Hz up to 792Hz in steps of 4.

If I now wish to take a smaller window of data each time of 125ms instead of 250ms in order to speed things up. If i correlate this data with sine and cosine waves of incrementing frequencies by 1 like before, this means that it is actually correlating the incoming audio with waves in steps of 8Hz. This is not good for my problem as I want to be able to look for frequency differences in the signal of less than 8Hz.

My question is, is this the normal trade-off, speed versus frequency resolution , or is there some way around this ?

Many thanks in advance. I am new to audio processing so forgive me if i'm missing out on some common sense :)

Answer 1

The window size of your FFT limits your resolution and there is no way round this (i.e. you can't zero pad or zero stuff to get round it). The easiest way to think about it is: lower frequencies have longer periods so need a longer window (more samples) to differentiate.

I believe it would be impossible to increase your resolution even if you used an alternaitve method like a series of very steep band passes narrower than the frequency resolution permitted by FFT for your window size. Yes, you would get some measures out from your band passes but if the window size was not long enough, the data would be highly inaccurate in differentiating very close lower frequencies as there would not be enough data to disentangle them.

Consider a window of 1 sample or 2 samples, in these cases it is easy to see that you just can't recover resolution from small windows without making them bigger by gathering more independent samples.

Answer 2

My question is, is this the normal trade-off, speed versus frequency resolution , or is there some way around this ?

Well, yes, that is the normal trade-off.

But: If speed is a concern, why on earth are you using your own correlation-based DFT? There's a lot of FFT implementations out there, and a 11025-point FFT done with the FFTw takes a few µs on my PC, so you can have a running FFT for every other sample without problems.

Hence: if you care for speed, use a library that someone with experiences (or decades of development time, university carreers full of theory and a lot of assistant researchers) has written for you. A "correlation with sines" based DFT is bound to be slower, especially since I presume you didn't even implement this as simple multiplication with a DFT matrix, based on how you worded your question.

Note that there might be even more specific algorithms that perform even better, if you don't really need all equidistant frequencies that a DFT would give you, but just need to test a few frequencies (e.g. parametric pseudospectrum estimators such as MUSIC) or know exactly how many discrete tones there are (the closely related ESPRIT).

Answer 3

The trade-off between the length of samples and frequency resolution varies with the signal to noise ratio (or spectral sparcity) and in what kind of resolution you need. If the noise level is low enough, then sufficiently isolated narrow frequency spectrum can be interpolated to within some fraction of the DFT result frequency bin spacing (e.g. perhaps enough to get 1 or 2 Hz resolution from 8 Hz DFT result spacings). If the interference level is high enough, then more than 2 DFT result bin spacings may be required to cleanly separate spectral peaks.

For signals with a very sparse spectrum, there are also other parametric estimators than just using DFT magnitude peaks.