4 ms·
Visualizing the Discrete Fourier Transform
- saintx 11y agoI love the way they used color and plain English to describe that function. It would be awesome if a general app for this sort of color coded simple translation were available to help kids learn about mathematics. It'd have to be more inclusive for people with dichromacy and anamalous trichromacy, but there could be settings in the app to compensate for that.
- deleted 11y ago[deleted]
- chestervonwinch 11y agoRather than funny analogies about signals spinning on poles, I think it's relatively easy to understand what the DFT is with just two things that many people already know: 1) knowledge of the complex exponential definition of Fourier series [1], and 2) how to approximate integrals with the left rectangle rule [2]. Take your continuous signal and represent it with a Fourier series. Since the Fourier series is a linear decomposition into integer frequency sinusoids, the coefficients of the series tell you the amount of each frequency contained in the signal. The DFT gives you an approximation of these. The coefficients of the Fourier series of a function are integrals. Approximate these integrals with a left Riemann sum. Integrals turn into sums ... sums turn into a linear system ... the linear system turns into a matrix ... bingobango there's the DFT matrix [3]. [1]: http://users.wpi.edu/~goulet/Matlab/overlap/efs.html http://users.wpi.edu/~goulet/Matlab/overlap/efs.html [2]: https://en.wikipedia.org/wiki/Riemann_sum#Left_Riemann_Sum https://en.wikipedia.org/wiki/Riemann_sum#Left_Riemann_Sum [3]: https://en.wikipedia.org/wiki/DFT_matrix https://en.wikipedia.org/wiki/DFT_matrix
- anjc 11y agoAnd to understand this easy explanation, simply get a degree in mathematics or engineering first, simple! (I appreciate the post though, thanks)
- chestervonwinch 11y agoHence, my reason for prepending "relatively" before "easy" :) I admit the Fourier series part probably isn't standard knowledge. On the other hand, every student of a science-related field has (hopefully!!) at least taken calc one, so should be familiar with the rectangle rule for approximating integrals.
- retbull 11y agoHum wasn't taught in my calc 1 class. I know what DFT is and studied a lot more calc but I didn't get that until at least cal2 when we started working with integrals regularly.
- zo1 11y agoWe did, and yes, we learnt the thing you're mentioning. I however, had absolutely no idea what it was called anymore. But thanks for the links, I now remember.
- hatsunearu 11y agoYup. I think it's not that hard to understand the continuous time fourier transform -- just imagine every signal ever can be expressed as an infinite integral of sinusoids of varying frequencies (the inverse fourier transform), and reverse that process to coax the fourier transform. It is trivial to coax the DTFT and DFT derivations if one understands the CTFT.
- blt 11y agoI like the linear algebra interpretation, where the DFT is a basis change, and the only 'magic' is believing/proving that the Fourier basis is orthogonal. (It's an easy proof.) I still don't understand how the FFT works though...
- 4ad 11y agoIf you understand DFT, it should be very easy to understand FFT. It's the same thing but with an infinite-dimensional vector space. The fact that it's a vector space is the important thing. The infinite dimensionality is relatively a minor detail.
- ablatner 11y agoNo that's not right. The FFT is not infinite dimensional. It's the same dimension as whatever length FFT you take. The FFT is just a set of algorithms for computing the DFT. In general they work by recursively decomposing an N-length DFT into shorter length DFT's. The DTFT on the other hand is "infinite" dimensional in that it takes an infinite time series as input and outputs a continuous spectrum with period of 2pi.
- 4ad 11y agoSorry, This is embarrassing, I must have not drank my coffee... Of course you are right.
- blt 11y agoI was talking about the O(n log n) algorithm that computes the DFT.
- 4ad 11y agoYeah, see my other comment.
- chestervonwinch 11y ago> I like the linear algebra interpretation, where the DFT is a basis change Yea. Maybe a loose analogy would be transforming from RGB to HSV space - the difference in how we can interpret the numbers in one versus the other is what's great.
- JshWright 11y agoOn a similar note, The Engineer Guy's walkthrough of Albert Michelson's Harmonic Analyzer gave me a much better understanding of Fourier analysis in general. https://www.youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqGNW5AeEwq https://www.youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5...
- gruez 11y agoWhy not link to the original site? http://www.billconnelly.net/?p=276 http://www.billconnelly.net/?p=276
- lobo_tuerto 11y agoSome admin should fix the link, the current article don't contribute anything important over the original.
- Thriptic 11y agoI found this video to be an incredibly useful explanation of the Fourier Transform: https://www.youtube.com/watch?v=FjmwwDHT98c https://www.youtube.com/watch?v=FjmwwDHT98c