Chapter2DiscreteFourierTransform

Instructor:TedEmail:yzmhit@163.comPhone:138360340682023/5/71整理課件ThreeQuestionsaboutDiscreteFourierTransformQ1:WHATisDFT?Q2:WHYisDFT?Q3:HOWtoDFT?WHATisrelationshipbetweenDFTandotherkindsofFourierTransform?WHYweneedDFT?HOWtorealizeDFT?HowtouseDFTtosolvethepracticalproblems?2023/5/72整理課件Basiccontentsofthischapter2.1ReviewofFourierTransform2.2DiscreteFourierSeries2.3Discrete

FourierTransform2.4RelationshipbetweenDFT,z-Transformandsequence’sFourierTransform2.5Frequencysamplingtheorem2.6Computesequence’slinearconvolutionusingDFT2.7SpectrumanalysisbasedonDFT2.8Review2023/5/73整理課件2.1FourierTransformInsomesituation,signal’sfrequencyspectrumcanrepresentitscharacteristicsmoreclearly.infrequency-domainintime-domainFourierTransformSignalAnalysisandProcessing（1）TimeDomainAnalysis:t-A（2）FrequencyDomainAnalysis:f-A2023/5/74整理課件2.1FourierTransformSignalAnalysisandProcessing:（1）TimeDomainAnalysis（2）FrequencyDomainAnalysisFourierTransformisabridgefromtimedomaintofrequencydomain.Characteristic:continuous—discrete,periodic—nonperiodic

.ContinuousperiodicsignalsContinuousnonperiodicsignalsDiscreteperiodicsignalsDiscretenonperiodic

signalsType:？2023/5/75整理課件1)Continuousperiodicsignal--FourierSeriesItisprovedthatcontinuous-timeperiodicsignalcanberepresentedbyaFourierSeriescorrespondingtoasumofharmonicallyrelatedcomplexexponentialsignal.Toaperiodicfunctionwithperiod,Conclusion:Continuousperiodic

function—

NonperiodicdiscretefrequencyimpulsesequenceTime-domainFrequency-domain2023/5/76整理課件2)Continuousnonperiodic

function’sFourierTransformConclusion

:Continuousnonperiodic

function—

NonperiodiccontinuousfunctionTime-domainFrequency-domain2023/5/77整理課件3)Discrete-timenonperiodic

sequence’sFourierTransformConclusion

:Discretenonperiodicfunction—

Continuous-timeperiodicfunctionTime-domainFrequency-domain2023/5/78整理課件4)Conclusion（1）Samplingintimedomainbringsperiodicityinfrequencydomain.（2）Samplinginfrequency

domainbringsperiodicityintimedomain.（3）Relationshipbetweenfrequencydomainandtimedomain

TimedomainFrequencydomainTransform

ContinuousperiodicDiscretenonperiodicFourierseriesContinuousnonperiodicContinuousnonperiodic

FourierTransform

DiscretenonperiodicContinuousperiodic

Sequence’sFourierTransform

DiscreteperiodicDiscreteperiodicDiscreteFourierSeriesPeriodicDiscrete;NonperiodicContinuous2023/5/79整理課件5)BasicideaofDiscreteFourierTransformInpracticalapplication,signalprocessedbycomputerhastwomaincharacteristics:(1)Discrete(2)FinitelengthSimilarly,signal’sfrequencymustalsohavetwomaincharacteristics:(1)Discrete

(2)Finitelength

Idea:

Expandfinite-lengthsequencetoperiodicsequence,computeitsDiscreteFourierSeries,sothatwecangetthediscretespectruminfrequencydomain.Butnonperiodicsequence’sFourierTransformisacontinuousfunctionof,anditisaperiodicfunctioninwithaperiod2.Soitisnotsuitabletosolvepracticaldigitalsignalprocessing.

