5 ms·
A gentle introduction to the FFT (2002)
- dls2016 5y agoAnd of course Gauss discovered the FFT even before Fourier published about heat transfer.
- deleted 5y ago[deleted]
- shermozle 5y ago3Blue1Brown has an amazing visual explanation which would go well with this: https://www.youtube.com/watch?v=spUNpyF58BY https://www.youtube.com/watch?v=spUNpyF58BY
- N1H1L 5y agoI rediscovered my joy of mathematics with 3Blue1Brown
- jstx1 5y agoAnd an FFT explanation by Reducible - https://www.youtube.com/watch?v=h7apO7q16V0 https://www.youtube.com/watch?v=h7apO7q16V0 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.
- secondcoming 5y agoThe FFT can be computed/visualised with a lens [0]. Quite cool [0] https://youtu.be/Y9FZ4igNxNA?t=567 https://youtu.be/Y9FZ4igNxNA?t=567
- kergonath 5y agoPhysicist’s nitpick: this is Fourier transform (or its discrete equivalent DFT, not to be confused with density functional theory). FFT (fast Fourier transform) is just an algorithm to calculate DFTs. They are used interchangeably by computer people, but they really are not the same thing. 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.
- kergonath 5y agoI guess it would be equally jarring if someone were using “quick sort” in every context where they mean “sort”.
- dotancohen 5y agoOr if one were to "Google" every time they mean search. "Honey, Google the pantry for the maple syrup please!".
- secondcoming 5y agoOk, I'll edit it! Edit: Oops, too late to edit. It's there forever.
- kergonath 5y agoNo need to anyway. Sorry, it wasn’t meant to be personal, or even criticism really. As I said, just a nit (the video was quite good).
- sydd 5y agoI loved this explanation of FFT, full with interactive examples and it makes it also easy to understand how the JPEG compression utilizes FFT https://www.jezzamon.com/fourier/ https://www.jezzamon.com/fourier/ AKA how can you represent an image with Fourier transformations
- hasmanean 5y agoIf you’re new to signal processing, then just remember that the basic algorithm of spectral analysis is the DFT and the FFT is just a clever way to compute it by skipping all the redundant operations. The DFT is trivial.
- joppy 5y agoTrivial, or just straightforward? I don’t think that it’s trivial to know why multiplying by this powers-of-roots-of-unity matrix is interesting, and does the things that it does.
- hasmanean 5y agoThe Correlation of two signals a and b is just multiplying them (if they are vectors, multiply each element of a by the corresponding element of b) Corr(a,b) = sum(a. * b) 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.
- ktpsns 5y agoThe DFT is not trivial at all. The standard way of teaching goes over calculus (including complex numbers), introduces the original Fourier transformation and then discretization (numerical mathematics). Having a PhD in physics, let me assert you that we still have to think twice many times when we "just do a dft" of something. This is also obvious if you look into the manuals, for instance the many variants of a FFT in https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html or https://www.gnu.org/software/gsl/doc/html/fft.html https://www.gnu.org/software/gsl/doc/html/fft.html . This is not trivial.
- roland35 5y agoThe coolest application of an FFT I implemented was for a custom oxygen sensor for a wearable breath measuring device. The sensor would flash a blue light at about 40 kHz, and there was a phosphorescent dye which would flash orange with a phase lag that changed based on temperature and oxygen level. 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.
- dr_coffee 5y agoWas the phosphorescent dye inhaled? What was the physical process responsible for the phase lag? Would love to read more about your device if you ever published your results!
- roland35 5y agoI am not a scientist so I can't pretend to understand it too well, but here is an example of a paper about it: https://www.academia.edu/17195945/O_2_pH_Multisensor_Based_on_One_Phosphorescent_Dye https://www.academia.edu/17195945/O_2_pH_Multisensor_Based_o... 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.
- nayuki 5y agoThe article doesn't explain much; for example it doesn't cover the algebra that allows the FFT to run in O(n log n) time. I recommend instead "The Scientist and Engineer's Guide to Digital Signal Processing": https://www.dspguide.com/pdfbook.htm https://www.dspguide.com/pdfbook.htm