CHAPTER 2

THE DISCRETE FOURIER TRANSFORM

**2.1 OVERVIEW**

In this chapter we introduce the *discrete Fourier transform* (DFT) and *inverse discrete Fourier transform* (IDFT) for analyzing sampled signals and images. We’ve already developed the mathematics that underlies these tools: the formula *α _{k}* = (

**v, E**

_{k})/

*N*behind equation (1.34) in the last chapter is, up to a minor modification, the DFT, while equation (1.34) is itself the IDFT.

But rather than jumping straight to the definition of the DFT and IDFT, it may be useful to first discuss some basic facts about the notions of *time domain* and *frequency domain*. We’ll also pause to a look at a very simple computational example that can help build some important intuition about how the DFT and frequency domain are used. As usual, we’ll consider the one-dimensional case of signals first and then move to two dimensions.

Before proceeding futher, we should remark that the definition of these transforms varies slightly from text to text. However, the definitions usually only differ by a scaling or “normalizing” constant. We selected our normalization to be algebraically convenient and consistent with Matlab. For a more comprehensive account of the DFT, see [8],

**2.2 THE TIME DOMAIN AND FREQUENCY DOMAIN**

In the previous chapter we presented a few different mathematical models associated to one-dimensional signals. In the analog case, the signal is a function *x*(*t*) of a real variable *t*, and we usually view *t* as time. In the discrete case, the signal ...