《数字信号处理cha》PPT课件

1、2021/3/1,1,Chapter 2 Discrete Fourier Transform,Instructor: Ted Email: Phone2021/3/1,2,Three Questions about Discrete Fourier Transform,Q1: WHAT is DFT,Q2: WHY is DFT,Q3: HOW to DFT,WHAT is relationship between DFT and other kinds of Fourier Transform,WHY we need DFT,HOW to realize DFT?

2、 How to use DFT to solve the practical problems,2021/3/1,3,Basic contents of this chapter 2.1 Review of Fourier Transform 2.2 Discrete Fourier Series 2.3 Discrete Fourier Transform 2.4 Relationship between DFT, z-Transform and sequences Fourier Transform 2.5 Frequency sampling theorem 2.6 Compute se

3、quences linear convolution using DFT 2.7 Spectrum analysis based on DFT 2.8 Review,2021/3/1,4,2.1 Fourier Transform,In some situation, signals frequency spectrum can represent its characteristics more clearly,in frequency-domain,in time-domain,Fourier Transform,Signal Analysis and Processing （1）Time

4、 Domain Analysis: t-A （2）Frequency Domain Analysis: f-A,2021/3/1,5,2.1 Fourier Transform,Signal Analysis and Processing: （1）Time Domain Analysis （2）Frequency Domain Analysis Fourier Transform is a bridge from time domain to frequency domain,Characteristic: continuousdiscrete, periodicnonperiodic,Con

5、tinuous periodic signals,Continuous nonperiodic signals,Discrete periodic signals,Discrete nonperiodic signals,Type,2021/3/1,6,1) Continuous periodic signal-Fourier Series,It is proved that continuous-time periodic signal can be represented by a Fourier Series corresponding to a sum of harmonically

6、related complex exponential signal. To a periodic function with period,Conclusion: Continuous periodic function Nonperiodic discrete frequency impulse sequence,Time-domain,Frequency-domain,2021/3/1,7,2) Continuous nonperiodic functions Fourier Transform,Conclusion : Continuous nonperiodic function N

7、onperiodic continuous function,Time-domain,Frequency-domain,2021/3/1,8,3) Discrete-time nonperiodic sequences Fourier Transform,Conclusion : Discrete nonperiodic function Continuous-time periodic function,2021/3/1,9,4) Conclusion,1）Sampling in time domain brings periodicity in frequency domain,2）Sam

8、pling in frequency domain brings periodicity in time domain,3）Relationship between frequency domain and time domain Time domain Frequency domain Transform Continuous periodic Discrete nonperiodic Fourier series Continuous nonperiodic Continuous nonperiodic Fourier Transform Discrete nonperiodic Cont

9、inuous periodic Sequences Fourier Transform Discrete periodic Discrete periodic Discrete Fourier Series,Periodic Discrete; NonperiodicContinuous,2021/3/1,10,5) Basic idea of Discrete Fourier Transform,In practical application, signal processed by computer has two main characteristics,1) Discrete,2)

10、Finite length,Similarly, signals frequency must also have two main characteristics,Idea: Expand finite-length sequence to periodic sequence, compute its Discrete Fourier Series, so that we can get the discrete spectrum in frequency domain,But nonperiodic sequences Fourier Transform is a continuous f

11、unction of , and it is a periodic function in with a period 2. So it is not suitable to solve practical digital signal processing,2021/3/1,11,2.2 Discrete Fourier Series,1) Discrete Fourier Series Transform Pair,Similar with continuous-time periodic signals, a periodic sequence with period N, can be

12、 represented by a Fourier Series corresponding to a sum of harmonically related complex exponential sequences, such as,Attention: Fourier Series for discrete-time signal with period N requires only N harmonically related complex exponentials,2-1,where,2021/3/1,12,computation,2021/3/1,13,Attention,Di

13、screte Fourier Series for periodic sequence,2021/3/1,14,2) Properties of DFS,1）Linear,2）Sequence Shift,2021/3/1,15,2) Properties of DFS,3）Periodic Convolution,Compared with linear convolution, periodic convolutions main difference is: The sum is over the finite interval m=0N-1,Periodic convolution,2

14、021/3/1,16,Periodic convolution,2021/3/1,17,Symmetry,Multiplication of periodic sequence in time-domain is correspond to convolution of periodic sequence in frequency domain,2021/3/1,18,Periodic sequence and its DFS,2021/3/1,19,2.3 Discrete Fourier Transform-DFT,Periodic sequence and its DFS,2021/3/

