版《数字信号处理(英)》课件Chap-5-Finite-Length-Discrete-Transforms

Chap5Finite-LengthDiscreteTransforms

1TheDiscreteFourierTransformRelationBetweenDTFTandDFTOperationonFinite-LengthSequencesClassificationofFinite-LengthSequencesDFTSymmetryRelationDiscreteFourierTransformTheoremsComputationoftheDFTofRealSequenceLinearConvolutionUsingtheDFTChap5Finite-LengthDiscrete5.1OrthogonalTransforms21.

Definition------------analysisequation------------synthesisequation------------basissequence,Length-N5.1OrthogonalTransforms21.D5.1OrthogonalTransforms3Condition:2.

Parseval’srelation5.1OrthogonalTransforms3Cond5.2TheDiscreteFourierTransformTimedomainFrequencydomainContinueaperiodicFTAperiodiccontinueContinueperiodicFSAperiodicdiscreteDiscreteaperiodicDTFTPeriodiccontinueDiscreteperiodicDFSPeriodicdiscrete41.

Review5.2TheDiscreteFourierTransTheengineeringsignalsareoftencontinuousandaperiodic.IfwewanttoprocessthesignalswithDFT,wehavetomakethesignalsdiscreteandperiodic.52.Makeasignaldiscreteandperiodic1)Samplingtomakethesignaldiscrete2)Makethesignalperiodic:a)Ifx[n]isalimitedlengthN-pointsequence,seeitasoneperiodofaperiodicsignalthatmeansextendittoaperiodicb)Ifx[n]isaninfinitelengthsequence,cut-offitstailtomakeaN-pointsequence,thendotheperiodicextending.Thetailcutting-offwillintroducedistortion.Wemustdeveloptruncationalgorithmtoreducetheerror,whichiswindowing.Theengineeringsignalsar62.Makeasignaldiscreteandperiodicx(t)x[nT]X(jΩ)FTDFSX(jΩ)DTFTP(t)Ts……q(t)TP(jΩ)ω0Ω

0=2π/TsQ(jΩ)Ω0……Ω0=

2π/T62.Makeasignaldiscreteand5.2.1Definition71.

Definition---------discreteFouriertransformbasissequence---------complexexponentialsequenceSuppose:x[n],X[k]----finite-lengthsequence,N---length;i.e.,x[n]=0whenn<0orn>N-15.2.1Definition71.Definition5.2.1Definition8basissequencehastheorthogonalitypropertyProof:5.2.1Definition8basissequenc5.2.1Definition1)X[k]isalsoalength-Nsequenceinthefrequencydomain2)X[k]iscalledthediscreteFouriertransform(DFT)ofthesequencex[n]3)UsingthenotationWN=e-j2/NtheDFTisusuallyexpressedas:92.

Note5.2.1Definition1)X[k]isals5.2.1Definition1)TheinversediscreteFouriertransform(IDFT)isgivenby103.

IDFT2)Toverifytheaboveexpression,wemultiplybothsidesoftheaboveequationbyWNlnandsumtheresultfromn=0ton=N-15.2.1Definition1)Theinverse5.2.1Definitionresultingin115.2.1Definitionresultingin15.2.1Definition12Makinguseoftheidentity Hence5.2.1Definition12Makinguse5.2.1Definition131)Considerthelength-NsequenceItsN-pointDFTisgivenby4.

Example5.2.1Definition131)Consider5.2.1Definition142)Considerthelength-NsequenceItsN-pointDFTisgivenby4.

Example5.2.1Definition142)Consider5.2.1Definition153)Considerthelength-Nsequencedefinedfor0≤n≤N-14.

ExampleUsingatrigonometricidentitywecanwrite5.2.1Definition153)Consider5.2.1DefinitionTheN-pointDFTofx[n]isthusgivenby164.

ExampleMakinguseoftheidentityraninteger5.2.1DefinitionTheN-pointDF5.2.1Definition174.

Example5.2.1Definition174.Example5.2.2MatrixRelations18whereTheDFTsamplesdefinedby:

canbeexpressedinmatrixformsas:5.2.2MatrixRelations18whereT5.2.2MatrixRelations19DNistheN×NDFTmatrixgivenby5.2.2MatrixRelations19DNis5.2.2MatrixRelations20Likewise,theIDFTcanbeexpressedinmatrixformsas:5.2.2MatrixRelations20Likewi5.2.2MatrixRelations21

