Algorithms for programmers ideas and source code
This document is work in progress: read the ”important remarks” near the beginning
J¨org Arndt
[email protected] This document1 was LATEX’d at September 26, 2002
1
This document is online at
http://www.jjj.de/fxt/.
It will stay available online for free.
Contents Some important remarks about this document
6
List of important symbols
7
1 The Fourier transform
8
1.1
The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.2
Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.3
Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.3.1
A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.3.2
Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.3.3
Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . .
13
Saving trigonometric computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
1.4.1
Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
1.4.2
Recursive generation of the sin/cos-values . . . . . . . . . . . . . . . . . . . . . . .
16
1.4.3
Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
Higher radix DIT and DIF algorith