15、1,20,HINTS,Periodic sequence is infinite length. but only N sequence values contain information,Periodic sequence finite length sequence. Relationship between these sequences,Infinite Finite Periodic Nonperiodic,2021/3/1,21,2.3 Discrete Fourier Transform-DFT,Relationship between periodic sequence an

16、d finite-length sequence,Periodic sequence can be seen as periodically copies of finite-length sequence. Finite-length sequence can be seen as extracting one period from periodic sequence,Main period,Finite-duration Sequence,Periodic Sequence,2021/3/1,22,2.3 Discrete Fourier Transform-DFT,2021/3/1,2

17、3,2.3 Discrete Fourier Transform,Get DFT by extracting one period of DFS,DFS of periodic sequence,Computation of DFT by extracting one period of DFS,To a finite-length sequence,Periodical copies,Attention：DFT is acquired by extracting one period of DFS, it is not a new kind of Fourier Transform,2021

18、/3/1,24,DFT Transform Pair,Inverse Transform,2021/3/1,25,Property of DFT,1) Linearity,2) Circular Shift Circular shift of x(n) can be defined,2021/3/1,26,Circular shift of sequence,Linear shift of sequence,2021/3/1,27,Symmetric between DFT and IDFT,2021/3/1,28,3）Parsevals Theorem,Conservation of ene

19、rgy in time domain and frequency domain,2021/3/1,29,4）Circular convolution,Periodic convolution is convolution of two sequences with period N in one period, so it is also a periodic sequence with period N. Circular convolution is acquired by extracting one period of periodic convolution, expressed b

