DTFT, DFT, ZT, and FFT 499
In addition, since WN^0 = 1 and Wn(N/2)+k = −Wnk, the total number of computations
is further reduced by half.
R.5.122 The linear convolutions can be evaluated by using discrete transforms that employ
the FFT. This technique is referred to as the fast convolution. The evaluation of the
convolution in the time domain for a sequence of N samples requires 4N^2 real
multiplications.
For the case of an N-point DFT, both the time as well as frequency functions are
periodic. The points n = 1 to N/2 are symmetric with respect to the points between
(N/2) + 1 through N − 1.
If the time sequence is real, then the DFT has real and imaginary components,
which are symmetric and asymmetric, respectively.
R.5.123 The term fast refers in general to a number of techniques that use the discrete
transforms in an effi cient computational environment. For example, the convolu-
tion sum requires N^2 multiplications as compared with 4Nlog 2 (N) + 4N multipli-
cations when using the fft. If the number of discrete elements N = 1000, then the
convolution requires 1,000,000 multiplications, whereas the transform method to
evaluate the convolution requires about 44,000 multiplications.
R.5.124 For example, to sample music at a rate that is pleasant to the ear, the sampling rate
accordance to Nyquist would be about 40,000 Hz. A few seconds of music quickly
builds up into a large amount of data.
R.5.125 If a continuous time signal f(t) is band-limited, the spectra characteristics of f(n)
constitute a good approximation of f(t) if the sampling rate was performed at least
at the Nyquist rate (or higher). If f(t) is not band-limited (defi ned over −∞ < t <
+∞), then f(n) becomes an infi nite sequence over −∞ < n < +∞. Practical limits
must be imposed on the length of the sequence f(n) if a digital computer is used, by
windowing or truncating the sequence f(n) to a fi nite number of samples (N). The
DTFT of the signal f(n) is given byFe()jW n f ne()jWn and is truncated by the
use of the window w(n), over the range −N/2 ≤ n ≤ N/ 2 , yielding the following
relation:Few jW fnwnejWn
nNN
( ) () ()
22
∑R.5.126 To provide a good resolution, the DFT of length L is usually chosen to be greater
than the window length N, by adding L − N zero value samples. In addition, the
relation L = 2 k > N for the smallest integer value of k must be maintained to gain
computational effi ciency.
R.5.127 The MATLAB command k = nextpow2(N) returns the smallest integer k so that
2 k ≥ N. It is a useful command for fi nding the nearest power of 2, given an arbi-
trary sequence length, when the fft command is used.
R.5.128 There are a number of other effi cient algorithms to evaluate the DFT, especially
when a few time samples are available, such as the Goertzel algorithm. For practi-
cal reasons, only the fft command is used in this book.
R.5.129 The discrete sequence f(n) is in most cases a 1-D array, where the elements of f(n)
are the order samples of the continuous time function f(t). In general, f can be a
matrix denoted by f(n, m) with n rows and m columns. In this case, the MATLAB
function fft(f) returns the DFT of each of the m columns of f.