Bài giảng Digital Signal Processing - Chương 7: Frequency Analysis of Signals and Systems - Nguyễn Thanh Tuấn

Click to edit Master subtitle style Nguyen Thanh Tuan, M.Eng. 
Department of Telecommunications (113B3) 
Ho Chi Minh City University of Technology 
Email: nttbk97@yahoo.com 
 Frequency Analysis of Signals and Systems 
 Chapter 7 
Digital Signal Processing 2 
 Frequency analysis of signal involves the resolution of the signal into 
its frequency (sinusoidal) components. The process of obtaining the 
spectrum of a given signal using the basic mathematical tools is 
known as frequency or spectral analysis. 
Frequency analysis of signals and systems 
 The term spectrum is used when referring the frequency content of a 
signal. 
 The process of determining the spectrum of a signal in practice base 
on actual measurements of signal is called spectrum estimation. 
 The instruments of software programs 
used to obtain spectral estimate of such 
signals are kwon as spectrum analyzers. 
Digital Signal Processing 3 
 The frequency analysis of signals and systems have three major uses 
in DSP: 
Frequency analysis of signals and systems 
 1) The numerical computation of frequency spectrum of a signal. 
 3) The coding of waves, such as speech or pictures, for efficient 
transmission and storage. 
 2) The efficient implementation of convolution by the fast Fourier 
transform (FFT) 
Digital Signal Processing 
Content 
4 
1. Discrete time Fourier transform DTFT 
2. Discrete Fourier transform DFT 
Transfer functions 
and Digital Filter Realizations 
3. Fast Fourier transform FFT 
1. Discrete-time Fourier transform (DTFT) 
 The Fourier transform of the finite-energy discrete-time signal x(n) is 
defined as: 
( ) ( ) j n
n
X x n e 
 
 The spectrum X(w) is in general a complex-valued function of 
frequency: 
( )( ) | ( ) | jX X e    
 where ( ) arg( ( )) with - ( )X     
 : is the magnitude spectrum 
 : is the phase spectrum 
| ( ) |X 
( ) 
Digital Signal Processing 5 Frequency analysis of signals and systems 
 where ω=2πf/fs 
 Determine and sketch the spectra of the following signal: 
 a) ( ) ( )x n n 
Digital Signal Processing 6 Frequency analysis of signals and systems 
 b) ( ) ( ) with |a|<1nx n a u n 
 is periodic with period 2π. ( )X 
 The frequency range for discrete-time signal is unique over the 
frequency interval (-π, π), or equivalently, (0, 2π). 
( 2 )( 2 ) ( ) ( ) ( )j k n j n
n n
X k x n e x n e X  
  
 Remarks: Spectrum of discrete-time signals is continuous and 
periodic. 
Inverse discrete-time Fourier transform (IDTFT) 
 Given the frequency spectrum , we can find the x(n) in time-
domain as 
Digital Signal Processing 7 Frequency analysis of signals and systems 
 which is known as inverse-discrete-time Fourier transform (IDTFT) 
1
( ) ( )
2
j nx n X e d

 
( )X 
 Example: Consider the ideal lowpass filter with cutoff frequency wc. 
Find the impulse response h(n) of the filter. 
 Properties of DTFT 
 Symmetry: if the signal x(n) is real, it easily follows that 
Digital Signal Processing 8 Frequency analysis of signals and systems 
or equivalently, (even symmetry) 
( ) ( )X X  
| ( ) | | ( ) |X X  
 (odd symmetry) arg( ( )) arg( ( ))X X  
We conclude that the frequency range of real discrete-time signals can 
be limited further to the range 0 ≤ ω≤π, or 0 ≤ f≤fs/2. 
 Energy density of spectrum: the energy relation between x(n) and 
X(ω) is given by Parseval’s relation: 
22 1| ( ) | ( )
2
x
n
E x n X d
 
  
2( ) | ( ) |xxS X  is called the energy density spectrum of x(n) 
 Properties of DTFT 
 The relationship of DTFT and z-transform: if X(z) converges for 
|z|=1, then 
Digital Signal Processing 9 Frequency analysis of signals and systems 
( ) | ( ) ( )j
j n
z e
n
X z x n e X
 
 
 Linearity: if 1 1( ) ( )
Fx n X  
2 2( ) ( )
Fx n X  
then 1 1 2 2 1 1 2 2( ) ( ) ( ) ( )
Fa x n a x n a X a X   
 Time-shifting: if ( ) ( )Fx n X  
then ( ) ( )
F j kx n k e X   
 Properties of DTFT 
 Time reversal: if 
