Fast Fourier Transform and Convolution Algorithms - Nussbaumer, Henri J.

. .

Sommaire:
1 Introduction.- 1.1 Introductory Remarks.- 1.2 Notations.- 1.3 The Structure of the Book.- 2 Elements of Number Theory and Polynomial Algebra.- 2.1 Elementary Number Theory.- 2.2 Polynomial Algebra.- 3 Fast Convolution Algorithms.- 3.1 Digital Filtering Using Cyclic Convolutions.- 3.2 Computation of Short Convolutions and Polynomial Products.- 3.3 Computation of Large Convolutions by Nesting of Small Convolutions.- 3.4 Digital Filtering by Multidimensional Techniques.- 3.5 Computation of Convolutions by Recursive Nesting of Polynomials.- 3.6 Distributed Arithmetic.- 3.7 Short Convolution and Polynomial Product Algorithms.- 4 The Fast Fourier Transform.- 4.1 The Discrete Fourier Transform.- 4.2 The Fast Fourier Transform Algorithm.- 4.3 The Rader-Brenner FFT.- 4.4 Multidimensional FFTs.- 4.5 The Bruun Algorithm.- 4.6 FFT Computation of Convolutions.- 5 Linear Filtering Computation of Discrete Fourier Transforms.- 5.1 The Chirp z-Transform Algorithm.- 5.2 Rader's Algorithm.- 5.3 The Prime Factor FFT.- 5.4 The Winograd Fourier Transform Algorithm (WFTA).- 5.5 Short DFT Algorithms.- 6 Polynomial Transforms.- 6.1 Introduction to Polynomial Transforms.- 6.2 General Definition of Polynomial Transforms.- 6.3 Computation of Polynomial Transforms and Reductions.- 6.4 Two-Dimensional Filtering Using Polynomial Transforms.- 6.5 Polynomial Transforms Defined in Modified Rings.- 6.6 Complex Convolutions.- 6.7 Multidimensional Polynomial Transforms.- 7 Computation of Discrete Fourier Transforms by Polynomial Transforms.- 7.1 Computation of Multidimensional DFTs by Polynomial Transforms.- 7.2 DFTs Evaluated by Multidimensional Correlations and Polynomial Transforms.- 7.3 Comparison with the Conventional FFT.- 7.4 Odd DFT Algorithms.- 8 Number Theoretic Transforms.- 8.1 Definition ofthe Number Theoretic Transforms.- 8.2 Mersenne Transforms.- 8.3 Fermat Number Transforms.- 8.4 Word Length and Transform Length Limitations.- 8.5 Pseudo Transforms.- 8.6 Complex NTTs.- 8.7 Comparison with the FFT.- Appendix A Relationship Between DFT and Conyolution Polynomial Transform Algorithms.- A.1 Computation of Multidimensional DFT's by the Inverse Polynomial Transform Algorithm.- A.1.1 The Inverse Polynomial Transform Algorithm.- A.1.2 Complex Polynomial Transform Algorithms.- A.1.3 Round-off Error Analysis.- A.2 Computation of Multidimensional Convolutions by a Combination of the Direct and Inverse Polynomial Transform Methods.- A.2.1 Computation of Convolutions by DFT Polynomial Transform Algorithms.- A.2.2 Convolution Algorithms Based on Polynomial Transforms and Permutations.- A.3 Computation of Multidimensional Discrete Cosine Transforms by Polynomial Transforms.- A.3.1 Computation of Direct Multidimensional DCT's.- A.3.2 Computation of Inverse Multidimensional DCT's.- Appendix B Short Polynomial Product Algorithms.- Problems.- References.