文档介绍：Algorithms for programmers
ideas and source code
This document is work in progress: read the ”important remarks” near the beginning
Arndt
******@
1
This document was LATEX’d at September 26, 2002
1This document is online at /. 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
The discrete Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Symmetries of the Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Radix 2 FFT algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
A little bit of notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Decimation in time (DIT) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Decimation in frequency (DIF) FFT . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Saving putations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Using lookup tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Recursive generation of the sin/cos-values . . . . . . . . . . . . . . . . . . . . . . . 16
Using higher radix algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Higher radix DIT and DIF algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
More notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Decimation in time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Decimation in frequency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Implementation of radix r = px DIF/DIT FFTs . . . . . . . . . . . . . . . . . . . . 19
Split radix Fourier transforms (SRFT) . . . . . . . . . . . . . . . . . . . . . . . . . . .