Fast Fourier TransformsThis book uses an index map, a polynomial decomposition, an operator factorization, and a conversion to a filter to develop a very general and efficient description of fast algorithms to calculate the discrete Fourier transform (DFT). The work of Winograd is outlined, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided. |
Contents
Fast Fourier Transforms | 2 |
This selection and arrangement of content as a collection is copyrighted by C Sidney Burrus It is | 3 |
Fast Fourier Transforms | 5 |
Multidimensional Index Mapping | 7 |
Polynomial Description of Signals | 21 |
The DFT as Convolution or Filtering | 27 |
Factoring the Signal Processing Operators | 39 |
Winograds Short DFT Algorithms | 43 |
Algorithms for Data with Restrictions | 137 |
Convolution Algorithms | 139 |
Fast Fourier Transforms | 153 |
Fast Fourier Transforms | 157 |
FFT Flowgraphs | 159 |
Operation Counts for General Length FFT | 165 |
FFT Computer Programs | 167 |
Programs for Short FFTs | 207 |
An Algebraic View | 65 |
The CooleyTukey Fast Fourier Transform Algorithm | 79 |
The Prime Factor and Winograd Fourier Transform Algo rithms | 97 |
Implementing FFTs in Practice | 109 |
Bibliography | 210 |
| 242 | |
November 18 2012 | 244 |
Other editions - View all
Common terms and phrases
1This content A. V. Oppenheim array ASSP bit-reversal block butter C. S. Burrus cache cache-oblivious cache-oblivious algorithms calculated Chinese remainder theorem ciency codelets coe cients compute Convolution Algorithms Cooley Cooley-Tukey FFT cyclic convolution decimation-in-frequency DFT's Digital Signal Processing discrete fourier transform discrete Hartley transform distributed arithmetic Englewood Cli Equation erent evaluation factor t algorithm fast fourier transform FFTW FFTW's Fourier Transform Algorithm Goertzel algorithm GOTO IEEE Trans IEEE Transactions implementation in-place integers length DFT length-N linear loop M. T. Heideman matrix method modulo Multidimensional Index Mapping number of additions number of multiplications Number Theory operation count optimal output ow graph polynomial algebras Prentice-Hall prime factor algorithm prime length FFTs problem radix radix-2 FFT real data real multiplications recursive residue reduction Section Short DFT Algorithms Sidney Burrus SIMD Speech split-radix FFT Theorem Transactions on Acoustics Transactions on Signal Tukey twiddle factors unscrambler Winograd Fourier Transform Winograd's Short DFT z-transform