2023/5/710整理課件2.2DiscreteFourierSeries1)DiscreteFourierSeriesTransformPairSimilarwithcontinuous-timeperiodicsignals,aperiodicsequencewithperiodN,canberepresentedbyaFourierSeriescorrespondingtoasumofharmonicallyrelatedcomplexexponentialsequences,suchas:Attention:

FourierSeriesfordiscrete-timesignalwithperiodNrequiresonlyNharmonicallyrelatedcomplexexponentials.（2-1）where2023/5/711整理課件computation2023/5/712整理課件Attention:DiscreteFourierSeriesforperiodicsequence:2023/5/713整理課件2)PropertiesofDFS（1）Linear（2）SequenceShift2023/5/714整理課件2)

PropertiesofDFS（3）PeriodicConvolutionComparedwithlinearconvolution,periodicconvolution’smaindifferenceis:Thesumisoverthefiniteintervalm=0~N-1.Periodicconvolution2023/5/715整理課件Periodicconvolution2023/5/716整理課件Symmetry:Multiplicationofperiodicsequenceintime-domainiscorrespondtoconvolutionofperiodicsequenceinfrequencydomain.2023/5/717整理課件PeriodicsequenceanditsDFS2023/5/718整理課件2.3DiscreteFourierTransform-DFTPeriodicsequenceanditsDFS2023/5/719整理課件

HINTS

Periodicsequenceisinfinitelength.butonlyNsequencevaluescontaininformation.Periodicsequencefinitelengthsequence.Relationshipbetweenthesesequences?InfiniteFinitePeriodicNonperiodic2023/5/720整理課件2.3DiscreteFourierTransform-DFT

Relationshipbetweenperiodicsequenceandfinite-lengthsequencePeriodicsequencecanbeseenasperiodicallycopiesoffinite-lengthsequence.Finite-lengthsequencecanbeseenasextractingoneperiodfromperiodicsequence.MainperiodFinite-durationSequencePeriodicSequence2023/5/721整理課件2.3DiscreteFourierTransform-DFT2023/5/722整理課件2.3DiscreteFourierTransformGetDFTbyextractingoneperiodofDFSDFSofperiodicsequenceComputationofDFTbyextractingoneperiodofDFSToafinite-lengthsequence:PeriodicalcopiesAttention：DFTisacquiredbyextractingoneperiodofDFS,itisnotanewkindofFourierTransform.2023/5/723整理課件

DFTTransformPairInverseTransform2023/5/724整理課件PropertyofDFT(1)Linearity(2)CircularShiftCircularshiftofx(n)canbedefined:2023/5/725整理課件CircularshiftofsequenceLinearshiftofsequence2023/5/726整理課件SymmetricbetweenDFTandIDFT2023/5/727整理課件（3）Parseval’sTheoremConservationofenergyintimedomainandfrequencydomain.2023/5/728整理課件（4）CircularconvolutionPeriodicconvolutionisconvolutionoftwosequenceswithperiodNinoneperiod,soitisalso

aperiodicsequencewithperiodN.Circularconvolutionisacquiredbyextractingoneperiodofperiodicconvolution,expressedby

.Circularconvolution2023/5/729整理課件f(n)CircularconvolutionPeriodicconvolution2023/5/730整理課件Circularconvolutioncanbeusedtocomputetwosequence’slinearconvolution.2023/5/731整理課件（5）共軛對稱性Conjugatesymmetricpropertiesa）DFTofconjugatesequenceAttention：X(k)hasonlykvalidvalues：0kN-12023/5/732整理課件b）DFTofsequence’srealandimaginarypart2023/5/733整理課件Xe(k)isevencomponentsofX(k),Xe(k)isconjugatesymmetric;thatisrealpartisequal,imaginarypartisopposite.Xo(k)isoddcomponentsofX(k),Xo(k)isconjugateasymmetric;thatisrealpartisopposite,imaginarypartisequal.2023/5/734整理課件Xe(k)conjugateevenpart,conjugatesymmetric;realpartisequal,imaginarypartisopposite.Xe(k)’srealpartXe(k)’simaginarypartXo(k)conjugateoddpart

