Bài giảng Digital Signal Processing - Chapter 7: Frequency Analysis of Signals and Systems - Nguyen Thanh Tuan

Nội dung text: Bài giảng Digital Signal Processing - Chapter 7: Frequency Analysis of Signals and Systems - Nguyen Thanh Tuan

1. Chapter 7 Frequency Analysis of Signals and Systems Nguyen Thanh Tuan, ClickM.Eng. to edit Master subtitle style Department of Telecommunications (113B3) Ho Chi Minh City University of Technology Email: nttbk97@yahoo.com
2.  The frequency analysis of signals and systems have three major uses in DSP: 1) The numerical computation of frequency spectrum of a signal. 2) The efficient implementation of convolution by the fast Fourier transform (FFT) 3) The coding of waves, such as speech or pictures, for efficient transmission and storage. Digital Signal Processing 3 Frequency analysis of signals and systems
3. 1. Discrete-time Fourier transform (DTFT)  The Fourier transform of the finite-energy discrete-time signal x(n) is defined as: X()()  x n e jn n where ω=2πf/fs  The spectrum X(w) is in general a complex-valued function of frequency: X( ) | X ( ) | e j() where (  ) arg(X (  )) with -  (  )  | X (  ) | : is the magnitude spectrum   () : is the phase spectrum Digital Signal Processing 5 Frequency analysis of signals and systems
4. Inverse discrete-time Fourier transform (IDTFT)  Given the frequency spectrum X ()  , we can find the x(n) in time- domain as 1 x()() n X ejn d 2 which is known as inverse-discrete-time Fourier transform (IDTFT) Example: Consider the ideal lowpass filter with cutoff frequency wc. Find the impulse response h(n) of the filter. Digital Signal Processing 7 Frequency analysis of signals and systems
5. Properties of DTFT  The relationship of DTFT and z-transform: if X(z) converges for |z|=1, then jn X( z ) | x ( n ) e X ( ) ze j  n F  Linearity: if x11()() n X  F x22()() n X  F then a1 x 1()()()() n a 2 x 2 n  a 1 X 1 a 2 X 2  Time-shifting: if x()() n F X  then x()() n k  F e jk X  Digital Signal Processing 9 Frequency analysis of signals and systems
6. Frequency resolution and windowing  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. Digital Signal Processing 11 Frequency analysis of signals and systems
7. Impact of rectangular window  Consider a single analog complex sinusoid of frequency f1 and its sample version:  With assumption , we have Digital Signal Processing 13 Frequency analysis of signals and systems
8. Hamming window Digital Signal Processing 15 Frequency analysis of signals and systems
9. Example  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.  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. Digital Signal Processing 17 Frequency analysis of signals and systems
10. Example Digital Signal Processing 19 Frequency analysis of signals and systems
11. 2. Discrete Fourier transform (DFT)  With the assumption x(n)=0 for n ≥ L, we can write N 1 X () k  x () n e j 2/ kn N , k 0,1,, N 1. (DFT) n 0  The sequence x(n) can recover form the frequency samples by inverse DFT (IDFT) 1 N 1 x () n  X () k e j 2/ kn N , n 0,1,, N 1. (IDFT) N n 0 Example: Calculate 4-DFT and plot the spectrum of x(n)=[1 1, 2, 1] Digital Signal Processing 21 Frequency analysis of signals and systems
12. Matrix form of DFT 1 1 1 1 1 WWW21N NNN 2 4 2(N 1) WNNNN 1 WWW NNNN 1 2( 1) ( 1)( 1) 1 WWWNNN  Let us define: x(0) X (0) x(1) X (1) xN X N xN( 1) XN( 1) The N-point DFT can be expressed in matrix form as: XNNN W x Digital Signal Processing 23 Frequency analysis of signals and systems
13. Properties of DFT Properties Time domain Frequency domain  Notation xn() Xk()  Periodicity x()() n N x n X()() k X k N  Linearity a1 x 1()() n a 2 x 2 n a1 X 1()() k a 2 X 2 k j2/ kl N  Circular time-shift x(( n l ))N e X() k  Circular convolution  Multiplication of two sequences NN1 1  22 Parveval’s theorem Ex | x ( n ) | | X ( k ) | nk 00N Digital Signal Processing 25 Frequency analysis of signals and systems
14. Circular convolution  The circular convolution of two sequences of length N is defined as  Example: Perform the circular convolution of the following two sequence: xn1( ) [2,1,2,1] xn2 ( ) [1,2,3,4] It can been shown from the below Fig, Digital Signal Processing 27 Frequency analysis of signals and systems
15. Circular convolution Digital Signal Processing 29 Frequency analysis of signals and systems
16. 4. Fast Fourier transform (FFT)  N-point DFT of the sequence of data x(n) of length N is given by following formula: N 1 k X( k )  x n WN , k 0,1,2, , N 1 n 0 jN2/ where WeN  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. k N/2 k - Symmetry: WWNN k N k - Periodicity: WWNN Digital Signal Processing 31 Frequency analysis of signals and systems
17. Fast Fourier transform (FFT)  Using the property that: N k 2 k WWNN  The entire DFT can be computed with only k=0, 1, ,N/2-1. NN/2 1 /2 1 -kn -k -kn X k  x2 n WNNN W x 2 n 1 W nn 0022 NN/2 1 /2 1 N -kn -k -kn X k  x2 n WNNN W x 2 n 1 W 2 nn 0022 Digital Signal Processing 33 Frequency analysis of signals and systems
18. Recursion  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). 3rd stage 2nd stage 1st stage x(0) X(0) 0 W8 x(4) - X(1) 0 W8 x(2) - X(2) 0 2 W8 W x(6) - 8 - X(3) W 0 x(1) 8 - X(4) 0 0 1 W =1 W8 W8 8 x(5) - - X(5) 0 2 W8 W8 x(3) - - X(6) 0 2 3 W8 W8 W8 x(7) - - - X(7) Digital Signal Processing 35 Frequency analysis of signals and systems
19. Number of operations r  If N=2 , 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 37 Frequency analysis of signals and systems
20. Homework 2 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}. Digital Signal Processing 39 Frequency analysis of signals and systems
21. Homework 4 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. Digital Signal Processing 41 Frequency analysis of signals and systems