Fast Fourier Transform and Convolution Algorithms

Print on Demand | 1027 Stück | Lieferzeit:3-5 Tage I

74,89 €*

Alle Preise inkl. MwSt. | zzgl. Versand
Henri J. Nussbaumer
446 g
238x156x10 mm

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.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.- 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.- 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.- 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 Algorithm.- 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 FFT.- 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.- 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 Polynomials.- 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 Algorithms.- 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.- 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 Pol
In the first edition of this book, we covered in Chapter 6 and 7 the applications to multidimensional convolutions and DFT's of the transforms which we have introduced, back in 1977, and called polynomial transforms. Since the publication of the first edition of this book, several important new developments concerning the polynomial transforms have taken place, and we have included, in this edition, a discussion of the relationship between DFT and convolution polynomial transform algorithms. This material is covered in Appendix A, along with a presentation of new convolution polynomial transform algorithms and with the application of polynomial transforms to the computation of multidimensional cosine transforms. We have found that the short convolution and polynomial product algorithms of Chap. 3 have been used extensively. This prompted us to include, in this edition, several new one-dimensional and two-dimensional polynomial product algorithms which are listed in Appendix B. Since our book is being used as part of several graduate-level courses taught at various universities, we have added, to this edition, a set of problems which cover Chaps. 2 to 8. Some of these problems serve also to illustrate some research work on DFT and convolution algorithms. I am indebted to Mrs A. Schlageter who prepared the manuscript of this second edition. Lausanne HENRI J. NUSSBAUMER April 1982 Preface to the First Edition This book presents in a unified way the various fast algorithms that are used for the implementation of digital filters and the evaluation of discrete Fourier transforms.