498 Practical MATLAB® Applications for Engineers
The analysis of the circular convolution for f 1 (n) with h(n), denoted by gC(n), is
presented as follows:
First h(n) is converted from a length 4 sequence into a length 5 sequence by set-
ting the element h(4) = 0 , then the fi ve terms of the circular convolution are evalu-
ated as follows:
gC(0) = f(0) h(0) + f(1) h(4) + f(2) h(3) + f(3) h(2) + f(4) h(1)
gC(1) = f(0) h(1) + f(1) h(0) + f(2) h(4) + f(3) h(3) + f(4) h(2)
gC(2) = f(0) h(2) + f(1) h(1) + f(2) h(0) + f(3) h(4) + f(4) h(3)
gC(3) = f(0) h(3) + f(1) h(2) + f(2) h(1) + f(3) h(0) + f(4) h(4)
gC(4) = f(0) h(4) + f(1) h(3) + f(2) h(2) + f(3) h(1) + f(4) h(0)
R.5.117 Let us compare the elements of the linear convolution sequence gL(n) with the ele-
ments of the circular convolution gC(n). The observation yields
gL(0) ≠ gC(0)
gL(1) ≠ gC(1)
gL(2) ≠ gC(2)
gL(3) = gC(3)
gL(4) = gC(4)
R.5.118 From R.5.117, it can be stated that if h(n) is a sequence of length M and f(n) is a
sequence of length N where N > M, then the fi rst M − 1 values of the circular con-
volution do not correspond with the linear convolution, whereas the remaining N
− M + 1 elements of the circular convolution correspond to the values of the linear
convolutions.
R.5.119 For example, if h(n) is a sequence of length 4 and f(m) of length 5 , the fi rst 4 − 1
coeffi cients of the circular convolution should be discarded although coeffi cients
3 and 4 are identical to the linear convolution values.
R.5.120 Recall that DFT is often used to evaluate the linear convolutions. Effi cient algo-
rithms for the evaluation of DFT have been topics of intense research during the
1960s and 1970s. The results of this research led to a collection of effi cient compu-
tational algorithms known collectively as the ffts.
The earliest algorithm goes back to the paper published by Good in the late
1950s. These algorithms are also referred as the prime factor algorithms. The fi rst
Cooley–Tukey algorithms were published in the early 1960s and one of the main
assumptions in its implementation was that the DFT with length N is a power of
two, leading in this way into an effi cient computational implementation.
To evaluate the DFT of an N-point sequence, the number of complex multiplica-
tions is approximately of the order of N^2. Since a complex multiplication involves
four real multiplications and two additions, then the number of real multiplications
is of the order of 4N^2 and the number of real additions is approximately 4N^2 − 2N.
The effi ciency of the DFT algorithms consists of taking advantage of the nature
of the complex number (WNnk), in particular its periodicity and symmetry.
R.5.121 The fft algorithms are based in decomposing the N-point DFT computations into
smaller size DFT. For example, the DFT of an N-point sequence can be decomposed
into two (N/2) point sequences reducing the computational process from 4N^2 − 2N
to 2N + N^2 real additions.