Fast Fourier Transforms (6x9
Version)
Collection Editor:
C. Sidney Burrus
Fast Fourier Transforms (6x9
Version)
Collection Editor:
C. Sidney Burrus
Authors:
C. Sidney Burrus
Matteo Frigo
Steven G. Johnson
Markus Pueschel
Ivan Selesnick
Online:
< http://cnx.org/content/col10683/1.5/
>
C O N N E X I O N S
Rice University, Houston, Texas
This selection and arrangement of content as a collection is copyrighted
by C. Sidney Burrus. It is licensed under the Creative Commons Attribu-
tion 3.0 license (http://creativecommons.org/licenses/by/3.0/).
Collection structure revised: August 24, 2009
PDF generated: October 26, 2012
For copyright and attribution information for the modules contained in
this collection, see p. 351.
❚❛❜❧❡ ♦❢ ❈♦♥t❡♥ts
1 Preface: Fast Fourier Transforms . . . . . . . . . . . . . . . . . . . . . . . 1
2 Introduction: Fast Fourier Transforms . . . . . . . . . . . . . . . . . . 5
3 Multidimensional Index Mapping . . . . . . . . . . . . . . . . . . . . . . . 9
4 Polynomial Description of Signals . . . . . . . . . . . . . . . . . . . . . . 27
5 The DFT as Convolution or Filtering . . . . . . . . . . . . . . . . . . . 35
6 Factoring the Signal Processing Operators . . . . . . . . . . . . . . 51
7 Winograd’s Short DFT Algorithms . . . . . . . . . . . . . . . . . . . . . 57
8 DFT and FFT: An Algebraic View . . . . . . . .. . . . . . . . . . . . . . 89
9 The Cooley-Tukey Fast Fourier Transform
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10 The Prime Factor and Winograd Fourier
Transform Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
11 Implementing FFTs in Practice . . . . . . . . . . . . . . . . . . . . . . 155
12 Algorithms for Data with Restrictions . . . . . . . . . . . . . . . . 199
13 Convolution Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203
14 Comments: Fast Fourier Transforms . . . . . . . . . . . . . . . . . 225
15 Conclusions: Fast Fourier Transforms . . . . . . . . . . . . . . . 231
16 Appendix 1: FFT Flowgraphs . . . . . . . . . . .. . . . . . . . . . . . . 233
17 Appendix 2: Operation Counts for Gen-
eral Length FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
18 Appendix 3: FFT Computer Programs . . . . . . . . . . . . . . . 247
19 Appendix 4: Programs for Short FFTs . . . . . . . . . . . . . . . 297
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
Attributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
iv
Available for free at Connexions
<http://cnx.org/content/col10683/1.5>