Digital Signal Processing 10 Frequency analysis of signals and systems 
1 1( ) ( )
Fx n X  
2 2( ) ( )
Fx n X  
then 1 2 1 2( ) ( ) ( ) ( ) ( ) ( )
Fx n x n x n X X X    
( ) ( )Fx n X  
then ( ) ( )
Fx n X   
 Convolution theory: if 
Example: Using DTFT to calculate the convolution of the sequences 
x(n)=[1 2 3] and h(n)=[1 0 1]. 
Frequency resolution and windowing 
Digital Signal Processing 11 Frequency analysis of signals and systems 
 The duration of the data record is: 
 The rectangular window of length 
L is defined as: 
 The windowing processing has two major effects: reduction in the 
frequency resolution and frequency leakage. 
 Rectangular window 
Digital Signal Processing 12 Frequency analysis of signals and systems 
Impact of rectangular window 
Digital Signal Processing 13 Frequency analysis of signals and systems 
 Consider a single analog complex sinusoid of frequency f1 and its 
sample version: 
With assumption , we have 
 Double sinusoids 
Digital Signal Processing 14 Frequency analysis of signals and systems 
 Frequency resolution: 
Digital Signal Processing 15 Frequency analysis of signals and systems 
Hamming window 
Non-rectangular window 
Digital Signal Processing 16 Frequency analysis of signals and systems 
 The standard technique for suppressing the sidelobes is to use a non-
rectangular window, for example Hamming window. 
 The main tradeoff for using non-rectangular window is that its 
mainlobe becomes wider and shorter, thus, reducing the frequency 
resolution of the windowed spectrum. 
 The minimum resolvable frequency difference will be 
where : c=1 for rectangular window and c=2 for Hamming 
window. 
 The minimum frequency separation is Applying 
the formulation , the minimum length L to 
resolve all three sinusoids show be 20 
samples for the rectangular window, and L =40 samples for the 
Hamming case. 
Example 
Digital Signal Processing 17 Frequency analysis of signals and systems 
 The following analog signal consisting of three equal-strength 
sinusoids at frequencies 
 where t (ms), is sampled at a rate of 10 kHz. We consider four data 
records of L=10, 20, 40, and 100 samples. They corresponding of the 
time duarations of 1, 2, 4, and 10 msec. 
Example 
Digital Signal Processing 18 Frequency analysis of signals and systems 
Example 
Digital Signal Processing 19 Frequency analysis of signals and systems 
2. Discrete Fourier transform (DFT) 
 is a continuous function of frequency and therefore, it is not a 
computationally convenient representation of the sequence x(n). 
( )X 
Digital Signal Processing 20 Frequency analysis of signals and systems 
 DFT will present x(n) in a frequency-domain by samples of its 
spectrum . ( )X 
 A finite-duration sequence x(n) of length L has a Fourier transform: 
1
0
( ) ( ) 0 2
L
j n
n
X x n e   
 
 Sampling X(ω) at equally spaced frequency , k=0, 1,,N-1 
where N ≥ L, we obtain N-point DFT of length L-signal: 
2
k
k
N
 
1
2 /
0
2
( ) ( ) ( )
L
j kn N
n
k
X k X x n e
N
  (N-point DFT) 
 DFT presents the discrete-frequency samples of spectra of discrete-
time signals. 
2. Discrete Fourier transform (DFT) 
With the assumption x(n)=0 for n ≥ L, we can write 
Digital Signal Processing 21 Frequency analysis of signals and systems 
 The sequence x(n) can recover form the frequency samples by inverse 
DFT (IDFT) 
1
2 /
0
( ) ( ) , 0,1, , 1.
N
j kn N
n
X k x n e k N 
  (DFT) 
1
2 /
0
1
( ) ( ) , 0,1, , 1.
N
j kn N
n
x n X k e n N
N
  (IDFT) 
Example: Calculate 4-DFT and plot the spectrum of x(n)=[1 1, 2, 1] 
Matrix form of DFT 
 By defining an Nth root of unity , we can rewritte DFT 
and IDFT as follows 
Digital Signal Processing 22 Frequency analysis of signals and systems 
 Let us define: 
1
0
( ) ( ) , 0,1, , 1.
N
kn
N
n
X k x n W k N
 
1
0
1
( ) ( ) , 0,1, , 1.
N
kn
N
n
x n X k W n N
N
  (IDFT) 
2 /j N
NW e
 (DFT) 
(0)
(1)
( 1)
N
x
x
x N
x
(0)
(1)
( 1)
N
X
X
X N
X
The N-point DFT can be expressed in matrix form as: N N N X W x
Matrix form of DFT 
Digital Signal Processing 23 Frequency analysis of signals and systems 
 Let us define: (0)
