Frequency resolution and timestep in DFT

Question

I am learning DFT and I am not sure I understand it correctly. I am just going to write out the process of DFT and I am asking you to tell me if I am thinking the right way.

Suppose we have a signal on which we run DFT to get the frequencies incorporated in the signal. We use a window of size N samples and calculate DFT on it. The result are frequencies which occur in this chunk of audio. Now we can display the spectrum (like Winamp does). But we would like to display the spectrum while the song is playing thus calculating DFT for many such windows. Because it would take a long time to do this with all the windows, we say we have a timestep (dt) between windows. This way we loose some frequencies (not all samples are processed) but we gain in computing time and this way it is possible to display spectrum "realtime" while the audio is playing.

Again, I am not sure if what I wrote is correct so please shed a light.

Even if everything what I wrote above is true indeed, where does the frequency resolution (df) step in? My first answer would be the window size (N) because that way we can test more samples.

Answer 1

The "timestep" $dt$ (using your nomenclature) between DFT windows can really be anything you choose. There are a few different cases to consider:

• $dt < N$: In this case, there is overlap between successive windows of samples that you input to the DFT. This can be used if you would like to get answers more frequently than every $N$ samples. It's quite common to see something like 50% overlap between windows being used.

• $dt = N$: In this case, there is no overlap; you just take successive blocks of $N$ samples and use those as inputs to the DFT. This would give you the minimum processing load while not skipping any input data.

• $dt > N$: As you noted, in this case, you're skipping data between windows (sometimes called "underlap"). This can reduce your processing load further, but since you're skipping data, you run the risk of missing the analysis of some feature in that portion of data that was discarded.

The frequency spacing of the DFT is related to the sample rate and the DFT length. Specifically:

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

where $f_s$ is the sample rate of the input data. $df$ in the equation above corresponds to the frequency spacing between each output (i.e. with $f_s$ measured in Hz, the outputs will have a spacing of $df$ Hz).

Answer 2

Digging up this old post because I thought the OP's assignment is interesting (basically building a real-time display of the spectrum of an audio signal) and because I think the answer to his question can be improved upon. If I understand correctly, he would like to know two things: (1) What is frequency resolution (in the context of a DFT computation)? and (2) What should timestep dt be?

I will attempt to answer (1).

Suppose you have a continuous-time signal $x_c(t)$ which you can think of as physically corresponding to an analog signal which you've pre-recorded (I don't know how, but "pre-recorded" in the sense that you can replay the same analog signal). To get $x(n)$ you sample the analog signal periodically every $T$ seconds (i.e., $f_s = \frac{1}{T}$):

$x(n) = x_c(nT)$

which, for the duration of the audio file, might contain a total of $N_{max}$ samples. The length-$N$ DFT takes the sampled signal $x(n)$ for $n = 0, 1, 2, ..., (N-1)$ with $N \leq N_{max}$ and computes values that are proportional to projection coefficients (if you read chapter 5 and 6, you'll get a better sense of what a coefficient-of-projection geometrically represents — although it is essentially the length of a vector).

A length-$N$ DFT gives you $N$ values such that, if you were to divide each value by $N$, would result in the set of magnitudes of sampled complex sinusoids (of various frequencies) that add up (in the vector addition-sense) to $x(n)$. The book calls those sampled complex sinusoids $s_k = e^{j\omega_knT} = e^{j2\pi\frac{k}{N}n}$ and geometrically each $s_k(n)$ is a 3D-spiral (the higher the frequency, the bigger $\omega_k$, the tighter the spiral winds — but note that there is a limit to how tight the spiral winds get). The frequency of each sampled complex sinusoid is $w_k = 2\pi\frac{k}{N}f_s$.

When we say "the magnitude of the frequency component $w_k$ of the signal $x(n)$ is $X(w_k)$", we are actually referring to the result of this finite sum: $X(k)= X(\omega_k)=\sum\limits_{n=0}^{N-1} x(n)s_k^{*}(n)= \sum\limits_{n=0}^{N-1}x(n)e^{-j\omega_knT}= \sum\limits_{n=0}^{N-1}x(n)e^{-j(2\pi\frac{k}{N})n}$.

That is the definition of the DFT. The input to the DFT is the frequency you want by specifying a value $k$ (referred to as the $k$'th frequency bin), which through the definition $w_k$ will yield a frequency value.

$k$ is an integer defined in a manner similar to $n$. Specifically $k = 0, 1, ..., (N-1)$. The frequency resolution (in units of radians) is just the difference between any two consecutive $\omega_k$'s:

$(\omega_{k+1})-(\omega_k) = (2\pi\frac{k+1}{N}fs) - (2\pi\frac{k}{N}fs) = \frac{2\pi f_s}{N} $

Which in units of Hz is just $\frac{f_s}{N}$. Geometrically, frequency resolution is the angular displacement between consecutive roots of unity. In the context of the DFT computation, the frequency resolution is the difference between two consecutive frequencies for which you can obtain spectra samples (i.e., the difference in frequency between two consecutive frequencies for which $X(\omega_k)$ is defined).