![Fast Fourier Transform and Convolution Algorithms [electronic resource] /](/search/themes/bootstrap3/images/libros.png)
Fast Fourier Transform and Convolution Algorithms [electronic resource] /
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. The book consists of eight chapters. The first two chapters are devoted to background information and to introductory material on number theory and polynomial algebra. This section is limited to the basic concepts as they apply to other parts of the book. Thus, we have restricted our discussion of number theory to congruences, primitive roots, quadratic residues, and to the properties of Mersenne and Fermat numbers. The section on polynomial algebra deals primarily with the divisibility and congruence properties of polynomials and with algebraic computational complexity. The rest of the book is focused directly on fast digital filtering and discrete Fourier transform algorithms. We have attempted to present these techniques in a unified way by using polynomial algebra as extensively as possible. This objective has led us to reformulate many of the algorithms which are discussed in the book. It has been our experience that such a presentation serves to clarify the relationship between the algorithms and often provides clues to improved computation techniques. Chapter 3 reviews the fast digital filtering algorithms, with emphasis on algebraic methods and on the evaluation of one-dimensional circular convolutions. Chapters 4 and 5 present the fast Fourier transform and the Winograd Fourier transform algorithm.
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Texto biblioteca |
| Language: | eng |
| Published: |
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer,
1981
|
| Subjects: | Mathematics., Numerical analysis., Numerical Analysis., |
| Online Access: | http://dx.doi.org/10.1007/978-3-662-00551-4 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| id |
KOHA-OAI-TEST:225531 |
|---|---|
| record_format |
koha |
| institution |
COLPOS |
| collection |
Koha |
| country |
México |
| countrycode |
MX |
| component |
Bibliográfico |
| access |
En linea En linea |
| databasecode |
cat-colpos |
| tag |
biblioteca |
| region |
America del Norte |
| libraryname |
Departamento de documentación y biblioteca de COLPOS |
| language |
eng |
| topic |
Mathematics. Numerical analysis. Mathematics. Numerical Analysis. Mathematics. Numerical analysis. Mathematics. Numerical Analysis. |
| spellingShingle |
Mathematics. Numerical analysis. Mathematics. Numerical Analysis. Mathematics. Numerical analysis. Mathematics. Numerical Analysis. Nussbaumer, Henri J. author. SpringerLink (Online service) Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| description |
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. The book consists of eight chapters. The first two chapters are devoted to background information and to introductory material on number theory and polynomial algebra. This section is limited to the basic concepts as they apply to other parts of the book. Thus, we have restricted our discussion of number theory to congruences, primitive roots, quadratic residues, and to the properties of Mersenne and Fermat numbers. The section on polynomial algebra deals primarily with the divisibility and congruence properties of polynomials and with algebraic computational complexity. The rest of the book is focused directly on fast digital filtering and discrete Fourier transform algorithms. We have attempted to present these techniques in a unified way by using polynomial algebra as extensively as possible. This objective has led us to reformulate many of the algorithms which are discussed in the book. It has been our experience that such a presentation serves to clarify the relationship between the algorithms and often provides clues to improved computation techniques. Chapter 3 reviews the fast digital filtering algorithms, with emphasis on algebraic methods and on the evaluation of one-dimensional circular convolutions. Chapters 4 and 5 present the fast Fourier transform and the Winograd Fourier transform algorithm. |
| format |
Texto |
| topic_facet |
Mathematics. Numerical analysis. Mathematics. Numerical Analysis. |
| author |
Nussbaumer, Henri J. author. SpringerLink (Online service) |
| author_facet |
Nussbaumer, Henri J. author. SpringerLink (Online service) |
| author_sort |
Nussbaumer, Henri J. author. |
| title |
Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| title_short |
Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| title_full |
Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| title_fullStr |
Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| title_full_unstemmed |
Fast Fourier Transform and Convolution Algorithms [electronic resource] / |
| title_sort |
fast fourier transform and convolution algorithms [electronic resource] / |
| publisher |
Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, |
| publishDate |
1981 |
| url |
http://dx.doi.org/10.1007/978-3-662-00551-4 |
| work_keys_str_mv |
AT nussbaumerhenrijauthor fastfouriertransformandconvolutionalgorithmselectronicresource AT springerlinkonlineservice fastfouriertransformandconvolutionalgorithmselectronicresource |
| _version_ |
1756270860513050624 |
| spelling |
KOHA-OAI-TEST:2255312018-07-31T00:05:47ZFast Fourier Transform and Convolution Algorithms [electronic resource] / Nussbaumer, Henri J. author. SpringerLink (Online service) textBerlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer,1981.engThis 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. The book consists of eight chapters. The first two chapters are devoted to background information and to introductory material on number theory and polynomial algebra. This section is limited to the basic concepts as they apply to other parts of the book. Thus, we have restricted our discussion of number theory to congruences, primitive roots, quadratic residues, and to the properties of Mersenne and Fermat numbers. The section on polynomial algebra deals primarily with the divisibility and congruence properties of polynomials and with algebraic computational complexity. The rest of the book is focused directly on fast digital filtering and discrete Fourier transform algorithms. We have attempted to present these techniques in a unified way by using polynomial algebra as extensively as possible. This objective has led us to reformulate many of the algorithms which are discussed in the book. It has been our experience that such a presentation serves to clarify the relationship between the algorithms and often provides clues to improved computation techniques. Chapter 3 reviews the fast digital filtering algorithms, with emphasis on algebraic methods and on the evaluation of one-dimensional circular convolutions. Chapters 4 and 5 present the fast Fourier transform and the Winograd Fourier transform algorithm.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 of the 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 -- References.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. The book consists of eight chapters. The first two chapters are devoted to background information and to introductory material on number theory and polynomial algebra. This section is limited to the basic concepts as they apply to other parts of the book. Thus, we have restricted our discussion of number theory to congruences, primitive roots, quadratic residues, and to the properties of Mersenne and Fermat numbers. The section on polynomial algebra deals primarily with the divisibility and congruence properties of polynomials and with algebraic computational complexity. The rest of the book is focused directly on fast digital filtering and discrete Fourier transform algorithms. We have attempted to present these techniques in a unified way by using polynomial algebra as extensively as possible. This objective has led us to reformulate many of the algorithms which are discussed in the book. It has been our experience that such a presentation serves to clarify the relationship between the algorithms and often provides clues to improved computation techniques. Chapter 3 reviews the fast digital filtering algorithms, with emphasis on algebraic methods and on the evaluation of one-dimensional circular convolutions. Chapters 4 and 5 present the fast Fourier transform and the Winograd Fourier transform algorithm.Mathematics.Numerical analysis.Mathematics.Numerical Analysis.Springer eBookshttp://dx.doi.org/10.1007/978-3-662-00551-4URN:ISBN:9783662005514 |