Fast Fourier Transforms

by C. Sidney Burrus

Read here Read at LibreTextsPDF

This book focuses on the discrete Fourier transform (DFT), discrete convolution, and, particularly, the fast algorithms to calculate them. These topics have been at the center of digital signal processing since its beginning, and new results in hardware, theory and applications continue to keep them important and exciting.

Description from LibreTexts.

Publisher
Rice University
Subjects
Engineering, Electrical Engineering
Licence
CC BY, as LibreTexts states it
Who can read
Tweens profiles and older, judged from its title and subjects

Contents

LibreTexts writes equations in TeX, and here they show as TeX; the PDF has them typeset.

  1. Front Matter
  2. TitlePage
  3. InfoPage
  4. Table of Contents
  5. Licensing
  6. 1: Fast Fourier Transforms
  7. 1.1: Introduction
  8. 2: Multidimensional Index Mapping
  9. 2.1: Introduction
  10. 2.2: The Index Map
  11. 2.3: In-Place Calculation of the DFT and Scrambling
  12. 2.4: Efficiencies Resulting from Index Mapping with the DFT
  13. 2.5: The FFT as a Recursive Evaluation of the DFT
  14. 3: Polynomial Description of Signals
  15. 3.1: Introduction
  16. 3.2: Polynomial Reduction and the Chinese Remainder Theorem
  17. 3.3: The DFT as a Polynomial Evaluation
  18. 4: The DFT as Convolution or Filtering
  19. Front Matter
  20. TitlePage
  21. InfoPage
  22. 4.1: Introduction
  23. 4.2: Rader's Conversion of the DFT into Convolution
  24. 4.3: The Chirp Z-Transform or Bluestein's Algorithm
  25. 4.4: Goertzel's Algorithm or A Better DFT Algorithm
  26. 4.5: The Quick Fourier Transform (QFT)
  27. Back Matter
  28. Index
  29. 5: Factoring the Signal Processing Operators
  30. 5.1: Introduction
  31. 5.2: The FFT from Factoring the DFT Operator
  32. 5.3: Algebraic Theory of Signal Processing Algorithms
  33. 6: Winograd's Short DFT Algorithms
  34. 6.1: Introduction
  35. 6.2: Winograd Fourier Transform Algorithm (WFTA)
  36. 6.3: The Bilinear Structure
  37. 6.4: Winograd's Complexity Theorems
  38. 6.5: The Automatic Generation of Winograd's Short DFTs
  39. 7: DFT and FFT - An Algebraic View
  40. 7.1: Introduction
  41. 7.2: Polynomial Algebras and the DFT
  42. 7.3: Algebraic Derivation of the Cooley-Tukey FFT
  43. 7.4: Discussion and Further Reading
  44. 8: The Cooley-Tukey Fast Fourier Transform Algorithm
  45. Front Matter
  46. TitlePage
  47. InfoPage
  48. 8.1: Introduction
  49. 8.2: Basic Cooley-Tukey FFT
  50. 8.3: Modifications to the Basic Cooley-Tukey FFT
  51. 8.4: The Split-Radix FFT Algorithm
  52. 8.5: Evaluation of the Cooley-Tukey FFT Algorithms
  53. 8.6: The Quick Fourier Transform - An FFT based on Symmetries
  54. Back Matter
  55. Index
  56. 9: The Prime Factor and Winograd Fourier Transform Algorithms
  57. 9.1: Introduction
  58. 9.2: The Prime Factor Algorithm
  59. 9.3: The Winograd Fourier Transform Algorithm
  60. 9.4: Modifications of the PFA and WFTA Type Algorithms
  61. 9.5: Evaluation of the PFA and WFTA
  62. 10: Implementing FFTs in Practice
  63. 10.1: Introduction
  64. 10.2: Review of the Cooley-Tukey FFT
  65. 10.3: Goals and Background of the FFTW Project
  66. 10.4: FFTs and the Memory Hierarchy
  67. 10.5: Adaptive Composition of FFT Algorithms
  68. 10.6: Generating Small FFT Kernels
  69. 10.7: SIMD instructions
  70. 10.8: Numerical Accuracy in FFTs
  71. 10.9: Concluding Remarks
  72. 11: Algorithms for Data with Restrictions
  73. 11.1: Introduction
  74. 11.2: Various Approaches to Developing Special Methods
  75. 11.3: Special Algorithms for input Data that is mostly Zero
  76. 12: Convolution Algorithms
  77. 12.1: Introduction
  78. 12.2: Fast Convolution by Overlap-Add and Overlap-Save
  79. 12.3: Block Processing - a Generalization of Overlap Methods
  80. 12.4: Direct Fast Convolution and Rectangular Transforms
  81. 12.5: Number Theoretic Transforms for Convolution
  82. 13: Comments and Conclusion
  83. 13.1: Comments
  84. 13.2: Conclusion
  85. 14: Appendix
  86. 14.1: Appendix 1 - FFT Flowgraphs
  87. 14.2: Appendix 2 - Operation Counts for General Length FFT
  88. 14.3: Appendix 3 - FFT Computer Programs
  89. 14.4: Appendix 4 - Programs for Short FFTs
  90. Back Matter
  91. Index
  92. Index
  93. Glossary
  94. Detailed Licensing