Page 720 - The Mechatronics Handbook

0066_Frame_C23 Page 28 Wednesday, January 9, 2002 1:53 PM

where x[(n − m)mod N] is the reflected and circularly translated version of x(n). However, by appropriate
selecting the value of N, both the circular and linear convolution can be the same. Thus, if signals x(n)
and y(n) are of length N 1 and N 2 , respectively, then circular and linear convolution are the same provided
N ≥ N 1 + N 2 − 1.
Circular correlation can be implemented by circular convolution since the cross correlation of the two
sequences x(n) and y(n) can be expressed as

R xy n() = xn()⊗ N yn() = xn()⊗ N y ( – n)mod N]
[
∗
From Eqs. (23.46) and (23.47), it is noted that to compute the DFT coefficients would require N 2
complex multiplications and N(N − 1) complex additions. This can be a computational load if N is very
large. Fast Fourier transforms (FFTs) are different types of algorithms that have been developed to speed
up the computation of the DFT coefficients. Readers can refer to many textbooks where the development
7,8
of the various forms of the FFT algorithms has been discussed. It can be shown that the number of
computations required for the FFT algorithms can be expressed as a constant times N ∗ log 2 N. Conse-
quently, there is a reduction in computation when an FFT algorithm is used for the DFT computation.

Remarks on the DFT Processing of Signals
Zero Padding 6,8
The use of FFT for DFT coefficients computation imposes some constraints on the value of N, for example
N has to be a power of 2 for radix-2 FFT algorithm. Also, circular convolution is an undesirable solution
as it manifests from the IDFT of the product of the transform of two sequences. Zero-padding is a technique
for remedying the above situations, that is, the zero-padding is used either to augment the sequence
length so that either a radix-2 FFT algorithm can be used or to ensure that both the linear and circular
convolution are the same. In addition, this procedure is also used to provide a better-looking display of
the signal spectrum since the frequency spacing of the FFT samples decreases as N increases.
Error Sources 8,10
The resultant spectrum of a sampled signal comprises the analog spectrum repeated at the integer multiples
of the sampling frequency. The overlapping of the analog signal spectrum with its shifted versions causes
aliasing. In practice, excessive errors due to aliasing are minimized by either increasing the sampling rate
or prefiltering the signal to remove the high-frequency spectral components. Another source of error in the
DFT processing of signals is the spectral leakage. This is caused by using a window to truncate an infinitely
long signal to obtain a finite-length data for DFT processing. It is known that windowing the samples of a
signal in the time domain transforms to convolution of sampled signal spectrum and the window spectrum
in the frequency domain. Suppose the window width does not correspond to an integer multiple of periods
of all the frequency components of a discrete-time signal, then a single frequency component will spread
(leak) into other frequency locations in the DFT of the truncated data. This phenomenon causes spectral
distortion and makes it difficult to determine whether or not two closely adjacent frequencies are present
in a signal. Spectral resolution becomes better if the window width is increased, or by choosing a window
function with low sidelobes. The picket-fence effect arises because only a finite number of frequency points
of a continuous-frequency spectrum are produced by the DFT. It is therefore possible to miss the peak of
a particular frequency component in a signal because it is located between two adjacent frequency points
in the spectrum. Since the frequency spacing ∆f = F s /N, this problem can be alleviated by increasing N the
number of DFT points while maintaining the same sampling rate, implying having more samples in the
DFT or a employing zero-padding technique.
DFT Parameter Selection 6
The sampling period, T s , frequency resolution (spacing), ∆f, and the DFT length, N, are the three parameters
that must be specified in performing DFT signal processing. Since F s = N∆f = 1/T s , these parameters are
related according to ∆f = 1/NT s . If T x denotes the length of the sampled data, then T x = MT s . Thus, there is

©2002 CRC Press LLC