How come FFT window give half size frequency bands when filter can seems to have an infinite precision?

Question

I don't really understand maths behind filtering but use it lot in music production and i'm a total newbie to DSP.

Usually parametric filters let you filter frequencies with a precision that seems almost infinite. But when using a FFT or DFT the taken window size gives n / 2 + 1 frequency bands.

Are the two related ? if so how can a filter get so much precision when Fourier Transform doesn't?

That may seem a dumb question but when I look at spectrograph in sound softwares they always looks much more precise than the buffer I've choosed (usually 256 samples).

Answer 1

It is simply because the FFT (which implements the DFT, Discrete Fourier Transform) is intended to provide (very efficiently) the results of bandpass filters centered on every bin. The easiest way to explain this is to consider the 4 point DFT and compare that to 4 point moving average filters and to show what we do to center the moving average filter on any given frequency with infinite precision.

Consider the 4 point DFT:

$$X[k] = \begin{bmatrix}1 & 1 &1 &1 \\1 & -j & -1 & j\\1 & -1 & 1 & -1 \\1 & j & -1 &j \end{bmatrix}\begin{bmatrix} x[0] \\ x[1] \\x[2]\\x[3]\end{bmatrix}$$

Notice the first row, which is the 0 frequency bin, is just the sum of the 4 samples of x. If we were to move through a larger data set, taking 4 samples at a time and computing the DFT, and then shifting by one sample and repeating this, then the first bin results would be EXACTLY the same as a moving average filter (note the reverse order of the coefficients in the structure showing the position of the samples of x after the first 4 samples):

Another key point with the moving average filter, if we rotate the coefficients, we translate the filter to the center frequency of that rotation. That is exactly what the other rows are: Notice row 2 is rotating clockwise one cycle. Thus the DFT is a bank of filters:

And here is the frequency response for each bin of the 4 point DFT. The horizontal axis in this plot is going from $0$ to $2\pi$ where $2\pi$ is the sampling rate. While the previous plot above is centered on zero going from $-\pi$ to $\pi$. (Similar to what the MATLAB command fftshift provides.

So because the DFT provides distinct rotations centered on each bin we get the results as a filter centered on each bin. To center the moving average filter on any other frequency (with infinite precision), simply rotate at that exact frequency.

For the example of the 4 point moving average, the coefficents would be given as

$$c_n = \sum_{n=0}^3 e^{j\omega_n n}$$

Where $\omega_n$ is the normalized angular frequency between $0$ and $2\pi$.

I demonstrate this below using $\omega_n = 1$ resulting in the coefficients

$$[e^{j0}, e^{j1}, e^{j2}, e^{j3}]$$

Answer 2

The DFT is a tool to represent the spectrum of any signal. Usually for an N point DFT only N/2 output coefficients are required because for a real signal the DFT is symmetric about the centre.

No filter has infinite precision, neither infinite bandwidth nor numeric representation. A filter with enough precision can be chosen for an application to seem smooth enough.

The DFT though doesn't have anything to do with a filter. It simply represents the spectrum of the signal at it's input.