，conjugateasymmetric;realpartisopposite,imaginarypartisequal.Xo(k)’srealpartXo(k)’simaginarypart2023/5/735整理課件Conclusion1）DFTofsequence’srealpartiscorrespondingtoX(k)’sconjugatesymmetricpart.2）DFTofsequence’simaginarypartiscorrespondingtoX(k)’sconjugateasymmetricpart.3）Supposex(n)isarealsequence,thatisx(n)=xr(n),thenX(k)onlyhasconjugatesymmetricpart,thatisX(k)=Xe(k)So:IfwegethalfX(k),wecanacquireallX(k)usingsymmetricproperties.2023/5/736整理課件DFTProgrammingExampleDFTMatrix2023/5/737整理課件function[Xk]=dft(xn)N=length(xn);%lengthofsequencen=0:N-1;%timesamplek=0:N-1;

WN=exp(-j*2*pi/N);nk=n'*k;WNnk=WN.^nk;%calculatetheDFTMatrixXk=xn*WNnk;%computeDFTMoreeffectivemethod.2023/5/738整理課件Fs=400;%GettheanalyzedsignalT=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;%DiscreteFourierTransformf=Fs/2*linspace(0,1,L/2+1);stem(f,2*abs(Y(1:L/2+1)));2023/5/739整理課件2023/5/740整理課件SummaryBasicideaofDFT;HowtogetDFTfromDFS;PropertyofDFT.2023/5/741整理課件2.4DFT,Sequence’sFourierTransformandz-transformDFSSamplingPeriodicCopiesExtractOneperiodExtractOneperiodDFTSequence’sFourierTransformFourierTransformContinuous-timeDiscrete-time2023/5/742整理課件Threedifferentfrequency-domainrepresentationsofafinite-lengthdiscrete-timesequence

2.Sequence’sFourierTransform3.DiscreteFourierTransform(DFT)1.z-Transform單位圓2023/5/743整理課件jIm[z]Re[z]X(k)

andX(z)?X(k)

andX(ejw)?2023/5/744整理課件Relationshipbetween2023/5/745整理課件2.5FrequencysamplingtheoremHowtorealize?Prerequisiteforimplementation?Whatisinterpolationformula?1）Samplingx(n)’sz-transform:Regularintervalsamplingonunitcircle:Lossaftersampling?2023/5/746整理課件Aftersamplinginfrequency-domain,canweacquiresequencerepresentingx(n)by

inversetransformingfromXN(k)?isperiodicalcopiesofx(n),thatissamplinginfrequencydomaincausesperiodicalcopiesofsequenceintime-domain.Ifwewanttorecoverthefinite-lengthsequencex(n)withnolossaftersamplinginfrequencydomain,thenitmustbesatisfied:Suppose:Misnumberofpointsintimedomain;

Nisnumberofpointsinfrequencydomain.Then:NMmustbesatisfiedifwewanttorecoveryx(n)withnolossfrom.(Proofinpage78)=？2023/5/747整理課件2）Interpolationformula2023/5/748整理課件ObjectiveDFTorIDFTcanbeusedtocomputetwosequence’scircularconvolution,andDFT,IDFThavetheirfastalgorithm.Soifwecanbuildtherelationshipbetweentwosequences’circularconvolutionandlinearconvolution,wecanimprovecomputationspeedoflinearconvolutionbyfastFourierTransformalgorithm.2.6Computingsequence’slinearconvolutionwithDFT2023/5/749整理課件CircularConvolutionLinearConvolutionWhatrelationshipbetweenand?2023/5/750整理課件2023/5/751整理課件2023/5/752整理課件ProcessConclusion:WecancomputelinearconvolutionusingcircularconvolutioniflengthofDFTssatisfyx’(n)h’(n)ZeropaddingZeropaddingX(k)H(k)X(k)H(k)x’(n)h’(n)x(n)

