3
DISCRETE FOURIER ANALYSIS
The Fourier transform and Fourier series techniques are useful for analyzing continuous signals such as the graph in Figure 3.1. However, for many applications, the signal is a discrete data set (see Figure 3.2), such as the signal coming from a compact disc player. A discrete version of the Fourier transform is needed to analyze discrete signals.
3.1 THE DISCRETE FOURIER TRANSFORM
To motivate the idea behind the discrete Fourier transform, we numerically approximate the coefficients of a Fourier series for a continuous function f(t). The trapezoidal rule for approximating the integral (2π)–1 
F(t) dt with step size h = 2π/n is
where Yj := F(hj) = F(2πj / n), j = 0,..., n. If F(t) is 2π -periodic, then Y0 = Yn and the preceding formula becomes
Figure 3.1. Continuous signal.
Figure 3.2. Discrete signal.
Applying this formula to the computation of the kth complex Fourier coefficient gives
Therefore
where
The sum on the right side of Eq. (3.1) involves ...
