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