《数字信号处理chaPPT课件》由会员分享，可在线阅读，更多相关《数字信号处理chaPPT课件（71页珍藏版）》请在金锄头文库上搜索。
1、2024/7/281Chapter 2Chapter 2Discrete Fourier Transform Instructor: Ted Instructor: TedEmail:Email: Phone:13836034068Phone:138360340682024/7/282Three Questions about Three Questions about DiscreteDiscrete Fourier Transform Fourier TransformQ1: Q1: WWHAT is DFT?HAT is DFT?Q2: Q2: WWHY is DFT?HY is DFT
2、?Q3: HOQ3: HOWW to DFT? to DFT?WHAT is relationship between DFT and other kinds of Fourier WHAT is relationship between DFT and other kinds of Fourier Transform?Transform?WHY we need DFT?WHY we need DFT?HOW to realize DFT? How to use DFT to solve the practical HOW to realize DFT? How to use DFT to s
3、olve the practical problems?problems?2024/7/283Basic contents of this chapter 2.1 2.1 Review of Fourier TransformReview of Fourier Transform 2.2 Discrete Fourier Series 2.2 Discrete Fourier Series 2.3 2.3 DiscreteDiscrete Fourier TransformFourier Transform 2.4 2.4 Relationship between DFT, z-Transfo
4、rm and Relationship between DFT, z-Transform and sequences sequences Fourier Transform Fourier Transform 2.5 2.5 Frequency sampling theoremFrequency sampling theorem 2.6 2.6 Compute sequences linear convolution using Compute sequences linear convolution using DFTDFT 2. 2.7 7 Spectrum analysis based
5、on DFTSpectrum analysis based on DFT 2.8 Review 2.8 Review2024/7/2842.1 2.1 Fourier TransformFourier TransformIn some situation, signals frequency spectrum can represent its characteristics more clearly. in frequency-domain in time-domainFourierTransformSignal Analysis and ProcessingSignal Analysis
6、and Processing （1 1）Time Domain Analysis: t-ATime Domain Analysis: t-A （2 2）Frequency Domain Analysis: f-AFrequency Domain Analysis: f-A2024/7/2852.1 2.1 Fourier TransformFourier TransformSignal Analysis and Processing:Signal Analysis and Processing: （1 1）Time Domain AnalysisTime Domain Analysis （2
7、2）Frequency Domain AnalysisFrequency Domain AnalysisFourier Transform is a bridge from time domain to frequency domain. Fourier Transform is a bridge from time domain to frequency domain. Characteristic: continuousCharacteristic: continuousdiscrete, periodicdiscrete, periodicnonperiodicnonperiodic .
8、 .Continuous periodic signalsContinuous periodic signalsContinuous nonperiodic signalsContinuous nonperiodic signalsDiscrete periodic signalsDiscrete periodic signalsDiscrete nonperiodicDiscrete nonperiodic signalssignalsType: Type: 2024/7/2861) Continuous periodic signal-Fourier 1) Continuous perio
9、dic signal-Fourier SeriesSeriesIt is proved that continuous-time periodic signal can be represented by a It is proved that continuous-time periodic signal can be represented by a Fourier Series corresponding to a sum of harmonically related complex Fourier Series corresponding to a sum of harmonical
10、ly related complex exponential signal. To a periodic function with period , exponential signal. To a periodic function with period , Conclusion: Conclusion: Continuous periodicContinuous periodic function function Nonperiodic discreteNonperiodic discrete frequency impulse sequence frequency impulse
11、sequenceTime-domainFrequency-domain2024/7/2872 2) ) Continuous Continuous nonperiodicnonperiodic functions Fourier functions Fourier TransformTransformConclusionConclusion : : Continuous nonperiodicContinuous nonperiodic function function Nonperiodic continuousNonperiodic continuous function functio
12、nTime-domainFrequency-domain2024/7/2883 3) ) Discrete-time Discrete-time nonperiodicnonperiodic sequences Fourier sequences Fourier TransformTransformConclusionConclusion : : Discrete nonperiodicDiscrete nonperiodic function function Continuous-time periodicContinuous-time periodic function function
13、Time-domainFrequency-domain2024/7/2894) Conclusion4) Conclusion（1 1）Sampling in time domain brings periodicity in frequency domain.Sampling in time domain brings periodicity in frequency domain.（2 2）Sampling in frequencySampling in frequency domain brings periodicity in time domain.domain brings per
14、iodicity in time domain.（3 3）Relationship between frequency domain and time domainRelationship between frequency domain and time domain Time domain Frequency domain Time domain Frequency domain TransformTransform Continuous periodic Continuous periodic Discrete nonperiodic Fourier seriesDiscrete non
15、periodic Fourier series Continuous nonperiodic Continuous nonperiodic Continuous nonperiodic Continuous nonperiodic Fourier TransformFourier Transform Discrete nonperiodic Continuous periodicDiscrete nonperiodic Continuous periodic Sequences Fourier Sequences Fourier Transform Transform Discrete per
16、iodic Discrete periodic Discrete Fourier SeriesDiscrete periodic Discrete periodic Discrete Fourier SeriesPeriodic Periodic Discrete; Discrete; NonperiodicNonperiodicContinuousContinuous2024/7/28105) Basic idea of Discrete Fourier Transform5) Basic idea of Discrete Fourier TransformIn practical appl
17、ication, In practical application, signal processed by computer has two main characteristics:signal processed by computer has two main characteristics:(1) Discrete (1) Discrete (2) Finite length(2) Finite lengthSimilarly, Similarly, signals frequency must also have two main characteristics:signals f
18、requency must also have two main characteristics:(1) Discrete (1) Discrete (2) Finite length(2) Finite length IdeaIdea: : Expand Expand finite-length sequence to periodic sequencefinite-length sequence to periodic sequence, compute its Discrete , compute its Discrete Fourier Series, so that we can g
19、et the discrete spectrum in frequency domain.Fourier Series, so that we can get the discrete spectrum in frequency domain.But nonperiodic sequences Fourier Transform is a continuous function of But nonperiodic sequences Fourier Transform is a continuous function of , and it , and it is a periodic fu
20、nction in is a periodic function in with a period with a period 2 2 . So it is not suitable to solve practical . So it is not suitable to solve practical digital signal processing.digital signal processing. 2024/7/28112.2 Discrete Fourier Series1) Discrete Fourier Series Transform PairSimilar with c
21、ontinuous-time periodic signals, a periodic 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 comp
22、lex exponentials.（2-1）where2024/7/2812 computation2024/7/2813Attention:Discrete Fourier Series for periodic sequence:2024/7/28142) Properties of DFS（1）LinearLinear（2）Sequence ShiftSequence Shift2024/7/28152) Properties of DFS（3）Periodic ConvolutionPeriodic ConvolutionCompared with linear convolution
23、, periodic convolutions main difference is: The sum is over the finite interval m=0N-1.Periodic convolution2024/7/2816Periodic convolutionPeriodic convolution2024/7/2817SymmetrySymmetry:Multiplication of periodic sequence in time-Multiplication of periodic sequence in time-domain is correspond to co
24、nvolution of domain is correspond to convolution of periodic sequence in frequency domain.periodic sequence in frequency domain.2024/7/2818Periodic sequence and its DFS2024/7/28192.3 Discrete Fourier Transform-DFT2.3 Discrete Fourier Transform-DFTPeriodic sequence and its DFS2024/7/2820 HINTS Period
25、ic sequence is infinite length.but only N sequence values contain information.Periodic sequence finite length sequence.Relationship between these sequences?Infinite FinitePeriodic Nonperiodic2024/7/28212.3 Discrete Fourier Transform-DFT2.3 Discrete Fourier Transform-DFT Relationship between periodic
26、 sequence and finite-length sequencePeriodic 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 periodFinite-duration SequenceFinite-duration SequencePeriodic SequencePeriodic Sequence2024/7/28
27、222.3 Discrete Fourier Transform-DFT2.3 Discrete Fourier Transform-DFT2024/7/28232.3 Discrete Fourier Transform2.3 Discrete Fourier TransformGet DFT by extracting one period of DFSDFS of periodic sequenceComputation of DFT by extracting one period of DFSTo a finite-length sequence : Periodical copie
28、s Attention：DFT is acquired by extracting one period of DFS, it is not a new kind of Fourier Transform. 2024/7/2824 DFT TransformPair Inverse TransformInverse Transform2024/7/2825Property of DFT(1) Linearity(2) Circular Shift Circular shift of x(n) can be defined:2024/7/2826Circular shift of sequenc
29、eCircular shift of sequence Linear shift of sequenceLinear shift of sequence2024/7/2827Symmetric between DFT and IDFTSymmetric between DFT and IDFT2024/7/2828（3）Parsevals TheoremParsevals TheoremConservation of energy in time domain and frequency domain.2024/7/2829（4 4）Circular convolutionCircular c
30、onvolutionPeriodic 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 by .Circular convolution2024/7/2830f(n)Circular convolutionCircular
31、 convolutionPeriodic convolutionPeriodic convolution2024/7/2831Circular convolution can be used to compute Circular convolution can be used to compute two sequencetwo sequences linear convolution.s linear convolution.2024/7/2832（5 5）共轭对称性）共轭对称性）共轭对称性）共轭对称性 Conjugate symmetric propertiesConjugate sym
32、metric propertiesa）DFT of conjugate sequenceAttention：X(k) has only k valid values：0 k N-12024/7/2833b） DFT of sequences real and imaginary part 2024/7/2834X Xe e(k) is even components of X(k), X(k) is even components of X(k), Xe e(k) is conjugate (k) is conjugate symmetric;symmetric;that is real pa
33、rt is equal, imaginary part is opposite.that is real part is equal, imaginary part is opposite.X Xo o(k) is odd components of X(k), X(k) is odd components of X(k), Xo o(k) is conjugate (k) is conjugate asymmetric;asymmetric;that is real part is that is real part is oppositeopposite, imaginary part i
34、s , imaginary part is equalequal. .2024/7/2835Xe(k) conjugate even part,conjugate symmetric;real part is equal, imaginary part is opposite.Xe(k)s real partXe(k)s imaginary partXo(k) conjugate odd part ， conjugate asymmetric;real part is opposite, imaginary part is equal.Xo(k)s real partXo(k)s imagin
35、ary part2024/7/2836Conclusion1）DFT of sequences real part is corresponding 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
36、 is X(k) =Xe(k)So: If we get half X(k), we can acquire all X(k) using symmetric properties.2024/7/2837DFT Programming ExampleDFT Matrix2024/7/2838function Xk=dft(xn)N=length(xn); %length of sequencen=0:N-1; % time samplek=0:N-1; WN=exp(-j*2*pi/N);nk=n*k;WNnk=WN.nk; %calculate the DFT MatrixXk=xn*WNn
37、k; %compute DFTMore effective method.2024/7/2839Fs = 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 Transformf = Fs/2*linspace(0,1,L/2+1); stem(f,2*abs(Y(1:L/2+1); 2024/7/28402024/7/2841SummaryBas
38、ic idea of DFT;How to get DFT from DFS;Property of DFT.2024/7/28422.4 DFT, Sequences Fourier Transform and z-transformDFSSamplingPeriodic CopiesExtract One periodExtract One periodDFTSequences Fourier TransformFourier TransformContinuous-timeDiscrete-time2024/7/2843Three different frequency-domain r
39、epresentations of a finite-length discrete-time sequence 2. Sequences Fourier Transform2. Sequences Fourier Transform3. Discrete Fourier Transform 3. Discrete Fourier Transform (DFT)(DFT)1. z-Transform1. z-Transform单位圆单位圆2024/7/2844jImzRezX(k)X(k) and X(z) ?and X(z) ?X(k)X(k) and X(eand X(ejwjw) ?)
40、?2024/7/2845Relationship between2024/7/28462.2.5 Frequency sampling 5 Frequency sampling theoremtheoremHow to realize? Prerequisite for How to realize? Prerequisite for implementation? implementation? What is interpolation formula? What is interpolation formula? 1 1） SamplingSampling x(n x(n) )s z-t
41、ransform:s z-transform:Regular interval sampling on unit circle:Regular interval sampling on unit circle:Loss after sampling?Loss after sampling?2024/7/2847After sampling in frequency-domain, can we acquire sequence After sampling in frequency-domain, can we acquire sequence representing representin
42、g x x( (n n) by) by inverse transforming from Xinverse transforming from XN N( (k k)?)? is periodical copies of is periodical copies of x x( (n n), that is sampling in frequency ), that is sampling in frequency domain causes periodical copies of sequence in time-domain.domain causes periodical copie
43、s of sequence in time-domain. If we want to recover the finite-length sequence If we want to recover the finite-length sequence x x( (n n) with no ) with no loss after sampling in frequency domain, then it must be satisfied: loss after sampling in frequency domain, then it must be satisfied: Suppose
44、: Suppose: MM is number of points in time domain; is number of points in time domain; N N is number of points in frequency domain.is number of points in frequency domain. Then: Then: N N MM must be satisfied if we want to recovery must be satisfied if we want to recovery x x( (n n) with no ) with no
45、 loss from .loss from .(Proof in page 78)(Proof in page 78)= ？2024/7/28482 2） Interpolation formulaInterpolation formula2024/7/2849Objective 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
46、 sequences circular convolution and linear convolution, we can improve computation speed of linear convolution by fast Fourier Transform algorithm.2.6 Computing sequences linear convolution with DFT2024/7/2850Circular Convolution Linear Convolution What relationship between and ?2024/7/28512024/7/28
47、522024/7/2853ProcessConclusion: We can compute linear convolution using circular convolution if length of DFTs satisfyx(n)h(n)Zero paddingZero paddingX(k)H(k)X(k)H(k)x(n) h(n)x(n) h(n)DFTDFTIDFT2024/7/2854After FFT algorithm, overlap-add method and over-lap save method will be learned.Problems: In p
48、ractical 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 sati
49、sfied.Solution: decomposition computation on long sequence.Divided and ConquerDivided and Conquer2024/7/2855SummaryRelationship between DFT, Sequence s Fourier transform and z-transform;Frequency sampling theorem;Computation of linear convolution using DFT.2024/7/28562.7 Spectrum analysis using DFT2
50、.7 Spectrum analysis using DFT(1) (1) Approximation Approximation process.process.Sample1) Process of spectrum analysis using 1) Process of spectrum analysis using DFTDFTDFT(2) Error analysis.(2) Error analysis.(3) Important parameters.(3) Important parameters.Spectrum analysisSpectrum analysis DFT
51、ComputationDFT ComputationDiscretization in time and Discretization in time and frequency domainfrequency domain 2024/7/2857Basic theory of Fourier TransformBasic theory of Fourier Transforml lFinite duration signal Infinite width frequency spectrum;Finite duration signal Infinite width frequency sp
52、ectrum;l lFinite width frequency spectrum Infinite duration signal. Finite width frequency spectrum Infinite duration signal. In practice, finite duration signal with finite width spectrum does In practice, finite duration signal with finite width spectrum does not really exist.not really exist.l lW
53、ide band signals FilteringWide band signals Filtering，f fc c f fs s/2/2l lInfinite duration signals Extract finite pointsInfinite duration signals Extract finite pointsl lEngineering applicationEngineering application： Filter high frequency component with small amplitude. Filter high frequency compo
54、nent with small amplitude. Cut away signal component with small amplitude. Cut away signal component with small amplitude. In below sections, all signals x In below sections, all signals xa a(t) are supposed to be finite-(t) are supposed to be finite-length, band-limited signals after filtering and
55、extracting.length, band-limited signals after filtering and extracting.2024/7/2858Process of spectrum analysis using Process of spectrum analysis using DFTDFT2 2）Errors of spectrum analysis using DFT Errors of spectrum analysis using DFT (3)(3) Fence effectFence effectSamplingConvolution（1）（3）（2）(1)
56、 (1) AliasingAliasing(2) Cutoff effect(2) Cutoff effect Windowing2024/7/2859（1）SamplingDFT2 2）Errors of spectrum analysis using DFT Errors of spectrum analysis using DFT Process of spectrum analysis using Process of spectrum analysis using DFTDFT(1) Aliasing(1) Aliasing If condition is not met: ther
57、e will be spectrum distortion at fs/2;If condition is not met: there will be spectrum distortion at fs/2; Solution: increase fs, or using anti-aliasing pre-filtering.Solution: increase fs, or using anti-aliasing pre-filtering. In practical application, In practical application, 2024/7/2860（2 2）Cutof
58、f effect of DFT 2 2）Errors of spectrum analysis using DFT Errors of spectrum analysis using DFT Convolution（1）（2）WindowingProcess of spectrum analysis using Process of spectrum analysis using DFTDFT2024/7/2861Cutoff effect of DFTAmplitude of square-wave functionss spectrum before and after windowing
59、 by square-wave function.LeakageDisturbance Solution: increase Sampling points N, or using other kind of Solution: increase Sampling points N, or using other kind of window function. window function.2024/7/2862（3）DFT2 2）Errors of spectrum analysis using DFT Errors of spectrum analysis using DFT Proc
60、ess of spectrum analysis using Process of spectrum analysis using DFTDFT(3) Fence effect(3) Fence effect N N DFTN equal interval sampling of FT.DFTN equal interval sampling of FT. Spectrum function value is omitted between sampling points, N intervals.Spectrum function value is omitted between sampl
61、ing points, N intervals. Solution: Zero padding, or change sequences length, increase N. Solution: Zero padding, or change sequences length, increase N.2024/7/2863Relationship between DFT and spectrum of continuous signalsRelationship between DFT and spectrum of continuous signalsSampling frequency:
62、 fs; Sampling hold time: Tp; Sampling frequency: fs; Sampling hold time: Tp; Sampling interval in frequency domain (Spectrum resolution): F;Sampling interval in frequency domain (Spectrum resolution): F;Sampling points: NSampling points: NP86: example 3.4.1P86: example 3.4.1Discrete Discrete Periodi
63、cPeriodicAperiodic Aperiodic Continuous Continuous2024/7/28643）Important parameter of DFTSome important conclusionSome 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 ac
64、quired by increase N, Tp=NT, that is increase sampling length.2024/7/2865Determine sampling rate by signals highest Determine sampling rate by signals highest frequency .frequency .Procedure of spectrum analysis using DFT Adjust parameters by DFT results.Adjust parameters by DFT results. Determine e
65、xtracting length N by frequency Determine extracting length N by frequency resolution. resolution.2024/7/2866DFT Programming ExampleDFT Matrix2024/7/2867function Xk=dft(xn)N=length(xn); % length of sequencen=0:N-1; % time samplek=0:N-1; WN=exp(-j*2*pi/N);nk=n*k;WNnk=WN.nk; %calculate the DFT MatrixX
66、k=xn*WNnk; %compute DFT更加高效的算法？更加高效的算法？2024/7/2868Fs = 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 Transformf = Fs/2*linspace(0,1,L/2+1); stem(f,2*abs(Y(1:L/2+1); 2024/7/28692024/7/28705）Summar
67、y (1) Basic principle of spectrum analysis using DFT.(2) Error of spectrum analysis using DFT.(3) Important parameters selection.2024/7/2871Three Questions about Three Questions about DiscreteDiscrete Fourier Transform Fourier TransformQ1: Q1: WWHAT is DFT?HAT is DFT?Q2: Q2: WWHY is DFT?HY is DFT?Q3
68、: HOQ3: HOWW to DFT? to DFT?WHAT is relationship between DFT and other kinds of Fourier WHAT is relationship between DFT and other kinds of Fourier Transform?Transform?WHY we need DFT?WHY we need DFT?HOW to realize DFT? How to use DFT to solve the practical HOW to realize DFT? How to use DFT to solve the practical problems?problems?
