A gentle introduction to the FFT (2002)
earlevel.com
earlevel.com
Using an FFT we could get that phase lag at 40 kHz and back out the % oxygen in exhaled breath! Typical oxygen sensors at the time were not anywhere near fast enough to do that.
The dye was on a small paper disk, not in the air. It was measuring exhaled breath anyways so you weren't inhaling it.
CO2 was another interesting sensor! There is a specific IR frequency it absorbs, so we used that to sense it in real time.
It's in a similar style to 3blue1brown (uses the same visualisation library) but the video focuses specifically on the FFT algorithm, not on Fourier transforms in general. I'm pretty sure Grant himself recommended the Reducible video at some point.
I recommend instead "The Scientist and Engineer's Guide to Digital Signal Processing": https://www.dspguide.com/pdfbook.htm
The DFT is trivial.
The correlation of a signal s with a sine wave of frequency f just gives the signal power at that frequency.
Repeat for a set of regularly spaced of frequency values from 0 to Fs/2 (the maximum frequency you can work with with data sampled at Fs) and you have the DFT. You can even clump the sine waves into a matrix and your DFT gets reduced to a single matrix multiply.
This is much easier to reason about than worrying about how an FFT works which is just a speed optimization (which can be derived from dynamic programming applied to the DFT).
For someone doing signal processing the results are the same. Introducing the FFT without making reference to the DFT is wrapping the subject up in an air of mystery.
The manuals you cite cover several different transforms (not just the DFT) as well as the complexities of the FFT.
It doesn’t have to be a sine wave. You could correlate your signal to a fart sound (or a set of them). It’s a valid transform but it would not be invertible—given a vector of scalar values showing how much your signal resembled each type of fart, you could not reconstruct the original signal.
However you can do that with the FT. It’s invertible and you can recover the signal from the spectrum. So in some sense it doesn’t lose information. Energy in the signal is equal to energy in the Fourier spectrum.
Part of that complexity is because the FFT only works on power-of-2 length (e.g. 1024) input vectors so they have special tricks to work with arbitrary length data.
The DFT has no such restriction.
I’ve read somewhere that if you apply dynamic programming to the DFT (recursive sub problems, memoization) then you end up with the FFT. One of these days I’ll try to derive that.
That aside, yes, it is amazing to play with this sort of things and produce Fourier transforms by shining a light through a physical object.
I remember a lab assignment from undergrad where we de-noised a picture by blocking some parts of its transform before transforming it back. We could remove the noise or the image itself (keeping almost only the noise) by blocking different parts of the beam. It makes the concept of frequency filtering very intuitive.
"Honey, Google the pantry for the maple syrup please!".
Edit: Oops, too late to edit. It's there forever.