DSP Lecture 11: Radix-2 Fast Fourier Transforms

ECSE-4530 Digital Signal Processing
Rich Radke, Rensselaer Polytechnic Institute
Lecture 11: Radix-2 Fast Fourier Transforms (10/9/14)
0:00:02 Recap of DFT and DTFT; what is the FFT?
0:02:07 The DFT formula
0:04:42 The naive DFT formula is O(N^2)
0:06:41 Characteristics of FFT algorithms
0:08:32 Simplifications involving W_N
0:11:35 Decimation in time
0:17:11 The DIT formula
0:20:02 Example with N=8: block diagram
0:23:05 Completed block diagram (first stage)
0:24:07 Computational cost of first-stage decomposition
0:25:09 Going down another level
0:29:05 Completed block diagram (second stage)
0:31:36 Going down to length-2 DFTs
0:34:23 Completed block diagram (all stages)
0:34:52 The final computational cost is O(N log N)
0:36:48 The "butterfly"
0:39:18 Computations can be done in place
0:41:16 Bit-reversed ordering
0:43:11 Matrix interpretation of decimation in time
0:55:06 F_8 in terms of F_4
0:56:03 Twiddle factors
0:57:40 Decimation in frequency
Follows Section 8.1.3 of the textbook (Proakis and Manolakis, 4th ed.).