Bài giảng Xử lý tín hiệu số - Lecture 5: Fourier Transform - Ngô Quốc Cường

Xử lý tín hiệu số Fourier Transform Ngô Quốc Cường Ngô Quốc Cường ngoquoccuong175@gmail.com sites.google.com/a/hcmute.edu.vn/ngoquoccuong CONTENTS • Frequency analysis of discrete time signal • Properties of Fourier transform • Frequency domain characteristics of LTI systems • Discrete Fourier Transform • Fast Fourier Transform 2 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals – Given a periodic signal x(n) with period N. 3 (DTFS) 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 1.Frequency analysis of discrete time signal 1.1. Fourier series for periodic signals • Example 1: Determine the spectra of the signal 5 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 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 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 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Example 2: 11 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Solution of example 2: 12 1.Frequency analysis of discrete time signal 1.2. Fourier transform of aperiodic signals • Solution of example 2 (cont’d): 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 2. Properties of Fourier transform 15 2. Properties of Fourier transform 16 2. Properties of Fourier transform • Example 3: 17 2. Properties of Fourier transform • Solution of Example 3: 18 2. Properties of Fourier transform • Solution of Example 3: 19 2. Properties of Fourier transform • Solution of Example 3 (cont’d): 20 a=0.8 2. Properties of Fourier transform • Example 4: 21 2. Properties of Fourier transform • Solution of Example 4: 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 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 3. Frequency domain characteristics of LTI systems • Example 25 3. Frequency domain characteristics of LTI systems • Solution • First, • At 𝜔 = 𝜋/2 yields • The output is 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 3. Frequency domain characteristics of LTI systems • Example 28 3. Frequency domain characteristics of LTI systems • The impulse response • It follows that • Hence 29 3. Frequency domain characteristics of LTI systems 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 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 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 4. Discrete Fourier Transform 4.1. Frequency domain sampling 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 4. Discrete Fourier Transform • 4.2. Discrete Fourier Transform • Exercise – Compute the 8-point DFT of 36 4. Discrete Fourier Transform • 4.2. Discrete Fourier Transform • Exercise – Compute the 6-point DFT of 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 4. Discrete Fourier Transform 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 4. Discrete Fourier Transform 4.2. Properties of the DFT • Circular symmetries – x’(n) is related to x(n) by a circular shift. 41 42 43 44 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 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 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution – The inverse of X3(k) is – Circular convolution 47 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Example 48 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution 49 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 50 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 51 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 52 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 53 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • The circular of the two sequences yields the sequence 54 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 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution • Compute the DFTs 56 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 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution • Solution • Thus, 58 4. Discrete Fourier Transform 4.3. Multiplication of two DFTs and Circular convolution 59 4. Discrete Fourier Transform • Exercise 60 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 5. Fast Fourier Transform • Direct computation of DFT does not exploit the symmetry and periodicity properties 62 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 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Because , • We also have • Result in a reduction of the number of multiplication 64 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 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Thus • The total number of multiplication is reduced again 66 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Comparison of computational complexity 67 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Perform 8-point DFT in 3 stages 68 69 5. Fast Fourier Transform 5.1. Radix-2 FFT algorithms • Basic butterfly computation 70 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 5. Fast Fourier Transform 5.2. Radix-4 FFT algorithms 72