Fast Fourier Transforms

This book focuses on discrete Fourier transforms (DFTs), discrete convolution, and especially fast algorithms for computing them. These topics have been central to digital signal processing since its inception, and new discoveries in hardware, theory, and applications continue to make them important and interesting.

It uses index maps, polynomial decay, operator factorization, and conversion to filters to develop a very general and efficient description of fast algorithms for computing the Discrete Fourier Transform. (DFT). Winograd’s work is described, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided.

C. Sidney Burrus received his PhD from Stanford University in 1965, after which he joined the faculty of Rice University, where he is currently ECE Research Professor.