Fast Fourier Transforms

Format:

Book

Author/Creator:

Burrus, C. S., author.

Language:

English

Subjects (All):

Computer science--Textbooks.

Computer science.

Physical Description:

1 online resource

Place of Publication:

[Place of publication not identified] OpenStax CNX [2012]

Language Note:

In English.

Summary:

This book focuses on the discrete Fourier transform (DFT), discrete convolution, and, particularly, the fast algorithms to calculate them. These topics have been at the center of digital signal processing since its beginning, and new results in hardware, theory and applications continue to keep them important and exciting. This book uses an index map, a polynomial decomposition, an operator factorization, and a conversion to a filter to develop a very general and efficient description of fast algorithms to calculate the discrete Fourier transform (DFT). The work of Winograd is outlined, chapters by Selesnick, Pueschel, and Johnson are included, and computer programs are provided.

Contents:

1 Preface: Fast Fourier Transforms

2 Introduction: Fast Fourier Transforms

3 Multidimensional Index Mapping

4 Polynomial Description of Signals

5 The DFT as Convolution or Filtering

6 Factoring the Signal Processing Operators

7 Winograd's Short DFT Algorithms

8 DFT and FFT: An Algebraic View

9 The Cooley-Tukey Fast Fourier Transform Algorithm

10 The Prime Factor and Winograd Fourier Transform Algorithms

11 Implementing FFTs in Practice

12 Algorithms for Data with Restrictions

13 Convolution Algorithms

14 Comments: Fast Fourier Transforms

15 Conclusions: Fast Fourier Transforms

16 Appendix 1: FFT Flowgraphs

17 Appendix 2: Operation Counts for General Length FFT

18 Appendix 3: FFT Computer Programs

19 Appendix 4: Programs for Short FFTs

Notes:

CC BY

Description based on print resource

OCLC:

1000323682