Fast Fourier Transform and Convolution AlgorithmsThis 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. |
Other editions - View all
Common terms and phrases
a₁ a₂ aperiodic convolution arithmetic operations b₁ calculated Chinese remainder reconstruction Chinese remainder theorem circular convolution coefficients complex multiplications convolution algorithms convolution of length correlation corresponding cyclic convolutions cyclotomic polynomials defined modulo DFT of length DFTs computed digital filter discrete Fourier transforms evaluated Fermat numbers FFT algorithm h₁ h₂ implemented input sequences integers inverse k₁ k₂ L₁ m₁ m₂ Mersenne number Mersenne transforms modulo P(z modulo q modulo z multidimensional DFT mutually prime N,N₂ N₁ N₁N₂ N₂ nesting method nomial NTTs number of additions number of arithmetic number of multiplications number of operations Number of real odd prime permutation polynomial multiplication modulo polynomial product modulo prime factor algorithm primitive roots quadratic nonresidue quadratic residue Rader's algorithm real multiplications reduced DFTs relatively prime root of order scalar Sect split nesting t₁ tions total number twiddle factors two-dimensional convolution u₁ X₁ Y₁ z₁