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 . . . . . . . . . . . . . . . . . . . . . . . . .