Fast Fourier Transforms (6x9 Version) by C. Sidney Burrus - HTML preview

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>