An overview with Julia of what the Discrete Fourier Transform (DFT) does, by applying it to analyze sounds, including how it is defined, along with a comparison between the runtime of a naively-
[Click "↓ ↓ ↓ Show More " for the Outline:]
implemented DFT and one using the Fast Fourier Transform (FFT) algorithm.


Course homepage: https://computationalthinking.mit.edu...
Pluto notebook: https://github.com/mitmath/18S191/blo...

0:00 Introduction
2:00 Time series data from sound recordings
2:37 Julia notebook: Playing with sound - WAV files
4:02 Drawing waveforms
5:45 Effect of frequency
6:00 Combining (superposing) different frequencies
6:45 Julia: FFT function
6:59 Discrete Fourier Transform (DFT) vs Fast Fourier Transform (FFT)
8:18 Plotting an FFT
8:58 Musical overtones: Magnitude of the FFT
12:13 Analyzing a sound file using the FFT
12:53 Defining the DFT mathematically
13:35 First term of the DFT
14:08 Visualizing the DFT in the complex plane
14:20 Equally-spaced points on unit circle in the complex plane
15:12 Idea of Fourier transform of a signal: walking around a circle
16:13 Adding complex numbers as adding vectors
17:10 Magnitude of DFT gives information about frequency
17:35 Angle of DFT gives information about phase
18:39 Interpreting the second term of the DFT
21:06 General formula for DFT
22:10 Implementing the DFT in Julia
23:01 Julia: Writing "i" as im
23:33 Julia: Array comprehension
25:35 Comparison of DFT with FFT results
26:49 Julia: isapprox for testing approximate equality
26:56 Efficiency of the implementation
28:23 Pre-computing an array of powers
28:57 Julia: Modulo (%)
29:14 Julia: OffsetArray for zero-based indexing
32:02 Computational complexity of DFT vs FFT
34:12 DFT as polynomials

Video on FFT from Reducible:    • The Fast Fourier Transform (FFT): Mos...