《《数字信号处理cha》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数字信号处理cha》PPT课件.ppt（71页珍藏版）》请在三一文库上搜索。
1、2021/3/31,1,Chapter 2 Discrete Fourier Transform,Instructor: Ted Email: Phone:13836034068,2021/3/31,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 reali
2、ze DFT? How to use DFT to solve the practical problems?,2021/3/31,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 C
3、ompute sequences linear convolution using DFT 2.7 Spectrum analysis based on DFT 2.8 Review,2021/3/31,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 Process
4、ing （1）Time Domain Analysis: t-A （2）Frequency Domain Analysis: f-A,2021/3/31,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, periodicno
5、nperiodic .,Continuous periodic signals,Continuous nonperiodic signals,Discrete periodic signals,Discrete nonperiodic signals,Type:,？,2021/3/31,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 s
6、um of harmonically 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/31,7,2) Continuous nonperiodic functions Fourier Transform,Conclusion : Continuous n
7、onperiodic function Nonperiodic continuous function,Time-domain,Frequency-domain,2021/3/31,8,3) Discrete-time nonperiodic sequences Fourier Transform,Conclusion : Discrete nonperiodic function Continuous-time periodic function,2021/3/31,9,4) Conclusion,（1）Sampling in time domain brings periodicity i
8、n frequency domain.,（2）Sampling 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 Transfo
9、rm Discrete nonperiodic Continuous periodic Sequences Fourier Transform Discrete periodic Discrete periodic Discrete Fourier Series,Periodic Discrete; NonperiodicContinuous,2021/3/31,10,5) Basic idea of Discrete Fourier Transform,In practical application, signal processed by computer has two main ch
10、aracteristics:,(1) Discrete,(2) 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 F
11、ourier Transform is a continuous function 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/31,11,2.2 Discrete Fourier Series,1) Discrete Fourier Series Transform Pair,Similar with continuous-time periodic signals, a per
12、iodic sequence with period N, can be 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/3
13、1,12,computation,2021/3/31,13,Attention:,Discrete Fourier Series for periodic sequence:,2021/3/31,14,2) Properties of DFS,（1）Linear,（2）Sequence Shift,2021/3/31,15,2) Properties of DFS,（3）Periodic Convolution,Compared with linear convolution, periodic convolutions main difference is: The sum is over
14、the finite interval m=0N-1.,Periodic convolution,2021/3/31,16,Periodic convolution,2021/3/31,17,Symmetry:,Multiplication of periodic sequence in time-domain is correspond to convolution of periodic sequence in frequency domain.,2021/3/31,18,Periodic sequence and its DFS,2021/3/31,19,2.3 Discrete Fou
15、rier Transform-DFT,Periodic sequence and its DFS,2021/3/31,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/31,21,2.3 Discrete Fou
16、rier Transform-DFT,Relationship between periodic sequence and 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 Seque
17、nce,2021/3/31,22,2.3 Discrete Fourier Transform-DFT,2021/3/31,23,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
18、one period of DFS, it is not a new kind of Fourier Transform.,2021/3/31,24,DFT Transform Pair,Inverse Transform,2021/3/31,25,Property of DFT,(1) Linearity,(2) Circular Shift Circular shift of x(n) can be defined:,2021/3/31,26,Circular shift of sequence,Linear shift of sequence,2021/3/31,27,Symmetric
19、 between DFT and IDFT,2021/3/31,28,（3）Parsevals Theorem,Conservation of energy in time domain and frequency domain.,2021/3/31,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 convolu
20、tion is acquired by extracting one period of periodic convolution, expressed by .,Circular convolution,2021/3/31,30,f(n),Circular convolution,Periodic convolution,2021/3/31,31,Circular convolution can be used to compute two sequences linear convolution.,2021/3/31,32,（5）共轭对称性 Conjugate symmetric prop
21、erties,a）DFT of conjugate sequence,Attention：X(k) has only k valid values：0k N-1,2021/3/31,33,b） DFT of sequences real and imaginary part,2021/3/31,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(
22、k), Xo(k) is conjugate asymmetric; that is real part is opposite, imaginary part is equal.,2021/3/31,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/31,36,Conclusion,1）DFT of sequences real part is corre
23、sponding to X(k)s conjugate symmetric part. 2）DFT of sequences imaginary part is corresponding 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)
24、using symmetric properties.,2021/3/31,37,DFT Programming Example,DFT Matrix,2021/3/31,38,function 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/31,39
25、,Fs = 400; % Get the analyzed signal T = 1/Fs; L = 1000; t = (0:L-1)*T; x = 0.7*sin(2*pi*50*t); plot(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/31,40,2021/3/31,41,Summary,Basic idea of DFT; How to get DFT from DFS;
26、 Property of DFT.,2021/3/31,42,2.4 DFT, Sequences Fourier Transform and z-transform,DFS,Sampling,Periodic Copies,Extract One period,Extract One period,DFT,Sequences Fourier Transform,Fourier Transform,Continuous-time,Discrete-time,2021/3/31,43,Three different frequency-domain representations of a fi
27、nite-length discrete-time sequence,2. Sequences Fourier Transform,3. Discrete Fourier Transform (DFT),1. z-Transform,单位圆,2021/3/31,44,2021/3/31,45,Relationship between,2021/3/31,46,2.5 Frequency sampling theorem,How to realize? Prerequisite for implementation? What is interpolation formula?,1） Sampl
28、ing x(n)s z-transform:,Regular interval sampling on unit circle:,Loss after sampling?,2021/3/31,47,After sampling in 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 co
29、pies of sequence in time-domain.,If we want to recover the finite-length sequence x(n) with no loss after sampling in 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 recove
30、ry x(n) with no loss from .,(Proof in page 78),2021/3/31,48,2） Interpolation formula,2021/3/31,49,Objective DFT or IDFT can 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 a
31、nd linear convolution, we can improve computation speed of linear convolution by fast Fourier Transform algorithm.,2.6 Computing sequences linear convolution with DFT,2021/3/31,50,Circular Convolution,Linear Convolution,What relationship between and ?,2021/3/31,51,2021/3/31,52,2021/3/31,53,Process,C
32、onclusion: We can compute linear convolution using circular convolution if length of DFTs satisfy,x(n),h(n),Zero padding,Zero padding,X(k),H(k),X(k)H(k),x(n) h(n) x(n) h(n),DFT,DFT,IDFT,2021/3/31,54,After FFT algorithm, overlap-add method and over-lap save method will be learned.,Problems:,In practi
33、cal 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 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 satisfi
34、ed. Solution: decomposition computation on long sequence.,Divided and Conquer,2021/3/31,55,Summary,Relationship between DFT, Sequence s Fourier transform and z-transform; Frequency sampling theorem; Computation of linear convolution using DFT.,2021/3/31,56,2.7 Spectrum analysis using DFT,(1) Approxi
35、mation process.,Sample,1) Process of spectrum analysis using DFT,DFT,(2) Error analysis.,(3) Important parameters.,Spectrum analysis DFT Computation,Discretization in time and frequency domain,2021/3/31,57,Basic theory of Fourier Transform,Finite duration signal Infinite width frequency spectrum; Fi
36、nite width frequency spectrum Infinite duration signal. In practice, finite duration signal with finite width spectrum does not really exist. Wide band signals Filtering，fc fs/2 Infinite duration signals Extract finite points Engineering application： Filter high frequency component with small amplit
37、ude. Cut away signal component with small amplitude. In below sections, all signals xa(t) are supposed to be finite-length, band-limited signals after filtering and extracting.,2021/3/31,58,Process of spectrum analysis using DFT,2）Errors of spectrum analysis using DFT,(3) Fence effect,Sampling,Convo
38、lution,（1）,（3）,（2）,(1) Aliasing,(2) Cutoff effect,Windowing,2021/3/31,59,2）Errors of spectrum analysis using DFT,Process of spectrum analysis using DFT,(1) Aliasing If condition is not met: there will be spectrum distortion at fs/2; Solution: increase fs, or using anti-aliasing pre-filtering. In pra
39、ctical application,2021/3/31,60,（2）Cutoff effect of DFT,2）Errors of spectrum analysis using DFT,Convolution,（1）,（2）,Windowing,Process of spectrum analysis using DFT,2021/3/31,61,Cutoff effect of DFT,Amplitude of square-wave functions,s spectrum before and after windowing by square-wave function.,Lea
40、kage,Disturbance,Solution: increase Sampling points N, or using other kind of window function.,2021/3/31,62,（3）,DFT,2）Errors of spectrum analysis using DFT,Process of spectrum analysis using DFT,(3) Fence effect N DFTN equal interval sampling of FT. Spectrum function value is omitted between samplin
41、g points, N intervals. Solution: Zero padding, or change sequences length, increase N.,2021/3/31,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: exam
42、ple 3.4.1,Discrete Periodic Aperiodic Continuous,2021/3/31,64,3）Important parameter of DFT,Some important conclusion,(2) If N unchanged, F incensement can only be acquired by lowering fs . So spectrum analysis scope will be small. (3) fs unchanged, F incensement can only be acquired by increase N, T
43、p=NT, that is increase sampling length.,2021/3/31,65,Determine sampling rate by signals highest frequency .,Procedure of spectrum analysis using DFT,Adjust parameters by DFT results.,Determine extracting length N by frequency resolution.,2021/3/31,66,DFT Programming Example,DFT Matrix,2021/3/31,67,f
44、unction 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,更加高效的算法？,2021/3/31,68,Fs = 400; % Get the analyzed signal T = 1/Fs; L = 1000; t = (0:L-1)*T; x = 0.7*sin(2*pi*50*t); plot(10
45、00*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/31,69,2021/3/31,70,5）Summary,(1) Basic principle of spectrum analysis using DFT. (2) Error of spectrum analysis using DFT. (3) Important parameters selection.,2021/3/31,71,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? How to use DFT to solve the practical problems?,