Intuition of fft over time to frequency

Question

I understand how FFT (DFT) works. It acts as a change of basis. However, while many websites describe fft as a method that convert time domain stuff to frequency domain stuff, I still do not know why it transforms a vector in time domain to one in frequency domain. Which part of fft is doing this? It’s not trivial for me to find the corresponding part.

Answer 1

Let's say you have a $T$-periodic function $f$, and you want to numerically compute its Fourier series.

This Fourier series gives you the sequence of coefficients for frequencies that are multiples of the "base" frequency.

Say you are using the rectangle rule, to approximate the integral

$$c_n=\dfrac1T\int_{0}^{T} f(t) \exp(-2i\pi n\frac tT)\;\mathrm dt$$

The approximation with $N$ points is

$$\hat c_n=\frac{1}{N}\sum_{k=0}^{N-1}f(\frac{kT}{N})\exp(-2i\pi \frac {kn}N)$$

Apart from the $1/N$ coefficient, it's exactly the discrete Fourier transform.

An interesting follow-up would be to search why you can't really find coefficients for all frequencies (I mean, not all multiples of the base frequency), and link this with the Nyquist frequency and aliasing. Basically, the problem comes from $\hat c_{n+N}=\hat c_n$ and $\hat c_{N-n}=\overline{\hat c_n}$ (for real $f$), thus only $N/2$ coefficients are useful.

Answer 2

First some background. The FFT is an approximation to the integral transform involving sin(t) and cos(t) called the Fourier transform. These integral transforms, as with any integral transform (eg the Laplace transform, and others) change from one domain to another by replacing the independent variable. In the case of the Fourier transform, the time domain is replaced with the frequency domain (or variable).

The FFT is a digital approximation to the Fourier transform. The original Fourier transform involves an integral over infinite time and is smooth. The FFT algorithm is over a finite time and is discrete - hence the approximation. I suggest you study the original definition of the Fourier transform (which can be viewed as special case of the Laplace transform).

Hope this helps

Answer 3

Quick nit-pick before the answer. You asked about DFT and FFT. Those are the Discrete Fourier Transform, which is computed by the Fast Fourier Transform algorithm. FFT is the algorithm, DFT is the mathematical function. It turns out Fourier Transforms are more general, and the concept is the same, but I'll stick with DFT here.

---

You know how two real vectors at right angles have a dot product of zero? That's a property called orthogonality. It turns out that sine waves have it, too.

Try this yourself. Evaluate the following:

$$\int_0^{2\pi} \sin(2t) \cdot \sin(2t) dt$$ $$\int_0^{2\pi} \sin(2t) \cdot \sin(3t) dt$$

You'll find that the first one evaluates to $\pi$, and the other evaluates to $0$. The cool part about this is that we can "pull out frequencies" from a function. Imagine we had a function of the form $f(t) = g_1 \sin(t) + g_2\sin(2t) + \ldots + g_n\sin(nt)$. Suppose we did the following analysis:

$$g(n) = \frac{1}{\pi}\int_0^{2\pi} f(t) \sin(nt) dt$$

Then we would get $g(n) = g_n$, because the integral is $g_n \cdot \pi$ if the frequencies are the same, and it's $0$ if they aren't. This way, we recover the amplitude of each frequency from an arbitrary function.

In fact, we've gone from the time domain (parameter $t$) to the frequency domain (of integral frequency $n$, but you could imagine other frequencies). The orthogonality of the sine function is what does this.

You may see the Fourier transform written, as it is on Wikipedia, like:

$$\hat{f}(\xi) = \int_{-\infty}^\infty f(x) e^{2 \pi i x \xi} d\xi$$

Just think of $\xi$ as the frequency, and $x$ as the time, and remember Euler's formula $e^{2 \pi i \xi} = \cos(2 \pi \xi) + i \sin (2 \pi \xi)$. The orthogonality principle still holds, although this is more generalized for the complex domain.

Answer 4

For an entirely different understanding of what the DFT actually means, check out my blog article DFT Graphical Interpretation: Centroids of Weighted Roots of Unity. I disagree entirely with some of the other answers saying the DFT is best understood by understanding the continuous FT first. That path is fraught with difficult math and plenty of opportunities for misconceptions.

In short, the DFT can be thought of as a weighted average of an evenly spaced set of points around the unit circle. For each bin index, the signal is stretched that many times and wrapped around the circle. So, if your signal has seven "humps" in it, when it is stretched and wrapped seven time, all the humps align and throw the average off center.