Page 162 - Applied Numerical Methods Using MATLAB

FOURIER TRANSFORM 151
Suppose a sequence of data {x[n] = x(nT ), n = 0: M − 1}(T : the sampling
period) is obtained by sampling a continuous-time/space signal once every T
seconds. The N(≥ M)-point DFT/IDFT (inverse DFT) pair is defined as

N−1
−j2πnk/N
DFT: X(k) = x[n]e , k = 0: N − 1 (3.9.1a)
n=0
N−1
1 j2πnk/N
IDFT: x[n] = X(k)e , n = 0: N − 1 (3.9.1b)
N
k=0
Remark 3.3. DFS/DFT (Discrete Fourier Series/Transform)
0. Note that the indices of the DFT/IDFT sequences appearing in MATLAB
range from 1 to N.
1. Generally, the DFT coefficient X(k) is complex-valued and denotes the
magnitude and phase of the signal component having the digital frequency
k = k 0 = 2πk/N[rad], which corresponds to the analog frequency ω k =
kω 0 = k 0 /T = 2πk/NT [rad/s]. We call 0 = 2π/N and ω 0 = 2π/NT
(N represents the size of DFT) the digital/analog fundamental or resolution
frequency, since it is the minimum digital/analog frequency difference that
can be distinguished by the N-point DFT.
2. The DFS and the DFT are essentially the same, but different in the range
of time/frequency interval. More specifically, a signal x[n] and its DFT
X(k) are of finite duration over the time/frequency range {0 ≤ n ≤ N − 1}
and {0 ≤ k ≤ N − 1}, respectively, while a signal ˜x[n] (to be analyzed by
˜
DFS) and its DFS X(k) are periodic with the period N over the whole set
of integers.
3. FFT (fast Fourier transform) means the computationally efficient algorithm
developed by exploiting the periodicity and symmetry in the multiplying
factor e i2πnk/N to reduce the number of complex number multiplications
2
from N to (N/2) log N (N represents the size of DFT). The MATLAB
2
built-in functions “fft()”/“ifft()” implement the FFT/IFFT algorithm for
l
the data of length N = 2 (l represents a nonnegative integer). If the length
Mof the original data sequence is not a power of 2, it can be extended by
padding the tail part of the sequence with zeros, which is called zero-padding.
3.9.1 FFT Versus DFT

As mentioned in item 3 of Remark 3.3, FFT/IFFT (inverse FFT) is the compu-
tationally efficient algorithm for computing the DFT/IDFT and is fabricated into
the MATLAB functions “fft()”/“ifft()”. In order to practice the use of the
MATLAB functions and realize the computational advantage of FFT/IFFT over
DFT/IDFT, we make the MATLAB program “compare_dft_fft.m”. Readers are
recommended to run this program and compare the execution times consumed by
the 1024-point DFT/IDFT computation and its FFT/IFFT scheme, seeing that the