Why only calculating N frequency bins in DFT/FFT?

Question

I have a rough understanding of DFT/FFT. By definition: $$ X_{k}=\sum_{n=0}^{N-1} x_{n} \cdot e^{-\frac{i 2 \pi}{N} k n} $$

To me , DFT/FFT works like correlating the signal $x_{n}$ and a signal with known frequency($e^{-\frac{i 2 \pi}{N} k n}$) and finding how similar they are.

1. Why don't we correlate $x_{n}$ with signal other than $e^{-\frac{i 2 \pi}{N} k n}$. Why don't we calculating more frequency bins to get more information (even though it is aliased or something)?
2. Wouldn't it be like calculating the DTFT of the windowed and sampled time signal if we reduce the frequency bin size to a really small value?

Thanks.

Answer 1

You certainly can do this and it is done in other implementations of the Fourier Transform. With the current spacing as done, each bin is orthogonality spaced so results in a lossless mapping from time to frequency, and results in the efficient FFT implementation. If two frequency values are spaced closer than $1/T$ where $T$ is the total time duration of the signal, then the results will be correlated and therefore somewhat redundant. (To note, once we window with other than the rectangular window, adjacent bins will again be correlated and we will still have some of this redundancy which leads to overestimation of noise when the DFT is used to measure a noise floor or wideband signal that occupies multiple bins).

Answer 2

Why don't we …

We can do that, but it simply wouldn't be called the DFT anymore. The DFT is simply defined that way, to be an orthogonal base transform from $N$-dimensional time vectors to $N$-dimensional Fourier coefficient vectors.

So, we need to have an input size == output size relation. Only the equidistant placement of frequencies yields an orthogonal matrix, so that's what's done.

Wouldn't it be like calculating the DTFT of the windowed and sampled time signal if we reduce the frequency bin size to a really small value?

How would we do that? We have $N$ samples to work with. If we want the mapping to be surjective in $\mathbb C^N\mapsto\mathbb C^N$, we can only get $N$ dimensions on the output.

So, to increase the frequency resolution, we'd need to increase $N$, and the good news is that for $N$-periodic signals that are sufficiently well-behaved, the $N$-point DFT does indeed converge point-wise against the continuous Fourier transform for $N\to\infty$; in the end, that's, however, a result that depends on the convergence of a sum to an integral (namely, the time-continuos Fourier integral). The $N$-point DFT of $f(\Delta t\cdot n)_{n=0,\ldots,N-1}$ converging to the FT implies that $f(t)\cdot e^{j\omega t}$ is Riemann-integrable; however, we know quite a few functions $f$ for which that's not the case, and which still have a Fourier transform.

The most famous class of these signals are those with a discontinuity, a "jump": for those, the effect that the spectrum from finite-length observation does never converge everywhere is called Gibbs phenomenon.