Bài giảng Xử lý tín hiệu số - Fourier Transform

pdf 72 trang phuongnguyen 7460
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Xử lý tín hiệu số - Fourier Transform", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_xu_ly_tin_hieu_so_fourier_transform.pdf

Nội dung text: Bài giảng Xử lý tín hiệu số - Fourier Transform

  1. Xử lý tín hiệu số Fourier Transform Ngô Quốc Cường ngoquoccuong175@gmail.com sites.google.com/a/hcmute.edu.vn/Ngô Quốc Cường ngoquoccuong
  2. CONTENTS • Frequency analysis of discrete time signal • Properties of Fourier transform • Frequency domain characteristics of LTI systems • Discrete Fourier Transform • Fast Fourier Transform 2
  3. 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals – Given a periodic signal x(n) with period N. (DTFS) 3
  4. 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals • The spectrum of a signal x(n) which is periodic with period N, is a periodic sequence with period N. 4
  5. 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals • Example 1: Determine the spectra of the signal 5
  6. 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals • Solution of example 1: 6
  7. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • The Fourier transform of a finite energy signal x(n) is defined as • X(w) is periodic with period 2 : 8
  8. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • In summary, the Fourier transform pair of a discrete time is as follows • Uniform convergence is guaranteed if x(n) is absolutely summable 9
  9. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • The spectrum X(w) is, in general, a complex valued function of frequency • The energy density spectrum of x(n) is 10
  10. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Example 2: 11
  11. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Solution of example 2: 12
  12. 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Solution of example 2 (cont’d): 13
  13. 2. Properties of Fourier transform • Symmetry • Linearity • Time shifting • Time reversal • Convolution theorem • Correlation theorem • Frequency shifting • Modulation theorem • Windowing theorem • Differentiation in frequency domain 14
  14. 2. Properties of Fourier transform 15
  15. 2. Properties of Fourier transform 16
  16. 2. Properties of Fourier transform • Example 3: 17
  17. 2. Properties of Fourier transform • Solution of Example 3: 18
  18. 2. Properties of Fourier transform • Solution of Example 3: 19
  19. 2. Properties of Fourier transform • Solution of Example 3 (cont’d): a=0.8 20
  20. 2. Properties of Fourier transform • Example 4: 21
  21. 2. Properties of Fourier transform • Solution of Example 4: 22
  22. 3. Frequency domain characteristics of LTI systems • The response of any relaxed-system to arbitrary input signal is: • Excite the system with the complex exponential • Obtain the response 23
  23. 3. Frequency domain characteristics of LTI systems • The Fourier transform of the unit sample response h(k) of the system • The function H(휔) exists if the system is BIBO stable • The response of the system to the complex exponential is 24
  24. 3. Frequency domain characteristics of LTI systems • Example 25
  25. 3. Frequency domain characteristics of LTI systems • Solution • First, • At 휔 = /2 yields • The output is 26
  26. 3. Frequency domain characteristics of LTI systems • In general, H(휔) is a complex function of 휔, hence • Expressed in terms of real and image components 27
  27. 3. Frequency domain characteristics of LTI systems • Example 28
  28. 3. Frequency domain characteristics of LTI systems • The impulse response • It follows that • Hence 29
  29. 3. Frequency domain characteristics of LTI systems 30
  30. 3. Frequency domain characteristics of LTI systems • Example • Determine the response of the system (with given impulse response h(n)) to the input signal x(n) 31
  31. 3. Frequency domain characteristics of LTI systems • Solution • The frequency response • With each term in the input signal • The response to the input signal 32
  32. 4. Discrete Fourier Transform 4.1. Frequency domain sampling • Aperiodic finite- energy signals have continuous spectra • Sample X(휔) periodically at a spacing of 훿휔 radians, take N equidistant samples in the interval 0 ≤ 휔 ≤ 2 with spacing 휔 = 2 / 33
  33. 4. Discrete Fourier Transform 4.1. Frequency domain sampling 34
  34. 4. Discrete Fourier Transform 4.2. Discrete Fourier Transform • A finite-duration sequence x(n) of length L has the DFT where N ≥ L • Recover x(n) from its DFT (inverse DFT) 35
  35. 4. Discrete Fourier Transform • 4.2. Discrete Fourier Transform • Exercise – Compute the 8-point DFT of 36
  36. 4. Discrete Fourier Transform • 4.2. Discrete Fourier Transform • Exercise – Compute the 6-point DFT of 37
  37. 4. Discrete Fourier Transform 4.2. Properties of the DFT Denote • Periodicity, Linearity, Circular symmetries • Time reversal • Circular time shift • Circular frequency shift • Complex conjugate properties • Circular correlation • Parseval ’s theorem 38
  38. 4. Discrete Fourier Transform 39
  39. 4. Discrete Fourier Transform 4.2. Properties of the DFT • Circular symmetries – The N-point DFT of x(n) is equivalent to the N-point DFT of xp(n), in which – Shift the periodic sequence xp(n) by k unit to the right, we obtain another periodic sequence 40
  40. 4. Discrete Fourier Transform 4.2. Properties of the DFT • Circular symmetries – x’(n) is related to x(n) by a circular shift. 41
  41. 4. Discrete Fourier Transform 4.2. Properties of the DFT • Circular symmetries – The circular shift can be represented as the index modulo N. – Example 45
  42. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution – Suppose we have two finite-duration sequences of length N, x1(n) and x2(n). Their respective N-point DFTS are: – Multiply two sequences, the result is a DFT, say X3(k), of a sequence x3(n) 46
  43. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution – The inverse of X3(k) is – Circular convolution 47
  44. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Example 48
  45. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution 49
  46. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 50
  47. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 51
  48. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 52
  49. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 53
  50. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • The circular of the two sequences yields the sequence 54
  51. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Example • By means of DFT and IDFT, determine the sequence x3(n) corresponding to the circular convolution of x1(n) and x2(n) 55
  52. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution • Compute the DFTs 56
  53. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution • Thus, • Multiply the two DFTs • The IDFT of X3(k) 57
  54. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution • Thus, 58
  55. 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 59
  56. 4. Discrete Fourier Transform • Exercise 60
  57. 5. Fast Fourier Transform • The DFT can be written in the formula where • For each value of k, direct computation of X(k) involves – N complex multiplications – N-1 complex additions • For all N values, the DFT requires – N2 complex multiplications – N2-N complex additions 61
  58. 5. Fast Fourier Transform • Direct computation of DFT does not exploit the symmetry and periodicity properties 62
  59. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Split N-point data sequence x(n) into two N/2-point sequence • The N-point DFT of x(n) can be expressed as 63
  60. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Because , • We also have • Result in a reduction of the number of multiplication 64
  61. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • We can repeat the process for each of the sequences f1(n) and f2(n) 65
  62. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Thus • The total number of multiplication is reduced again 66
  63. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Comparison of computational complexity 67
  64. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Perform 8-point DFT in 3 stages 68
  65. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Basic butterfly computation 70
  66. 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Compute 8-point DFT (using FFT algorithm) of x(n)={1, 2, 3, 0, 0, 0, 0, 0} 71
  67. 5. Fast Fourier Transform 5.2. Radix-4 FFT algorithms 72