Page 365 - Matrix Analysis & Applied Linear Algebra

5.8 Discrete Fourier Transform 361

components—the spike in the real vector a indicates that one of the oscillatory
components is a cosine of frequency 80 Hz (or period = 1/80 ) whose amplitude
is approximately 1, and the spike in the imaginary vector ib indicates there is a
sine component with frequency 50 Hz and amplitude of about 2. In other words,
the Fourier transform indicates that the signal is
y(τ)= cos 2π(80τ)+2 sin 2π(50τ)+ Noise.
In truth, the data shown in Figure 5.8.3 was artificially generated by contami-
nating the function y(τ)= cos 2π(80τ)+2 sin 2π(50τ) with some normally dis-
tributed zero-mean noise, and therefore the plot of (2/n)F n x shown in Figure
5.8.4 does indeed accurately reflect the true nature of the signal. To understand
why F n reveals the hidden frequencies, let cos 2πft and sin 2πft denote the
discrete cosine and discrete sine vectors

 0   0 
cos 2πf · sin 2πf ·
n n
1 1
   
cos 2πf · sin 2πf ·
 n   n 
 2   2 
cos 2πft =  cos 2πf · n  and sin 2πft =  sin 2πf · n  ,
   
. .
 .   . 
 .   . 
n−1 n−1
cos 2πf · sin 2πf ·
n n
T
where t =( 0/n 1/n 2/n ··· n−1/n ) is the discrete time vector.If
the discrete exponential vectors e i2πft and e −i2πft are defined in the natural
way as e i2πft = cos 2πft +i sin 2πft and e −i2πft = cos 2πft − i sin 2πft, and
51
if 0 ≤ f< n is an integer frequency, then
 0f 
ω
 ω 1f 

 ω
e i2πft =  2f  = n F −1 = nF −1 e f ,

n
n
 .  ∗f
 . 
.
ω (n−1)f
where e f is the n × 1 unit vector witha1inthe f th component—remember
that components of vectors are indexed from 0 to n−1 throughout this section.
Similarly, the fact that
ξ kf = ω −kf =1ω −kf = ω kn ω −kf = ω k(n−f) for k =0, 1, 2,...
allows us to conclude that if 0 ≤ n − f< n, then
 0f   0(n−f) 
ξ ω
 ξ 1f   ω 1(n−f) 
 2f   2(n−f)  −1 −1
−i2πft
e =  ξ  =  ω  = n F n = nF n e n−f .
 .   .  ∗n−f
 .   . 
. .
ξ (n−1)f ω (n−1)(n−f)
51
The assumption that frequencies are integers is not overly harsh because the Fourier series for
aperiodic function requires only integer frequencies—recall Example 5.4.6.