istheN×NIDFTmatrixgivenbyNote5.2.2MatrixRelations21i5.3RelationbetweenDTFTandDFTandtheirInverses225.3.1RelationwithDTFT

TheFouriertransformofthelength-Nsequencex[n].

ByuniformlysamplingatNequallyspacedfrequencies5.3RelationbetweenDTFTand235.3.2NumericalComputationofDTFTDefineanewsequencexe[n]Eq.(5.38)usedfunction

freqzcanevaluatethefrequencyresponseofx[n]235.3.2NumericalComputation245.3.3TheDTFTfromDFTbyinterpolation1.show245.3.3TheDTFTfromDFTbyi255.3.3TheDTFTfromDFTbyinterpolation255.3.3TheDTFTfromDFTbyi265.3.3TheDTFTfromDFTbyinterpolationwhere265.3.3TheDTFTfromDFTbyi27

fromX[k]byinterpolation5.3.3TheDTFTfromDFTbyinterpolationResultTheinterpolatingpolynomialsatisfies:27fromX[k]285.3.4SamplingtheDTFT1.Considerasequencex[n]withaDTFT2.WesampleatNequallyspacedpoints developingtheNFrequencysamples3.TheseNfrequencysamplescanbeconsideredasanN-pointDFTY[k]whoseN-pointIDFTisalength-Nsequencey[n].285.3.4SamplingtheDTFT1.Co295.3.4SamplingtheDTFTNowFromEq.(3.12)295.3.4SamplingtheDTFTNowFr305.3.4SamplingtheDTFTMakinguseoftheaboveidentityinEq.(5.48),theny[n]isobtainedbyaddinginfinitenumberofshiftedreplicasofx[n].EachreplicashiftedbyanintegermultipleofNsamplinginstants305.3.4SamplingtheDTFTMakin315.3.4SamplingtheDTFTToapplya)Ifx[n]islength-MsequencewithM≤N,thusy[n]=x[n]for0≤n≤N-1.b)IfM>N,thereisatime-domainaliasingofsamplesofx[n]ingeneratingy[n],andx[n]cannotberecoveredfromy[n].315.3.4SamplingtheDTFTToap325.3.4SamplingtheDTFTExample5.6Give8equallyspacedpoints-------x[n]canberecoveredfromy[n]Give4equallyspacedpoints-------x[n]can’tberecoveredfromy[n]325.3.4SamplingtheDTFTExamp5.4OperationonFinite-LengthSequences335.4.1Circularshiftofasequence1.Considerlength-Nsequencesdefinedfor0≤n≤N-12.Samplevaluesofsuchsequencesareequaltozeroforvaluesofn<0andn≥N5.4OperationonFinite-Length5.4.1Circularshiftofasequence343.Ifx[n]issuchasequence,thenforanyarbitraryintegern0,theshiftedsequencex1[n]=x[n–n0]isnolongerdefinedfortherange0≤n≤N-14.Wethusneedtodefineanothertypeofashiftthatwillalwayskeeptheshiftedsequenceintherange0≤n≤N-15.4.1Circularshiftofasequ5.Thedesiredshift,calledthecircularshift,isdefinedusingamodulooperation:356.Forn0>0(right

circularshift),theaboveequationimplies5.4.1Circularshiftofasequence5.Thedesiredshift,calledt367.Illustrationoftheconceptofacircularshift5.4.1Circularshiftofasequence367.Illustrationoftheconce378.Ascanbeseenfromthepreviousfigure,arightcircularshiftbyn0isequivalenttoaleftcircularshiftbyN-n0sampleperiods9.AcircularshiftbyanintegernumbergreaterthanNisequivalenttoacircularshiftbyn0