h(n)DFTDFTIDFT2023/5/753整理課件AfterFFTalgorithm,overlap-addmethodandover-lapsavemethodwillbelearned.Problems:Inpracticalapplication:y(n)=x(n)*h(n),supposex(n)’slengthisM，h(n)’lengthisN；Usually,M>>N,IfL=N+M-1,then:Forshortsequence:manyzerospaddedintoh(n).Forlongsequence:computeafterallsequenceinput.Difficulties：Largememory,longcomputationtime,soreal-timepropertycannotbesatisfied.Solution:decompositioncomputationonlongsequence.DividedandConquer2023/5/754整理課件SummaryRelationshipbetweenDFT,Sequence‘sFouriertransformandz-transform;Frequencysamplingtheorem;ComputationoflinearconvolutionusingDFT.2023/5/755整理課件2.7SpectrumanalysisusingDFT(1)Approximationprocess.SampleTT1)ProcessofspectrumanalysisusingDFTDFTT(2)Erroranalysis.(3)Importantparameters.Spectrumanalysis

DFTComputationDiscretizationintimeandfrequencydomain

2023/5/756整理課件BasictheoryofFourierTransformFinitedurationsignal→Infinitewidthfrequencyspectrum;Finitewidthfrequencyspectrum→Infinitedurationsignal.Inpractice,finitedurationsignalwithfinitewidthspectrumdoesnotreallyexist.Widebandsignals→Filtering，fc≤fs/2Infinitedurationsignals→ExtractfinitepointsEngineeringapplication：Filterhighfrequencycomponentwithsmallamplitude.Cutawaysignalcomponentwithsmallamplitude.Inbelowsections,allsignalsxa(t)aresupposedtobefinite-length,band-limitedsignalsafterfilteringandextracting.2023/5/757整理課件ProcessofspectrumanalysisusingDFT2）ErrorsofspectrumanalysisusingDFT(3)

FenceeffectSamplingTTTTTConvolution（1）（3）（2）(1)Aliasing(2)Cutoffeffect

Windowing2023/5/758整理課件（1）SamplingTTDFTT2）ErrorsofspectrumanalysisusingDFTProcessofspectrumanalysisusingDFT(1)Aliasing

Ifconditionisnotmet:therewillbespectrumdistortionatfs/2;

Solution:increasefs,orusinganti-aliasingpre-filtering.

Inpracticalapplication,2023/5/759整理課件（2）CutoffeffectofDFT

2）ErrorsofspectrumanalysisusingDFTTTTTTConvolution（1）（2）WindowingProcessofspectrumanalysisusingDFT2023/5/760整理課件CutoffeffectofDFTAmplitudeofsquare-wavefunctions’sspectrumbeforeandafterwindowingbysquare-wavefunction.LeakageDisturbanceSolution:increaseSamplingpointsN,orusingotherkindofwindowfunction.2023/5/761整理課件（3）TTDFTT2）ErrorsofspectrumanalysisusingDFTProcessofspectrumanalysisusingDFT(3)Fenceeffect

N

DFT→NequalintervalsamplingofFT.

Spectrumfunctionvalueisomittedbetweensamplingpoints,Nintervals.Solution:Zeropadding,orchangesequence’slength,increaseN.2023/5/762整理課件RelationshipbetweenDFTandspectrumofcontinuoussignalsSamplingfrequency:fs;Samplingholdtime:Tp;Samplingintervalinfrequencydomain(Spectrumresolution):F;Samplingpoints:NP86:example3.4.1DiscretePeriodicAperiodicContinuous2023/5/763整理課件3）ImportantparameterofDFTSomeimportantconclusion

(2)IfNunchanged,Fincensementcanonlybeacquiredbyloweringfs.Sospectrumanalysisscopewillbesmall.