T0001 - The FFT Demystified. V2.1

Contents

Introduction
Definition of DFT and Inverse DFT (IDFT).

Some Simple Transforms.

FFT's are fast DFT Algorithms.
The Radix 2 Decimation In Frequency (DIF) Algorithm.

The Maths.
A Recursive DIF FFT Routine.
DIF FFT Algorithmic Complexity (Why it's fast).
A Recursive 'In Place' DIF FFT Routine.
The 'Classic' Non-Recursive DIF FFT Routine.
Twiddle Factor Tricks.

The Radix 2 Decimation In Time (DIT) Algorithm.

The Maths.
A Recursive DIT FFT Routine.
DIT FFT Algorithmic Complexity (Why it's fast).
A Recursive 'In Place' DIT FFT Routine.
The 'Classic' Non-Recursive DIT FFT Routine.
Twiddle Factor Tricks.

Practical Considerations.

Inverse Transforms.
Scaling.
Frequency Domain Rounding.
DIF or DIT?
Using Bit Reversed Addressing.
Cache Efficiency.
Using a DSP's internal memory.

Multi-Dimensional Transforms.

A 2D Transform.
Evaluation as Multiple 1D Transforms.
Algorithmic Complexity of Multi-Dimensional Radix 2 FFT's.

Mixed Radix Algorithms.

The Maths.
How much time will this save?
Radix 4 Algorithms.

DIF and DIT Decomposition Revisited.

DIF Decomposition.
DIT Decomposition.
Conclusion.

An Algorithm for Prime Length Sequences.

An Example.
A Little of Number Theory.
A Systematic Method.
The Example Again.

FFT of Pure Real Sequences.

Two for the Price of One.
A Different DIT.
Half a Transform.

FFT by Convolution.

The Maths.
The Algorithm.
So how long does it take?

Annex A - IDFT really is the Inverse DFT.
Annex B - Summing Complex Exponential Series.
Annex C - Convolution.

Definition of Convolution for Discrete Signals.
Circular Convolution.
Convolution of Finite Length Sequences.

Annex D - When does FFT Convolution/Correlation Pay?

Direct Convolution.
FFT Convolution.
Comparing of the Results.

Annex E - Interpolation and Decimation.

Interpolation.
Decimation.
Fractional Re-Sampling.

[HOME]
©1999 - Engineering Productivity Tools Ltd.