Circular convolution can be used to implement linear convolution if both sequences
contain sufficient zero samples. The linear convolution of two sequences of lengths L
and M will result in a sequence of length L M À 1. Thus the two sequences must be
extended to the length of L M À 1or greater by zero padding. That is, for the circular
convolution to yield the same result as the linear convolution, the sequence of length L
must be appended with at least M À 1zeros, while the sequence of length M must be
appended with at least L À 1zeros.
Example 7.6: Consider the previous example. If these 8-point sequences h(n) and
x(n) are zero-padded to 16 points, the resulting circular convolution is
yn xn hn f0, 0, 0, 1 , 2, 3, 4, 5, 4, 3, 2, 1 , 0, 0, 0, 0g:
This result is identical to the linear convolution of the two sequences. Thus the
linear convolution discussed in Chapter 5 can be realized by the circular convolu-
tion with proper zero padding.
In MATLAB, zero padding can be implemented using the function zeros. For
example, the 8-point sequence x(n) given in example 7.5 can be zero-padded to 16
points with the following command:
x [1, 1, 1, 1, zeros(1, 11)];
where the MATLAB function zeros(1, N)generates a row vector of N zeros.
7.2 Fast Fourier Transforms
The DFT is a very effective method for determining the frequency spectrum of a time-
domain signal. The only drawback with this technique is the amount of computation
necessary to calculate the DFT coefficients X(k). To compute each X(k), we need
approximately N complex multiplications and N complex additions based on the DFT
defined in (7.1.3). Since we need to compute N samples of X(k) for k 0, 1, . . . , N À 1,
a total of approximately N
2
complex multiplications and N
2
À N complex additions are
required. When a complex multiplication is carried out using digital hardware, it
requires four real multiplications and two real additions. Therefore the number of
arithmetic operations required to compute the DFT is proportional to 4N
2
, which
becomes very large for a large number of N. In addition, computing and storing the
twiddle factors W
kn
N
becomes a formidable task for large values of N.
The same values of the twiddle factors W
kn
N
defined in (7.1.4) are calculated many
times during the computation of DFT since W
kn
N
is a periodic function with a limited
number of distinct values. Because W
N
N
1,
W
kn
N
W
kn
mod N
N
for kn > N:
7:2:1
For example, different powers of W
kn
N
have the same value as shown in Figure 7.1for
N 8. In addition, some twiddle factors have real or imaginary parts equal to 1or 0. By
reducing these redundancies, a very efficient algorithm, called the FFT, exists. For
314
FAST FOURIER TRANSFORM AND ITS APPLICATIONS