N5.4.1Circularshiftofasequence378.Ascanbeseenfromthep38x[n-1]x[n]x[<n-1>N]n=<4>4=05.4.1Circularshiftofasequence38x[n-1]x[n]x[<n-1>N]n=<4>4=053910.circulartime-reversal11.Frequencydomain5.4.1Circularshiftofasequence3910.circulartime-reversal115.4.2Circularconvolution401.Thisoperationisanalogoustolinearconvolution,butwithasubtledifference2.Considertwolength-Nsequences,g[n]andh[n],respectively3.Theirlinearconvolutionresultsinalength-(2N-1)sequenceyL[n]givenby5.4.2Circularconvolution401.414.IncomputingyL[n]wehaveassumedthatbothlength-Nsequenceshavebeenzero-paddedtoextendtheirlengthsto2N-15.ThelongerformofyL[n]resultsfromthetime-reversalofthesequenceh[n]anditslinearshifttotheright6.ThefirstnonzerovalueofyL[n]isyL[0]=g[0]h[0],thelastnonzerovalueisyL[2N-2]=g[N-1]h[N-1]5.4.2Circularconvolution414.IncomputingyL[n]wehav427.

Todevelopaconvolution-likeoperationresultinginalength-NsequenceyC[n],weneedtodefineacirculartime-reversal,andthenapplyacirculartime-shift8.

Resultingoperation,calledacircularconvolution,isdefinedby5.4.2Circularconvolution427.Todevelopaconvolution-43Ny[n]=g[n]h[n]9.

Sincetheoperationdefinedinvolvestwolength-Nsequences,itisoftenreferredtoasanN-pointcircularconvolution,denotedas10.Thecircularconvolutioniscommutative,i.e.NNg[n]h[n]=h[n]g[n]5.4.2Circularconvolution43Ny[n]=g[n]h[n]9.Sinc44----------circulantmatrix5.4.2Circularconvolution44----------circulantmatrix5.45Example5.7-Determinethe4-pointcircularconvolutionofthetwolength-4sequences:nnassketchedbelow5.4.2Circularconvolution45Example5.7-Determinethe446Theresultisalength-4sequenceyC[n]givenbyFromtheaboveweobserve45.4.2Circularconvolution46Theresultisalength-4seq475.4.2Circularconvolution475.4.2Circularconvolution48ThecircularconvolutioncanalsobecomputedusingaDFT-basedapproach(example5.10)5.4.2Circularconvolution48Thecircularconvolutioncan49Othermethod:5.4.2Circularconvolution49Othermethod:5.4.2Circular5.5ClassificationsofFinite-LengthSequences505.5.1ClassificationbasedonconjugateSymmetrySymmetrydefinition:5.5ClassificationsofFinite5.5.1ClassificationbasedonconjugateSymmetry51Ifx[n]isrealsequence----------calledcircularevenpart orcircularevensequence----------calledcircularoddpartorcircularoddsequenceConjugate-symmetrypartisarealsequenceConjugate-antisymmetrypartisarealsequenceDenotexcev[n]Denotexcod[n]5.5.1Classificationbasedon52-------circularconjugate-symmetricsequenceIfx[n]iscomplexsequence-------circularconjugate-antisymmetricsequence5.5.1ClassificationbasedonconjugateSymmetry52-------circularconjugate-sy53Example-Considerthefinitesequenceoflength-5definedfor0≤n≤4Modulo5circularlytime-reversed5.5.1ClassificationbasedonconjugateSymmetry53Example-Considerthefinit545.5.1ClassificationbasedonconjugateSymmetry545.5.1Classificationbasedo555.5.1ClassificationbasedonconjugateSymmetry555.5.1Classificationbasedo5.5.2ClassificationbasedonGeometricSymmetry56-------symmetricsequency-------antisymmetricsequency

SincethelengthNofasequencecanbeeitherevenorodd,fourtypesofgeometricsymmetryaredefined.5.5.2Classificationbasedon5.6DFTSymmetryRelations57Realpart Imaginarypart5.6DFTSymmetryRelations57Re58Finite-lengthComplexSequenceFromtheabove

k=05.6DFTSymmetryRelations58Finite-lengthComplexSequen59

1≤k≤N-1Wethusget:Inasimilar5.6DFTSymmetryRelations591≤k≤N-1Wethusget:Inasim60Inasimilar5.6DFTSymmetryRelations60Inasimilar5.6DFTSymmetry61Table5.1:SymmetrypropertiesoftheDFTofacomplexsequenceLength-NSequence N-pointDFT5.6DFTSymmetryRelations61Table5.1:Symmetryproperti62Finite-lengthRealSequenceTable5.2:SymmetrypropertiesoftheDFTofarealsequenceLength-NSequence N-pointDFTsymmetryrelation62Finite-lengthRealSequenceT5.7DFTTheorems63DFTpairs:1.LinearityTheoremsNote:ifthelengthofeachsequenceis5.7DFTTheorems63DFTpairs:642.CircularTime-ShiftingTheorems642.CircularTime-ShiftingTh5.7DFTTheorems653.DualityTheoremsx[n],N=105.7DFTTheorems653.DualityT5.7DFTTheorems665.CircularConvolutionTheoremsN4.CircularFrequency-ShiftingTheoremsN-pointDFTN-pointDFTN-pointIDFTy[n]g[n]Length-NG[k]H[k]Length-Nh[n]Length-N5.7DFTTheorems665.Circular67Example5.10:

g[n]={1201},h[n]={2211}0n3,Computeyc[n]=g[n]④h[n]UsingDFT(example5.7)

5.7DFTTheorems67Example5.10:g[n]={12685.7DFTTheorems685.7DFTTheorems696.ModulationTheorems7.Parseval’sRelation5.7DFTTheorems696.ModulationTheorems7.Par70TypeofPropertylength-NsequenceN-pointDFT

Parseval’srelationModulationg[n]h[n]G[k]H[k]CircularConvolutionDualityG[n]N[g-kN]Frequency-shiftingWN-k0ng[n]G[k-k0N]CircularTime-shiftingg[n-n0N]WNkn0G[k]Linearityag[n]+bh[n]aG[k]+bH[k]h[n]H[k]g[n]G[k]Table5.35.7DFTTheorems70TypeofPropertylength71Considerthelength-10sequence,defined0n9,

x[n]={2,3,1,4,-3,-1,1,1,0,6}Witha10-pointDFTgivenbyX[k],0k9.EvaluatethefollowingfunctionsofX[k]withoutcomputingtheDFT:Example:X[0],(b)X[5],(c),(d),

(e)

5.7DFTTheorems71Considerthelength-10seque72Answer:(a)(b)5.7DFTTheorems72Answer:(a)(b)5.7DFTTheorem73(c)(d)5.7DFTTheorems73(c)(d)5.7DFTTheorems74(e)Example:g[n]andh[n]denotesafinitelengthrealsequenceoflength---N.y[n]=g[n]+jh[n].ComputingG[k],H[k],g[n]andh[n].5.7DFTTheorems74(e)Example:g[n]andh[n]den75Answer:5.7DFTTheorems75Answer:5.7DFTTheorems765.7DFTTheorems765.7DFTTheoremsWeknow

InasimilarWeknow Inasimilar5.8Fourier-DomainFiltering78TheFourier-domainfilteringisusuallyimplementedusingtheDFT.Inthetimedomain,this

approachisequivalenttothecircuitconvolutionofsignalx[n]andimpulseresponseh[n].Inthefrequencydomain,a

simple

approachtodesignthefilteristosettheFouriertransformH(ejω)tozerointhestopband,tosetH(ejω)equalto1inthepassband.Sincethe

idealfilteringhasaninverseFouriertransformthatisofinfinitelength,samplingtheFouriertransformtocreatetheDFTsamplesleadstothetime-domainaliasing.

Asaresult,theDFT-basedfilteringwillalwaysleadtosomesmallripplesinthefilterresponse.5.8Fourier-DomainFiltering78Example5.12:Considerthenarrow-bandlowpasssignalComputingthe256-pointDFT,thenX(k)=0,50≤k≤206OriginalsignalthenoisecorruptedsignalExample5.12:ConsiderthenaDFTofnoisecorruptedsignalX(k)=0,50≤k≤206thesignalobtainafteraFourier-domainfilteringsmallripplesComputingthe256-pointDFT,thenX(k)=0,50≤k≤206DFTofnoisecorruptedsignalXExample:Considerthenoisecorruptedpianoaudio.TheoriginalcorruptedsequenceThemagnitudespectrumoforiginalsequenceExample:ConsiderthenoisecoExample:Considerthenoisecorruptedpianoaudio.ThemagnitudespectrumofFourier-domainfilteringTheuncorruptedsequenceExample:Considerthenoiseco5.9ComputationoftheDFTofrealsequence835.9.1N-pointDFToftworealsequence

usingasingleN-pointDFTLetg[n]andh[n]betworealsequenceoflengthNFromtable5.1:5.9ComputationoftheDFTof845.9.22N-pointDFTofarealsequence

usingasingleN-pointDFTLetv[n]bearealsequenceoflength2N.845.9.22N-pointDFTofare855.9.22N-pointDFTofarealsequence

usingasingleN-pointDFT855.9.22N-pointDFTofare5.10LinearConvolutionUsingtheDFT861.

Linearconvolutionisakeyoperationinmostsignalprocessingapplications.2.

AnN-pointDFTcanbeimplementedveryefficientlyusingapproximatelyN(log2N)arithmeticoperations.3.

WehopetoinvestigatemethodsforimplementationofthelinearconvolutionusingtheDFT.5.10LinearConvolutionUsing5.10LinearConvolutionUsingtheDFT875.10.1Linearconvolutionoftwofinite-lengthsequence.Considertwosequences:g[n]----Npoints;h[n]----Mpoints;thenthelinearconvolutionofthetwosequencesareyL[n]DenotethelengthofthesequencesyL[n]whereL=M+N-1Definetwolength-Lsequence5.10LinearConvolutionUsing885.10.1Linearconvolutionoftwofinite-lengthsequence.L≥N＋M－1Note:L=2v(visinteger)885.10.1Linearconvolutionof89supposeg[n]=

h[n]=u[n]-u[n-6](1)Computeg[n]⑥h[n](2)Computeg[n]h[n]120g[n]=

h[n]1N=6y[n-N]N=60010y[n]=g[n]h[n]Example:89supposeg[n]=h[n]=u[n]-u[0-N=-6y[n+N]N=6N=6y[n-N]N=60010y[n]=g[n]h[n]N–1=50g[n]

h[n]N=6Ng[n]⑥h[n]0-N=-6y[n+N]N=6y[n-N]0010y[nN=12y[n-N]N=120g[n]

h[n]N=12NN-1=11=g[n]h[n]0g[n]

h[n]N=12NN-1=11=g[n]h[n]12g[n]h[n]N=12y[n-N]0g[n]h[n]NN-1=925.10.2Linearconvolutionofafinite-lengthsequencewithaninfinitesequence.Suppose:h[n]----Mpoints; x[n]----infinitepoint,causalsequence.Overlap-AddMethod:where925.10.2Linearconvolutionof935.10.2Linearconvolutionofafinite-lengthsequencewithaninfinitesequence.whereym[n]=xm[n]h[n]935.10.2Linearconvolutionof945.10.2Linearconvolutionofafinite-lengthsequencewithaninfinitesequence.0nN2N3N4Nx[n]Nn0N+M-2x0[n]n0NN+M-2x1[n]n0NN+M-2x2[n]945.10.2Linearconvolutionof955.10.2Linearconvolutionofafinite-lengthsequencewithaninfinitesequence.overlap-savemethod(ignored)Nn0N+M-2y0[n]N+M-2n0Ny1[n]n0Ny2[n]N+M-2955.10.2Linearconvolutionof96Exercises5.25.8(a)85.345.355.395.435.45(a)(b)5.485.495.5496Exercises5.25.8(a)5.10Chap5Finite-LengthDiscreteTransforms

97TheDiscreteFourierTransformRelationBetweenDTFTandDFTOperationonFinite-LengthSequencesClassificationofFinite-LengthSequencesDFTSymmetryRelationDiscreteFourierTransformTheoremsComputationoftheDFTofRealSequenceLinearConvolutionUsingtheDFTChap5Finite-LengthDiscrete5.1OrthogonalTransforms981.

Definition------------analysisequation------------synthesisequation------------basissequence,Length-N5.1OrthogonalTransforms21.D5.1OrthogonalTransforms99Condition:2.

Parseval’srelation5.1OrthogonalTransforms3Cond5.2TheDiscreteFourierTransformTimedomainFrequencydomainContinueaperiodicFTAperiodiccontinueContinueperiodicFSAperiodicdiscreteDiscreteaperiodicDTFTPeriodiccontinueDiscreteperiodicDFSPeriodicdiscrete1001.

Review5.2TheDiscreteFourierTransTheengineeringsignalsareoftencontinuousandaperiodic.IfwewanttoprocessthesignalswithDFT,wehavetomakethesignalsdiscreteandperiodic.1012.Makeasignaldiscreteandperiodic1)Samplingtomakethesignaldiscrete2)Makethesignalperiodic:a)Ifx[n]isalimitedlengthN-pointsequence,seeitasoneperiodofaperiodicsignalthatmeansextendittoaperiodicb)Ifx[n]isaninfinitelengthsequence,cut-offitstailtomakeaN-pointsequence,thendotheperiodicextending.Thetailcutting-offwillintroducedistortion.Wemustdeveloptruncationalgorithmtoreducetheerror,whichiswindowing.Theengineeringsignalsar1022.Makeasignaldiscreteandperiodicx(t)x[nT]X(jΩ)FTDFSX(jΩ)DTFTP(t)Ts……q(t)TP(jΩ)ω0Ω