(1)
( 1)
N
x
x
x N
x
(0)
(1)
( 1)
N
X
X
X N
X
The N-point DFT can be expressed in matrix form as: N N N X W x
2 1
2 4 2( 1)
1 2( 1) ( 1)( 1)
1 1 1 1
1
1
1
N
N N N
N
N N N N
N N N N
N N N
W W W
W W W
W W W
W
Digital Signal Processing 24 Frequency analysis of signals and systems 
 Example: Determine the DFT of the four-point sequence x(n)=[1 1, 
2 1] by using matrix form. 
Properties of DFT 
Digital Signal Processing 25 Frequency analysis of signals and systems 
 Properties Time domain Frequency domain 
 Periodicity 
 Linearity 
 Circular time-shift 
 Circular convolution 
Multiplication 
 of two sequences 
 Parveval’s theorem 
( )x n Notation ( )X k
( ) ( )x n N x n ( ) ( )X k X k N 
1 1 2 2( ) ( )a x n a x n 1 1 2 2( ) ( )a X k a X k 
(( ))Nx n l 
2 / ( )j kl Ne X k 
1
2 2
0 0
1
| ( ) | | ( ) |
N N
x
n k
E x n X k
N
  
Circular shift 
Digital Signal Processing 26 Frequency analysis of signals and systems 
'( ) ( , modulo ) (( ))Nx n x n k N x n k  
 The circular shift of the sequence can be represented as the index 
modulo N: 
Circular convolution 
Digital Signal Processing 27 Frequency analysis of signals and systems 
 The circular convolution of two sequences of length N is defined as 
 Example: Perform the circular convolution of the following two 
sequence: 
1( ) [2,1,2,1]x n 2( ) [1,2,3,4]x n 
It can been shown from the below Fig, 
Circular convolution 
Digital Signal Processing 28 Frequency analysis of signals and systems 
Circular convolution 
Digital Signal Processing 29 Frequency analysis of signals and systems 
Digital Signal Processing 30 Frequency analysis of signals and systems 
Use of the DFT in Linear Filtering 
 Suppose that we have a finite duration sequence x=[x0, x1,, xL-1 ] 
which excites the FIR filter of order M. 
 The sequence output is of length Ly=L+M samples. 
 If N ≥ L+M, N-point DFT is sufficient to present y(n) in the 
frequency domain, i.e., 
 Computation of the N-point IDFT must yield y(n). 
 Thus, with zero padding, the DFT can be used to perform linear 
filtering. 
1
0
( ) , 0,1,2,..., 1
N
k
N
n
X k x n W k N
 
Digital Signal Processing 31 Frequency analysis of signals and systems 
4. Fast Fourier transform (FFT) 
 N-point DFT of the sequence of data x(n) of length N is given by 
following formula: 
 where 
2 /j N
NW e
 In general, the data sequence x(n) is also assumed to be complex 
valued. To calculate all N values of DFT require N2 complex 
multiplications and N(N-1) complex additions. 
 FFT exploits the symmetry and periodicity properties of the phase 
factor WN to reduce the computational complexity. 
/2k N k
N NW W
 - Symmetry: 
 - Periodicity: k N k
N NW W
      
/2 1 /2 1
-k 2n 1-k2n
N N
0 0
2 W 2 1 W
N N
n n
X k x n x n
  
Digital Signal Processing 32 Frequency analysis of signals and systems 
3. Fast Fourier transform (FFT) 
 Based on decimation, leads to a factorization of computations. 
 Let us first look at the classical radix 2 decimation in time. 
 First we split the computation between odd and even samples: 
 Using the following property: 
2
N N
2
W W 
     
/2 1 /2 1
-kn -k -kn
N N N
0 02 2
2 W W 2 1 W
N N
n n
X k x n x n
  
 The N-point DFT can be rewritten: 
 for k=0, 1, , N-1 
N
k
k2
N NW W
   
/2 1 /2 1
-kn -k -kn
N N N
0 02 2
2 W W 2 1 W
2
N N
n n
N
X k x n x n
 
     
/2 1 /2 1
-kn -k -kn
N N N
0 02 2
2 W W 2 1 W
N N
n n
X k x n x n
  
Digital Signal Processing 33 Frequency analysis of signals and systems 
Fast Fourier transform (FFT) 
 Using the property that: 
 The entire DFT can be computed with only k=0, 1, ,N/2-1. 
