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.