0=2π/TsQ(jΩ)Ω0……Ω0=

2π/T62.Makeasignaldiscreteand5.2.1Definition1031.

Definition---------discreteFouriertransformbasissequence---------complexexponentialsequenceSuppose:x[n],X[k]----finite-lengthsequence,N---length;i.e.,x[n]=0whenn<0orn>N-15.2.1Definition71.Definition5.2.1Definition104basissequencehastheorthogonalitypropertyProof:5.2.1Definition8basissequenc5.2.1Definition1)X[k]isalsoalength-Nsequenceinthefrequencydomain2)X[k]iscalledthediscreteFouriertransform(DFT)ofthesequencex[n]3)UsingthenotationWN=e-j2/NtheDFTisusuallyexpressedas:1052.

Note5.2.1Definition1)X[k]isals5.2.1Definition1)TheinversediscreteFouriertransform(IDFT)isgivenby1063.

IDFT2)Toverifytheaboveexpression,wemultiplybothsidesoftheaboveequationbyWNlnandsumtheresultfromn=0ton=N-15.2.1Definition1)Theinverse5.2.1Definitionresultingin1075.2.1Definitionresultingin15.2.1Definition108Makinguseoftheidentity Hence5.2.1Definition12Makinguse5.2.1Definition1091)Considerthelength-NsequenceItsN-pointDFTisgivenby4.

