Fourier Transforms

CHAPTER 3 THE DISCRETE FOURIER TRANSFORM

In the last chapter, it was shown how an arbitrary vector in an N-dimensional space can be represented as a linear combination of N mutually orthogonal basis vectors in that space. In this chapter we consider , the space of N-dimensional complex vectors, and a basis {ϕ₀, ϕ₁, …ϕ_{N − 1}} of complex exponential vectors:

The expansion in this basis of a vector is

and is called the discrete Fourier transform (DFT) of f.

The DFT is the principal computational tool of Fourier analysis and a logical place to begin our study. Being a mapping between finite-dimensional spaces, its mathematics are uncomplicated by questions about convergence of series or integrals. We will derive the basic properties of the DFT, including several theorems that facilitate its application, and develop the fast Fourier transform (FFT) algorithm for computing the DFT. The chapter concludes by introducing a close relative of the DFT, the discrete cosine transform (DCT), which is widely applied in signal compression algorithms such as JPEG.

3.1 SINUSOIDAL SEQUENCES