Introduction

In this chapter we will study the problem of computing the components

of the discrete Fourier transform of given complex numbers f[0], f[1], , f[ N ?1]. We write these relations in the compact form

where

are complex N-component column vectors and where the N N DFT matrix

is expressed in terms of powers of

We will use indices 0, 1, , N ?1 (rather than 1, 2, , N) for the rows of vectors and for the rows and columns of matrices. When it is necessary, we will use a subscript to specify the size of a matrix, e.g., I ₈ , will denote the 8 8 identity matrix and the 16 16 DFT matrix, respectively.

Given an N N matrix

and an N-vector

we can evaluate the components of

by using the algorithm

The cost of this computation is approximately N ² operations when we define an operation to be the work we do as we execute the statement

from the inner loop. [More specifically, we fetch a _kn , b _n , and the old value of S from storage; we form the product a _kn b _n and the sum S+(a _kn b _n ); and we store this result as the new value of S.] Of course, complex arithmetic requires more effort than real arithmetic, and...