Book:H.J. Nussbaumer/Fast Fourier Transform and Convolution Algorithms/Second Edition
Jump to navigation
Jump to search
H.J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms (2nd Edition)
Published $\text {1982}$, Springer-Verlag
- ISBN 0-387-11825-X
Subject Matter
Contents
- Preface to the Second Edition (Lausanne, April 1982)
- Preface to the First Edition (La Gaude, November 1980)
- Chapter 1 Introduction
- 1.1 Introductory Remarks
- 1.2 Notation
- 1.3 The Structure of the Book
- Chapter 2 Elements of Number Theory and Polynomial Algebra
- 2.1 Elementary Number Theory
- 2.1.1 Divisibility of Integers
- 2.1.2 Congruences and Residues
- 2.1.3 Primitive Roots
- 2.1.4 Quadratic Residues
- 2.1.5 Mersenne and Fermat Numbers
- 2.2 Polynomial Algebra
- 2.2.1 Groups
- 2.2.2 Rings and Fields
- 2.2.3 Residue Polynomials
- 2.2.4 Convolution and Polynomial Product Algorithms in Polynomial Algebra
- 2.1 Elementary Number Theory
- Chapter 3 Fast Convolution Algorithms
- 3.1 Digital Filtering Using Cyclic Convolutions
- 3.1.1 Overlap-Add Algorithm
- 3.1.2 Overlap-Save Algorithm
- 3.2 Computation of Short Convolutions and Polynomial Products
- 3.2.1 Computation of Short Convolutions by the Chinese Remainder Theorem
- 3.2.2 Multiplications Modulo Cyclotomic Polynomials
- 3.2.3 Matrix Exchange Algorithm
- 3.3 Computation of Large Convolutions by Nesting of Small Convolutions
- 3.3.1 The Agarwal-Cooley Algorithm
- 3.3.2 The Split Nesting Algorithm
- 3.3.3 Complex Convolutions
- 3.3.4 Optimum Block Length for Digital Filters
- 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
- 3.7.1 Short Circular Convolution Algorithms
- 3.7.2 Short Polynomial Product Algorithms
- 3.7.3 Short Aperiodic Convolution Algorithms
- 3.1 Digital Filtering Using Cyclic Convolutions
- Chapter 4 The Fast Fourier Transform
- 4.1 The Discrete Fourier Transform
- 4.1.1 Properties of the DFT
- 4.1.2 DFTs of Real Sequences
- 4.1.3 DFTs of Odd and Even Sequences
- 4.2 The Fast Fourier Transform Algorithm
- 4.2.1 The Radix-2 FFT Algorithm
- 4.2.2 The Radix-4 FFT Algorithm
- 4.2.3 Implementation of FFT Algorithms
- 4.2.4 Quantization Effects in the FFT
- 4.3 The Rader-Brenner FFT
- 4.4 Multidimensional FFTs
- 4.5 The Bruun Algorithm
- 4.6 FFT Computation of Convolutions
- 4.1 The Discrete Fourier Transform
- Chapter 5 Linear Filtering Computation of Discrete Fourier Transforms
- 5.1 The Chirp $z$-Transform Algorithm
- 5.1.1 Real Time Computation of Convolutions and DFTs Using the Chirp $z$-Transform
- 5.1 2 Recursive Computation of the Chirp $z$-Transform
- 5.1.3 Factorizations in the Chirp Filter
- 5.2 Rader's Algorithms
- 5.2.1 Composite Algorithms
- 5.2.2 Polynomial Formulation of Rader's Algorithm
- 5.2.3 Short DFT Algorithms
- 5.3 The Prime Factor DFT
- 5.3.1 Multidimensional Mapping of One-Dimensional DFTs
- 5.3.2 The Prime Factor Algorithm
- 5.3.3 The Split Prime Factor Algorithm
- 5.4 The Winograd Fourier Transform Algorithm (WFTA)
- 5.4.1 Derivation of the Algorithm
- 5.4.2 Hybrid Algorithms
- 5.4.3 Split Nesting Algorithms
- 5.4.4 Multidimensional DFTS
- 5.4.5 Programming and Quantization Noise Issues
- 5.5 Short DFT Algorithms
- 5.5.1 2-Point DFT
- 5.5.2 3-Point DFT
- 5.5.3 4-Point DFT
- 5.5.4 5-Point DFT
- 5.5.5 7-Point DFT
- 5.5.6 8-Point DFT
- 5.5.7 9-point DFT
- 5.5.8 16-Point DFT
- 5.1 The Chirp $z$-Transform Algorithm
- Chapter 6 Polynomial Transforms
- 6.1 Introduction to Polynomial Transforms
- 6.2 General Definition of Polynomial Transforms
- 6.2.1 Polynomial Transforms with Roots in a Field of Polynonzials
- 6.2.2 Polynomial Transforms with Composite Roots
- 6.3 Computation of Polynomial Transforms and Reductions
- 6.4 Two-Dimensional Filtering Using Polynomial Transforms
- 6.4.1 Two-Dimensional Convolutions Evaluated by Polynomial Transforms and Polynomial Product Algorithms
- 6.4.2 Example of a Two-Dimensional Convolution Computed by Polynomial Transforms
- 6.4.3 Nesting Algorithmic
- 6.4.4 Comparison with Conventional Convolution Algorithms
- 6.5 Polynomial Transforms Defined in Modified Rings
- 6.6 Complex Convolutions
- 6.7 Multidimensional Polynomial Transforms
- Chapter 7 Computation of Discrete Fourier Transforms by Polynomial Transforms
- 7.1 Computation of Multidimensional DFTs by Polynomial Transforms
- 7.1.1 The Reduced DFT Algorithm
- 7.1.2 General Definition of the Algorithm
- 7.1.3 Multidimensional DFTs
- 7.1.4 Nesting and Prime Factor Algorithms
- 7.1.5 DFT Computation Using Polynomial Transforms Defined in Modified Rings of Polynomials
- 7.2 DFTs Evaluated by Multidimensional Correlations and Polynomial Transforms
- 7.2.1 Derivation of the Algorithm
- 7.2.2 Combination of the Two Polynomial Transform Methods
- 7.3 Comparison with the Conventional FFT
- 7.4 Odd DFT Algorithms
- 7.4.1 Reduced DFT Algorithm. $N = 4$
- 7.4.2 Reduced DFT Algorithm. $N = 8$
- 7.4.3 Reduced DFT Algorithm. $N = 9$
- 7.4.4 Reduced DFT Algorithm. $N = 16$
- 7.1 Computation of Multidimensional DFTs by Polynomial Transforms
- Chapter 8 Number Theoretic Transforms
- 8.1 Definition of the Number Theoretic Transforms
- 8.1.1 General Properties of NTTs
- 8.2 Mersenne Transforms
- 8.2.1 Definition of Mersenne Transforms
- 8.2.2 Arithmetic Modulo Mersenne Numbers
- 8.2.3 Illustrative Example
- 8.3 Fermat Number Transforms
- 8.3. 1 Definition of Fermat Number Transforms
- 8.3.2 Arithmetic Modulo Fermat Numbers
- 8.3.3 Computation of Complex Convolutions by FNTs
- 8.4 Word Length and Transform Length Limitations
- 8.5 Pseudo Transforms
- 8.5.1 Pseudo Mersenne Transforms
- 8.5.2 Pseudo Fermat Number Transforms
- 8.6 Complex NTTs
- 8.7 Comparison with the FFT
- 8.1 Definition of the Number Theoretic Transforms
- Appendix A Relationship Between DFT and Convolution Polynomial Transform Algorithms
- A.l Computation of Multidimensional DFT'S by the Inverse Polynomial Transfonn 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 Transform 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
- A.l Computation of Multidimensional DFT'S by the Inverse Polynomial Transfonn Algorithm
- Appendix B Short Polynomial Product Algorithms
- Problems
- References
- Subject Index