Example5.2.1Definition131)Consider5.2.1Definition1102)Considerthelength-NsequenceItsN-pointDFTisgivenby4.

Example5.2.1Definition142)Consider5.2.1Definition1113)Considerthelength-Nsequencedefinedfor0≤n≤N-14.

ExampleUsingatrigonometricidentitywecanwrite5.2.1Definition153)Consider5.2.1DefinitionTheN-pointDFTofx[n]isthusgivenby1124.

ExampleMakinguseoftheidentityraninteger5.2.1DefinitionTheN-pointDF5.2.1Definition1134.

Example5.2.1Definition174.Example5.2.2MatrixRelations114whereTheDFTsamplesdefinedby:

canbeexpressedinmatrixformsas:5.2.2MatrixRelations18whereT5.2.2MatrixRelations115DNistheN×NDFTmatrixgivenby5.2.2MatrixRelations19DNis5.2.2MatrixRelations116Likewise,theIDFTcanbeexpressedinmatrixformsas:5.2.2MatrixRelations20Likewi5.2.2MatrixRelations117

istheN×NIDFTmatrixgivenbyNote5.2.2MatrixRelations21i5.3RelationbetweenDTFTandDFTandtheirInverses1185.3.1RelationwithDTFT

TheFouriertransformofthelength-Nsequencex[n].

ByuniformlysamplingatNequallyspacedfrequencies5.3RelationbetweenDTFTand1195.3.2NumericalComputationofDTFTDefineanewsequencexe[n]Eq.(5.38)usedfunction

freqzcanevaluatethefrequencyresponseofx[n]235.3.2NumericalComputation1205.3.3TheDTFTfromDFTbyinterpolation1.show245.3.3TheDTFTfromDFTbyi1215.3.3TheDTFTfromDFTbyinterpolation255.3.3TheDTFTfromDFTbyi1225.3.3TheDTFTfromDFTbyinterpolationwhere265.3.3TheDTFTfromDFTbyi123

