An Elementary Introduction to the Discrete Fourier Transform

1.1 ComplexNumbers

1.3 Analyzing the Series

1.5 Filtering a Signal

1.6 How Often Does One Sample?

1.7 Notes and References

1.2 Trigonometric Interpolation

1.4 Fourier Frequency Versus Time Frequency

2 Some Mathematical and Computational Preliminaries

2.1 Computing the Twiddle Factors

2.2.1 Real floating-point operation (FLOP) count

2.2.2 Special considerations in computing the FFT

2.3 Expressing Complex Multiply-Adds in Terms of Real Multiply-Adds

2.4 Solving Recurrences to Determine an Unknown Function

2.2 Multiplying Two Complex Numbers

II Sequential FFT Algorithms

3 The Divide-and-Conquer Paradigm and Two Basic FFT Algorithms

3.1 Radix-2 Decimation-In-Time (DIT) FFT

3.1.1 Analyzing the arithmetic cost

3.2 Radix-2 Decimation-In-Frequency (DIF) FFT

3.2.1 Analyzing the arithmetic cost

3.3 Notes and References