Blick ins Buch

Fast Fourier Transform and Convolution Algorithms

Henri J. Nussbaumer (Autor)

Buch | Softcover

XII, 276 Seiten

1982 | 2. Second Edition 1982
Springer Berlin (Verlag)
978-3-540-11825-1 (ISBN)

Lese- und Medienproben

Inhaltsverzeichnis (PDF)

Artikel merken

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.

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.

Erscheint lt. Verlag	1.9.1982
Reihe/Serie	Springer Series in Information Sciences
Zusatzinfo	XII, 276 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	445 g
Themenwelt	Mathematik / Informatik ► Mathematik ► Analysis
Themenwelt	Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik
Schlagworte	Algorithmen • algorithms • convolution • Digitales Filter • Faltung (Math.) • Fourier • Fourier-Transformation
ISBN-10	3-540-11825-X / 354011825X
ISBN-13	978-3-540-11825-1 / 9783540118251
Zustand	Neuware