fromX[k]byinterpolation5.3.3TheDTFTfromDFTbyinterpolationResultTheinterpolatingpolynomialsatisfies:27fromX[k]1245.3.4SamplingtheDTFT1.Considerasequencex[n]withaDTFT2.WesampleatNequallyspacedpoints developingtheNFrequencysamples3.TheseNfrequencysamplescanbeconsideredasanN-pointDFTY[k]whoseN-pointIDFTisalength-Nsequencey[n].285.3.4SamplingtheDTFT1.Co1255.3.4SamplingtheDTFTNowFromEq.(3.12)295.3.4SamplingtheDTFTNowFr1265.3.4SamplingtheDTFTMakinguseoftheaboveidentityinEq.(5.48),theny[n]isobtainedbyaddinginfinitenumberofshiftedreplicasofx[n].EachreplicashiftedbyanintegermultipleofNsamplinginstants305.3.4SamplingtheDTFTMakin1275.3.4SamplingtheDTFTToapplya)Ifx[n]islength-MsequencewithM≤N,thusy[n]=x[n]for0≤n≤N-1.b)IfM>N,thereisatime-domainaliasingofsamplesofx[n]ingeneratingy[n],andx[n]cannotberecoveredfromy[n].315.3.4SamplingtheDTFTToap1285.3.4SamplingtheDTFTExample5.6Give8equallyspacedpoints-------x[n]canberecoveredfromy[n]Give4equallyspacedpoints-------x[n]can’tberecoveredfromy[n]325.3.4SamplingtheDTFTExamp5.4OperationonFinite-LengthSequences1295.4.1Circularshiftofasequence1.Considerlength-Nsequencesdefinedfor0≤n≤N-12.Samplevaluesofsuchsequencesareequaltozeroforvaluesofn<0andn≥N5.4OperationonFinite-Length5.4.1Circularshiftofasequence1303.Ifx[n]issuchasequence,thenforanyarbitraryintegern0,theshiftedsequencex1[n]=x[n–n0]isnolongerdefinedfortherange0≤n≤N-14.Wethusneedtodefineanothertypeofashiftthatwillalwayskeeptheshiftedsequenceintherange0≤n≤N-15.4.1Circularshiftofasequ5.Thedesiredshift,calledthecircularshift,isdefinedusingamodulooperation:1316.Forn0>0(right

circularshift),theaboveequationimplies5.4.1Circularshiftofasequence5.Thedesiredshift,calledt1327.Illustrationoftheconceptofacircularshift5.4.1Circularshiftofasequence367.Illustrationoftheconce1338.Ascanbeseenfromthepreviousfigure,arightcircularshiftbyn0isequivalenttoaleftcircularshiftbyN-n0sampleperiods9.AcircularshiftbyanintegernumbergreaterthanNisequivalenttoacircularshiftbyn0

N5.4.1Circularshiftofasequence378.Ascanbeseenfromthep134x[n-1]x[n]x[<n-1>N]n=<4>4=05.4.1Circularshiftofasequence38x[n-1]x[n]x[<n-1>N]n=<4>4=0513510.circulartime-reversal11.Frequencydomain5.4.1Circularshiftofasequence3910.circulartime-reversal115.4.2Circularconvolution1361.Thisoperationisanalogoustolinearconvolution,butwithasubtledifference2.Considertwolength-Nsequences,g[n]andh[n],respectively3.Theirlinearconvolutionresultsinalength-(2N-1)sequenceyL[n]givenby5.4.2Circularconvolution401.1374.IncomputingyL[n]wehaveassumedthatbothlength-Nsequenceshavebeenzero-paddedtoextendtheirlengthsto2N-15.ThelongerformofyL[n]resultsfromthetime-reversalofthesequenceh[n]anditslinearshifttotheright6.ThefirstnonzerovalueofyL[n]isyL[0]=g[0]h[0],thelastnonzerovalueisyL[2N-2]=g[N-1]h[N-1]5.4.2Circularconvolution414.IncomputingyL[n]wehav1387.

Todevelopaconvolution-likeoperationresultinginalength-NsequenceyC[n],weneedtodefineacirculartime-reversal,andthenapplyacirculartime-shift8.

Resultingoperation,calledacircularconvolution,isdefinedby5.4.2Circularconvolution427.Todevelopaconvolution-139Ny[n]=g[n]h[n]9.

Sincetheoperationdefinedinvolvestwolength-Nsequences,itisoftenreferredtoasanN-pointcircularconvolution,denotedas10.Thecircularconvolutioniscommutative,i.e.NNg[n]h[n]=h[n]g[n]5.4.2Circularconvolution43Ny[n]=g[n]h[n]