20、y,Circular convolution,2021/3/1,30,f(n,Circular convolution,Periodic convolution,2021/3/1,31,Circular convolution can be used to compute two sequences linear convolution,2021/3/1,32,5）共轭对称性 Conjugate symmetric properties,a）DFT of conjugate sequence,Attention：X(k) has only k valid values：0k N-1,2021/

21、3/1,33,b） DFT of sequences real and imaginary part,2021/3/1,34,Xe(k) is even components of X(k), Xe(k) is conjugate symmetric; that is real part is equal, imaginary part is opposite,Xo(k) is odd components of X(k), Xo(k) is conjugate asymmetric; that is real part is opposite, imaginary part is equal

22、,2021/3/1,35,Xe(k) conjugate even part, conjugate symmetric; real part is equal, imaginary part is opposite,Xe(k)s real part,Xe(k)s imaginary part,2021/3/1,36,Conclusion,1）DFT of sequences real part is corresponding to X(k)s conjugate symmetric part. 2）DFT of sequences imaginary part is correspondin

23、g to X(k)s conjugate asymmetric part. 3）Suppose x(n) is a real sequence, that is x(n)=xr(n), then X(k) only has conjugate symmetric part, that is X(k) =Xe(k,So: If we get half X(k), we can acquire all X(k) using symmetric properties,2021/3/1,37,DFT Programming Example,DFT Matrix,2021/3/1,38,function

24、 Xk=dft(xn) N=length(xn); %length of sequence n=0:N-1; % time sample k=0:N-1; WN=exp(-j*2*pi/N); nk=n*k; WNnk=WN.nk; %calculate the DFT Matrix Xk=xn*WNnk; %compute DFT,More effective method,2021/3/1,39,Fs = 400; % Get the analyzed signal T = 1/Fs; L = 1000; t = (0:L-1)*T; x = 0.7*sin(2*pi*50*t); plo

25、t(1000*t(1:200),x(1:200); Y = dft(x)/L; % Discrete Fourier Transform f = Fs/2*linspace(0,1,L/2+1); stem(f,2*abs(Y(1:L/2+1,2021/3/1,40,2021/3/1,41,Summary,Basic idea of DFT; How to get DFT from DFS; Property of DFT,2021/3/1,42,2.4 DFT, Sequences Fourier Transform and z-transform,DFS,Sampling,Periodic

26、 Copies,Extract One period,Extract One period,DFT,Sequences Fourier Transform,Fourier Transform,Continuous-time,Discrete-time,2021/3/1,43,Three different frequency-domain representations of a finite-length discrete-time sequence,2. Sequences Fourier Transform,3. Discrete Fourier Transform (DFT,1. z-

27、Transform,单位圆,2021/3/1,44,2021/3/1,45,Relationship between,2021/3/1,46,2.5 Frequency sampling theorem,How to realize? Prerequisite for implementation? What is interpolation formula,1） Sampling x(n)s z-transform,Regular interval sampling on unit circle,Loss after sampling,2021/3/1,47,After sampling i

28、n frequency-domain, can we acquire sequence representing x(n) by inverse transforming from XN(k),is periodical copies of x(n), that is sampling in frequency domain causes periodical copies of sequence in time-domain,If we want to recover the finite-length sequence x(n) with no loss after sampling in

29、 frequency domain, then it must be satisfied: Suppose: M is number of points in time domain; N is number of points in frequency domain. Then: NM must be satisfied if we want to recovery x(n) with no loss from,Proof in page 78,2021/3/1,48,2） Interpolation formula,2021/3/1,49,Objective DFT or IDFT can

30、 be used to compute two sequences circular convolution, and DFT, IDFT have their fast algorithm. So if we can build the relationship between two sequences circular convolution and linear convolution, we can improve computation speed of linear convolution by fast Fourier Transform algorithm,2.6 Compu

31、ting sequences linear convolution with DFT,2021/3/1,50,Circular Convolution,Linear Convolution,What relationship between and ,2021/3/1,51,2021/3/1,52,2021/3/1,53,Process,Conclusion: We can compute linear convolution using circular convolution if length of DFTs satisfy,x(n,h(n,Zero padding,Zero paddi

32、ng,X(k,H(k,X(k)H(k,x(n) h(n) x(n) h(n,DFT,DFT,IDFT,2021/3/1,54,After FFT algorithm, overlap-add method and over-lap save method will be learned,Problems,In practical application: y(n)=x(n)*h(n), suppose x(n)s length is M，h(n) length is N； Usually, MN, If L=N+M-1, then: For short sequence: many zeros

33、 padded into h(n). For long sequence: compute after all sequence input. Difficulties：Large memory, long computation time, so real-time property can not be satisfied. Solution: decomposition computation on long sequence,Divided and Conquer,2021/3/1,55,Summary,Relationship between DFT, Sequence s Four

34、ier transform and z-transform; Frequency sampling theorem; Computation of linear convolution using DFT,2021/3/1,56,2.7 Spectrum analysis using DFT,1) Approximation process,Sample,1) Process of spectrum analysis using DFT,DFT,2) Error analysis,3) Important parameters,Spectrum analysis DFT Computation

35、,Discretization in time and frequency domain,2021/3/1,57,Basic theory of Fourier Transform,Finite duration signal Infinite width frequency spectrum; Finite width frequency spectrum Infinite duration signal. In practice, finite duration signal with finite width spectrum does not really exist. Wide ba

36、nd signals Filtering，fc fs/2 Infinite duration signals Extract finite points Engineering application： Filter high frequency component with small amplitude. Cut away signal component with small amplitude. In below sections, all signals xa(t) are supposed to be finite-length, band-limited signals afte

37、r filtering and extracting,2021/3/1,58,Process of spectrum analysis using DFT,2）Errors of spectrum analysis using DFT,3) Fence effect,Sampling,Convolution,1,3,2,1) Aliasing,2) Cutoff effect,Windowing,2021/3/1,59,2）Errors of spectrum analysis using DFT,Process of spectrum analysis using DFT,1) Aliasi

38、ng If condition is not met: there will be spectrum distortion at fs/2; Solution: increase fs, or using anti-aliasing pre-filtering. In practical application,2021/3/1,60,2）Cutoff effect of DFT,2）Errors of spectrum analysis using DFT,Convolution,1,2,Windowing,Process of spectrum analysis using DFT,202

39、1/3/1,61,Cutoff effect of DFT,Amplitude of square-wave functions,s spectrum before and after windowing by square-wave function,Leakage,Disturbance,Solution: increase Sampling points N, or using other kind of window function,2021/3/1,62,3,DFT,2）Errors of spectrum analysis using DFT,Process of spectru

40、m analysis using DFT,3) Fence effect N DFTN equal interval sampling of FT. Spectrum function value is omitted between sampling points, N intervals. Solution: Zero padding, or change sequences length, increase N,2021/3/1,63,Relationship between DFT and spectrum of continuous signals,Sampling frequency: fs; Sampling hold time: Tp; Sampling interval in frequency domain (Spectrum resolution): F; Sampling points: N,P86: example 3.4.1,Discrete Periodic Aperiodic Continuous,2021/3/1,64,3）Important