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 March 26, 2003
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 1 The Fourier transform
8 10
1.1
The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.2
Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
1.3
Summary of definitions of Fourier transforms * . . . . . . . . . . . . . . . . . . . . . . . .
12
1.4
Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.4.1
A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.4.2
Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.4.3
Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . .
17
Saving trigonometric computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.5.1
Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
1.5.2
Recursive generation of the sin/cos-values . . . . . . . . . . . . . . . . . . . . . . .
19
1.5.3
Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . .