Nguồn ngoài

Fast Fourier Transforms

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.

Electrical Engineering Engineering

Tác giả: C. Sidney Burrus
Nhà xuất bản: Rice University
Nguồn: LibreTexts
Giấy phép: CC BY
Ngôn ngữ: EN

Đọc trực tuyến Tải PDF (nguồn mở)

Mục lục· 74 mục

01: Fast Fourier Transforms
1.01: Introduction
02: Multidimensional Index Mapping
2.01: Introduction
2.02: The Index Map
2.03: In-Place Calculation of the DFT and Scrambling
2.04: Efficiencies Resulting from Index Mapping with the DFT
2.05: The FFT as a Recursive Evaluation of the DFT
03: Polynomial Description of Signals
3.01: Introduction
3.02: Polynomial Reduction and the Chinese Remainder Theorem
3.03: The DFT as a Polynomial Evaluation
04: The DFT as Convolution or Filtering
4.01: Introduction
4.02: Rader's Conversion of the DFT into Convolution
4.03: The Chirp Z-Transform or Bluestein's Algorithm
4.04: Goertzel's Algorithm or A Better DFT Algorithm
4.05: The Quick Fourier Transform (QFT)
05: Factoring the Signal Processing Operators
5.01: Introduction
5.02: The FFT from Factoring the DFT Operator
5.03: Algebraic Theory of Signal Processing Algorithms
06: Winograd's Short DFT Algorithms
6.01: Introduction
6.02: Winograd Fourier Transform Algorithm (WFTA)
6.03: The Bilinear Structure
6.04: Winograd's Complexity Theorems
6.05: The Automatic Generation of Winograd's Short DFTs
07: DFT and FFT - An Algebraic View
7.01: Introduction
7.02: Polynomial Algebras and the DFT
7.03: Algebraic Derivation of the Cooley-Tukey FFT
7.04: Discussion and Further Reading
08: The Cooley-Tukey Fast Fourier Transform Algorithm
8.01: Introduction
8.02: Basic Cooley-Tukey FFT
8.03: Modifications to the Basic Cooley-Tukey FFT
8.04: The Split-Radix FFT Algorithm
8.05: Evaluation of the Cooley-Tukey FFT Algorithms
8.06: The Quick Fourier Transform - An FFT based on Symmetries
09: The Prime Factor and Winograd Fourier Transform Algorithms
9.01: Introduction
9.02: The Prime Factor Algorithm
9.03: The Winograd Fourier Transform Algorithm
9.04: Modifications of the PFA and WFTA Type Algorithms
9.05: Evaluation of the PFA and WFTA
10: Implementing FFTs in Practice
10.01: Introduction
10.02: Review of the Cooley-Tukey FFT
10.03: Goals and Background of the FFTW Project
10.04: FFTs and the Memory Hierarchy
10.05: Adaptive Composition of FFT Algorithms
10.06: Generating Small FFT Kernels
10.07: SIMD instructions
10.08: Numerical Accuracy in FFTs
10.09: Concluding Remarks
11: Algorithms for Data with Restrictions
11.01: Introduction
11.02: Various Approaches to Developing Special Methods
11.03: Special Algorithms for input Data that is mostly Zero
12: Convolution Algorithms
12.01: Introduction
12.02: Fast Convolution by Overlap-Add and Overlap-Save
12.03: Block Processing - a Generalization of Overlap Methods
12.04: Direct Fast Convolution and Rectangular Transforms
12.05: Number Theoretic Transforms for Convolution
13: Comments and Conclusion
13.01: Comments
13.02: Conclusion
14: Appendix
14.01: Appendix 1 - FFT Flowgraphs
14.02: Appendix 2 - Operation Counts for General Length FFT
14.03: Appendix 3 - FFT Computer Programs
14.04: Appendix 4 - Programs for Short FFTs