DFT N/2 
DFT N/2 
x(0) 
x(2) 
x(N-2) 
x(1) 
x(3) 
x(N-1) 
X(0) 
X(1) 
X(N/2-1) 
X(N/2) 
X(N/2+1) 
X(N-1) 
WN
0 
WN
1 
WN
N/2-1 
- 
- 
- 
We need: 
•N/2(N/2-1) complex ‘+’ for 
each N/2 DFT. 
•(N/2)2 complex ‘×’ for each 
DFT. 
•N/2 complex ‘×’ at the input 
of the butterflies. 
•N complex ‘+’ for the butter-
flies. 
•Grand total: 
N2/2 complex ‘+’ 
N/2(N/2+1) complex ‘×’ 
Digital Signal Processing 34 Frequency analysis of signals and systems 
Butterfly 
 This leads to basic building block of the FFT, the butterfly. 
x(0) 
x(4) 
x(2) 
x(6) 
x(1) 
x(5) 
x(3) 
x(7) 
X(0) 
X(1) 
X(2) 
X(3) 
X(4) 
X(5) 
X(6) 
X(7) 
W8
0 
W8
1 
W8
2 
W8
3 
- 
- 
- 
- - 
- 
- 
- 
- 
- 
- 
- 
W8
0 
W8
0 
W8
2 
W8
2 
W8
0 
W8
0 
W8
0 
W8
0 
W8
0=1 
1st stage 2nd stage 3rd stage 
 If N/2 is even, we can further split the computation of each DFT of 
size N/2 into two computations of half size DFT. When N=2r this 
can be done until DFT of size 2 (i.e. butterfly with two elements). 
Recursion 
Digital Signal Processing 35 Frequency analysis of signals and systems 
Shuffling the data, bit reverse ordering 
Digital Signal Processing 36 Frequency analysis of signals and systems 
 At each step of the algorithm, data are split between even and odd 
values. This results in scrambling the order. 
Number of operations 
Digital Signal Processing 37 Frequency analysis of signals and systems 
 If N=2r, we have r=log2(N) stages. For each one we have: 
• N/2 complex ‘×’ (some of them are by ‘1’). 
• N complex ‘+’. 
 Thus the grand total of operations is: 
• N/2 log2(N) complex ‘×’. 
• N log2(N) complex ‘+’ 
 Example: Calculate 4-point DFT of x=[1, 3, 2, 3] ? 
Digital Signal Processing 
Homework 1 
38 
a) Tính DFT-4 điểm của tín hiệu x(n) = {@, 1, 1, 2, 19, 11, 19, 11}. 
b) Tính IDFT-4 điểm của tín hiệu X(k) = {@, 1 + j, 16, 1 – j}. 
c) Vẽ sơ đồ thực hiện và tính FFT-4 điểm của tín hiệu x(n) = {@, 1 
– j, 16, 1 + j}. 
d) Vẽ 1 sơ đồ tổng quát thực hiện FFT-8 điểm. 
Frequency analysis of signals and systems 
Digital Signal Processing 
Homework 2 
39 
a) Tính DFT-4 điểm của tín hiệu x(n) = {@, 2, 8}. 
b) Vẽ sơ đồ thực hiện và tính FFT-4 điểm của tín hiệu x(n) = {@, 
0, 1, 2}. 
c) Xác định giá trị của A và B trong tín hiệu x(n) = {–20, –8, 1, 2, 
A, B} để DFT-4 điểm của tín hiệu trên có dạng X(k) = {5, 1 + 
j2, 1, 1 – j2}. 
Frequency analysis of signals and systems 
Digital Signal Processing 
Homework 3 
40 
a) Tính DFT-4 điểm của tín hiệu x(n) = {@, 8, 0, 5, 4, 0, 4, 1}. 
b) Xác định giá trị của A và B trong tín hiệu x(n) = {1, 2, 3, 4, 5, 6, 
A, B} để DFT-4 điểm của tín hiệu trên có dạng X(k) = {12, 1 – j, 
–2, 1 + j}. 
c) Vẽ sơ đồ thực hiện và tính FFT-4 điểm của tín hiệu x(n) = {@, 8, 
4, 6}. 
d) Vẽ sơ đồ thực hiện tính IFFT-4 điểm của tín hiệu X(k) = {@, 8, 0, 
5}. 
Frequency analysis of signals and systems 
Digital Signal Processing 
Homework 4 
41 
a) Tính DFT-4 điểm của tín hiệu x(n) = {@, 2, 1, 0, 1, 1, 1}. 
b) Xác định giá trị của A và B trong tín hiệu x(n) = {3, 1, 2, 0, A, B} 
để DFT-4 điểm của tín hiệu trên có dạng X(k) = {9, 2 – j3, 3, 2 + 
j3}. 
c) Chứng minh và vẽ sơ đồ thực hiện tính DFT-4 điểm dựa trên các 
DFT-2 điểm. 
d) Chứng minh và vẽ sơ đồ thực hiện tính IDFT-4 điểm dựa trên 
DFT-4 điểm. 
Frequency analysis of signals and systems