一天征服傅里葉變換+英文版

天征服傅里葉變換［英］作者：StephanM.Bernsee轉(zhuǎn)貼自:internet點(diǎn)擊數(shù)：169您要打印的文件是：一天征服傅里葉變換［英］TheDFTaPied:MasteringTheFourierTransforminOneDaybyStephanM.Bernsee,,.1999allrightsreserved*Ifyou'reintosignalprocessing,youwillnodoubtsaythattheheadlineisaverytallclaim.youcan'tlearnallthebellsandwhistlesoftheFouriertransforminonedaywithoutpractisingllydelvingintothemaths.However,thisonlinecoursewillprovideyouwiththebasicknowledgeformworks,whyitworksandwhyitcanbeverysimpletocomprehendwhenwe'reusingproach.Theimportantpart:youwilllearnthebasicsoftheFouriertransformcompletelywithoutondaddingandmultiplyingnumbers!IwilltrytoexplaintheFouriertransforminitspracticalprocessinginnomorethansixparagraphsbelow.Step1:SomesimpleprerequisitesWhatyouneedtounderstandthefollowingparagraphsareessentiallyfourthings:howtoanddividethemandwhatasine,acosineandasinusoidisandhowtheylook.Obviously,ndjustexplainabitthelastone.Youprobablyrememberfromyourdaysatschoolthe'trigonometricresomehowmysteriouslyusedinconjunctionwithtrianglestocalculatethelengthofitssidesiceversa.Wedon'tneedallthesethingshere,wejustneedtoknowhowthetwomostimportants,thesineandcosinelooklike.Thisisquitesimple:theylooklikeverysimplewaveswithstretchouttoinfinitytotheleftandtherightoftheobserver.Asyoucansee,bothwavesareperiodic,whichmeansthatafteracertaintime,theo,bothwaveslookalike,butthecosinewaveappearstostartatitsmaximum,whilethesinepractice,howcanwetellwhetherawaveweobserveatagiventimestartedoutatitsmaximum,on:wecan't.There'snowaytodiscernasinewaveandacosinewaveinpractice,thuswesineorcosinewaveasinusoid,whichisGreekandtranslatestosinus-like.Animportantpropertyy,whichtellsushowmanypeaksandvalleyswecancountinagivenperiodoftime.HighThesinewaveThecosinewave一天征服傅里葉變換［英］頁(yè)碼，1/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionandvalleys,lowfrequencymeansfewpeaksandvalleys:Step2:UnderstandingtheFourierTheoremJean-BaptisteJosephFourierwasoneofthosechildrenparentsareeitherproudorashamedghlycomplicatedmathematicaltermsatthemattheageoffourteen.Althoughhedidalotifetime,theprobablymostsignificantthinghediscoveredhadtodowiththeconductionofwithanequationthatdescribedhowtheheatwouldtravelinacertainmedium,andsolvedseriesoftrigonometricfunctions(thesinesandcosineswehavediscussedabove).Basically,atFourierdiscoveredboilsdowntothegeneralrulethateverysignal,howevercomplex,cansinusoidfunctionsthatareindividuallymixed.Anexampleofthis:Whatyouseehereisouroriginalsignal,andhowitcanbeapproximatedbyamixtureofs)thataremixedtogetherinacertainrelationship(a'recipe').Wewilltalkaboutthatrecipemoresinesweusethemoreaccuratelydoestheresultresembleouroriginalwaveform.Inarecontinuous,ie.youcanmeasurethemininfinitelysmallintervalsatanaccuracythatismentequipment,youwouldneedinfinitelymanysinestoperfectlybuildanygivensignal.otlivinginsuchaworld.Rather,wearedealingwithsamplesofsuch'realworld'signalsthatervalsandonlywithfiniteprecision.Thus,wedon'tneedinfinitelymanysines,wejustneedthat'howmuchisalot'lateron.Forthemoment,itisimportantthatyoucanimaginethatrcomputercanbeputtogetherfromsimplesinewaves,aftersomecookingrecipe.Step3:HowmuchisalotLowfrequencysinusoidMiddlefrequencysinusoidHighfrequencysinusoidThisisouroriginalOnesineTwosinesFoursinesSevensinesFourteensines一天征服傅里葉變換［英］頁(yè)碼，2/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionAswehaveseen,complexshapedwaveformscanbebuilt什omamixtureofsinewaves.Wemareneededtobuildanygivensignalonourcomputer.Well,ofcourse,thismaybeasfewvidedweknowhowthesignalwearedealingwithismadeup.Inmostcases,wearedealingmighthaveaverycomplexstructure,sowedonotknowinadvancehowmany'partial'wavesInthiscase,itisveryreassuringtoknowthatifwedon'tknowhowmanysinewavesconstituteisanupperlimittohowmanywewillneed.Still,thisleavesuswiththequestionofhowmanyytoapproachthisintuitively:assumewehave1000samplesofasignal.Thesinewavewithmostpeaksandvalleysinit)thatcanbepresenthasalternatingpeaksandvalleysforeverywiththehighestfrequencyhas500peaksand500valleysinour1000samples,witheveryheblackdotsinthefollowingdiagramdenoteoursamples,sothesinewavewiththehighestNowlet'slookhowlowthelowestfrequencysinewavecanbe.Ifwearegivenonlyonesinglewebeabletomeasurepeaksandvalleysofasinewavethatgoesthroughthispoint?Wewavesofdifferentperiodsthatgothroughthispoint.So,asingledatapointisnotenoughtotellusanythingaboutfrequency.Now,ifweweredbethelowestfrequencysinewavethatgoesthroughthesetwopoints?Inthiscase,itisrylowfrequencysinewavethatgoesthroughthetwopoints.Itlookslikethis:Imaginethetwoleftmostpointsbeingtwonailswithastringspannedbetweenthem(thentsasthesinewaveisperiodic,butwereallyonlyneedtheleftmosttwototellitsfrequency).canseeisthestringswingingbackandforthbetweenthetwonails,likeoursinewavedoestwopointstotheleft.Ifwehave1000samples,thetwo'nails'wouldbethefirstandthelastThehighestfrequencysinewaveManysinewavesgothroughonesinglepoint,soonepointdoesn'ttellusaboutfrequencyThelowestfrequencysinewave一天征服傅里葉變換［英］頁(yè)碼，3/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversion1andsamplenumber1000.Weknowfromourexperiencewithmusicalinstrumentsthatdownwhenitslengthincreases.Sowewouldexpectthatourlowestsinewavegetslowerurnailsfartheraway什omeachother.Ifwechoose2000samples,forinstance,thelowestsinceour'nails'arenowsamplenumber1andsamplenumber2000.Infact,itwillbetwiceowtwiceasfarawayasinthe1000samples.Thus,ifwehavemoresamples,wecandiscernencysincetheirzerocrossings(our'nails')willmovefartheraway.Thisisveryimportantexplanations.Aswecanalsosee,aftertwo'nails'ourwavestartstorepeatwiththeascendingslope(theentical).Thismeansthatanytwoadjacentnailsembraceexactlyonehalfofthecompletetheronepeakoronevalley,or1/2period.Summarizingwhatwehavejustlearned,weseethattheupperfrequencyofasampledsinebeingapeakandavalleyandthe/owe廠frequencyboundishalfaperiodofthesinewaveberofsampleswearelookingat.Butwait-wouldn'tthismeanthatwhiletheupperfrequencyfrequencywoulddropwhenwehavemoresamples?Exactly!Theresultofthisisthatwewillnwewanttoputtogetherlongersignalsofunknowncontent,sincewestartoutatalowerAllwellandgood,butstillwedon'tknowhowmanyofthesesinewaveswefinallyneed.Asupperfrequencyanypartialsinewavecanhave,wecancalculatehowmanyofthemfitinewehavenailedourlowestpartialsinewavedowntotheleftmostandrightmostsamples,wavesusethesenailsaswell(whyshouldwetreatthemdifferently?Allsinewavesarecreatedsinewaveswerestringsonaguitarattachedtotwofixedpoints.Theycanonlyswingbetweenbreak),justlikeoursinewavesbelow.Thisleadstotherelationshipthatourlowestpartialsecondpartial(2)fitsinwith1period,thethirdpartial(3)fitsinwith11/2okingat.Graphically,thislookslikethis:Nowifwecounthowmanysinewavesfitinour1000samplesthatway,wewillfindthatweesaddedtogethertorepresentthe1000samples.Infact,wewillalwaysfindthatweneeddsamples.Thefirst4partialsinewaves(clicktoenlarge)一天征服傅里葉變換［英］頁(yè)碼，4/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionStep4:AboutcookingrecipesInthepreviousparagraphwehaveseenthatanygivensignalonacomputercanbebuiltWehaveconsideredtheirfrequencyandwhatfrequencythelowestandhighestsinewavesonstructanysignalweanalyze.Wehaveseenthatthenumberofsampleswearelookingthelowestpartialsinewavethatisneeded,butwehavenotyetdiscussedhowtheactualoyieldacertainresult.Tomakeupanygivensignalbyaddingsinewaves,weneedtomeasurethem.Asamatteroffact,frequencyisnottheonlythingweneedtoknow.Wealsoneednewaves,ie.howmuchofeachsinewaveweneedtomixtogethertoreproduceourinputeightofthepeaksofasinewave,ie.thedistancebetweenthepeakandourzeroline.Thederitwillsoundwhenwelistentoit.So,ifyouhaveasignalthathaslotsofbassinityouemustbeagreaterportionoflowerfrequencysinewavesinthemixthantherearehighernerally,thelowfrequencysinewavesinabassysoundwillhaveahigheramplitudethantheInouranalysis,wewillneedtodeterminetheamplitudeofeachpartialsinewavetocompleteStep5:AboutapplesandorangesIfyouarestillwithme,wehavealmostcompletedourjourneytowardstheFouriertransform.ysinewavesweneed,thatthisnumberdependsonthenumberofsampleswearelookingupperfrequencyboundaryandthatwesomehowneedtodeterminetheamplitudeofthepleteourrecipe.We'restillnotclear,however,onhowwecandeterminetheactualrecipewewouldsaythatwecouldfindtheamplitudesofthesinewavessomehowbycomparingytothesampleswehavemeasuredandfindouthow'equal'theyare.Iftheyareexactlyavemustbepresentatthesameamplitude,ifwefindoursignaltonotmatchourreferencexpectthisfrequencynottobepresent.Still,howcouldweeffectivelycompareaknownsineal?Fortunately,DSPershavealreadyfiguredouthowtodothisforyou.Infact,thisisasnumbers-wetakethe'reference'sinewaveofknownfrequencyandunitamplitude(thistudeof1,whichisexactlywhatwegetbackfromtheSin()functiononourpocketcalculatoryitwithoursignalsamples.Afteraddingtheresultofthemultiplicationtogether,wewilltialsinewaveatthefrequencywearelookingat.Toillustratethis,here'sasimpleCcodeListing1.1:ThedirectrealizationoftheDiscreteSineTransform(DST):#defineM_PI3.14159265358979323846longbin,k;doublearg;for(bin=0;bin<transformLength;bin++)(transformData[bin]=0.;for(k=0;k<transformLength;k++)(arg=(float)bin*M_PI*(float)k/(float)transformLength;transformData[bin]+=inputData[k]*sin(arg);一天征服傅里葉變換[英]頁(yè)碼，5/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionThiscodesegmenttransformsourmeasuredsamplepointsthatareStoredininputData[0...transformLengthamplitudesofitspartialsinewavestransformData[0...transformLength-1]-Accordingtocommonterminology,ncystepsofourreferencesinewavebins,whichmeansthattheycanbethoughtofasbeingtheamplitudeofanyofthepartialwavesweevaluate.TheDiscreteSineTransform(DST)sumeswehavenoideawhatoursignallookslike,otherwisewecoulduseamoreefficientmplitudesofthepartialsinewaves(ifwe,forexample,knowbeforehandthatoursignalisequencywecoulddirectlycheckforitsamplitudewithoutcalculatingthewholerangeofsinehfordoingthisbasedontheFouriertheorycanbefoundintheliteratureunderthenameForthoseofyouwhoinsistonanexplanationforwhywecalculatethesinetransformthatachtowhywemultiplywithasinewaveofknownfrequency,imaginethatthiscorrespondsalworldhappenswhena'resonance'atagivenfrequencytakesplaceinasystem.Theatorthatgetsexcitedbyourinputwaveform.Iftheinputhasapartialatthefrequencywe'reetheamplitudeoftheresonancewiththereferencesinewave.Sinceourreferencewaveisadirectmeasureoftheactualamplitudeofthepartialatthatfrequency.Sincearesonatorr,thetransformcan(admittedlyundersomewhatrelaxedconditions)beseenasahavingnarrowbandpassfiltersthatarecenteredaroundthefrequencieswe'reevaluating.ThishelpseFouriertransformprovidesanefficienttoolforperformingfilteringofsignals.Justforthesakeofcompleteness:ofcourse,theaboveroutineisinvertible,oursignalcanricalprecision)beperfectlyreconstructedwhenweknowitspartialsinewaves,bysimplyisisleftasanexercisetothereader.ThesameroutinecanbechangedtoworkwithcosineesimplyneedtochangetheSin(arg)termtoCos(arg)toobtainthedirectrealizationoftheDiscreteT).Now,aswehavediscussedintheveryfirstparagraphofthisarticle,inpracticewehavenoinus-likefunctionassinewaveorcosinewave.Insteadwearealwaysmeasuringransformareofnogreatusewhenweareapplyingtheminpractice,exceptforsomespecialionwhereeachimagemighthavefeaturesthatarewellmodelledbyacosineorsinebasisofthesamecolorthatarewellrepresentedbythecosinebasisfunction).Asinusoidisabitrcosinewaveinthatitcanstartatanarbitrarypositioninitsperiod.Werememberthattheatzero,whilethecosinewavestartsoutatone.Whenwetakethesinewaveasreference,1/4thlaterinitsperiod.Itiscommontomeasurethisoffsetindegreeorradiansconjunctionwithtrigonometricfunctions.Onecompleteperiodequals360°(pron.degree)hpipronouncedlikethewordpie.isaGreeksymbolforthenumber3.14159265358979323846...nificanceintrigonometry).Thecosinewavethushasanoffsetof90Tor/2.Thisoffsetisd,solookingatourcosinewaveweseethatitisasinusoidwithaphaseoffsetof90Sowhat'sthisphasebusinessallabout.Aswecan'trestrictoursignaltostartoutatzeroe(sincewearejustobservingasignalwhichmightbebeyondourcontrol)itisofinterest}}一天征服傅里葉變換［英］頁(yè)碼，6/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionplitudeandphasetouniquelydescribeitatanyonetimeinstant.Withthesineorcosinetransform,erophaseor90°phaseandanysinusoidthathasanarbitraryphasewillcauseadjacenteaks(sincetheytryto'help'theanalysistoforce-fitthemeasuredsignaltoasumofzeroabitliketryingtofitaroundstoneintoasquarehole:youneedsmallerroundstonestofilldevenmoreevensmallerstonestofilloutthespacethatisstillleftempty,andsoon.Sohatisgeneralinthatitcandealwithsignalsthatarebuiltofsinusoidsofarbitraryphase.Step6:TheDiscreteFouriertransform.ThestepfromthesinetransformtotheFouriertransformissimple,makingitinawaymoreenusingasinewaveforeachfrequencywemeasureinthesinetransform,weusebothaFouriertransform.Thatis,foranyfrequencywearelookingatwe'compare'(or'resonate')hacosineandasinewaveofthesamefrequency.Ifoursignallooksmuchlikeasinewave,formwillhavealargeamplitude.Ifitlookslikeacosinewave,thecosinepartofourtransformde.Ifitlooksliketheoppositeofasinewave,thatis,itstartsoutatzerobutdropstoeportionwillhavealargenegativeamplitude.Itcanbeshownthatthe+and-signhasecanrepresentanysinusoidatthegivenfrequency?.We'restillleftwiththeproblemofhowtogetsomethingusefuloutoftheFourierTransform.efitoftheFouriertransformovertheSineandCosinetransformisthatweareworkingwithn'tseeanysinusoidsyet,therearestillonlysinesandcosines.Well,thisrequiresanadditionalListing1.2:ThedirectrealizationoftheDiscreteFourierTransform#defineM_PI3.14159265358979323846longbin,k;doublearg,sign=-1.;/*sign=-1->FFT,1->iFFT*/for(bin=0;bin<=transformLength/2;bin++)(cosPart[bin]=(sinPart[bin]=0.);for(k=0;k<transformLength;k++)(arg=2.*(float)bin*M_PI*(float)k/(float)transformLength;sinPart[bin]+=inputData[k]*sign*sin(arg);cosPart[bin]+=inputData[k]*cos(arg);}}一天征服傅里葉變換[英]頁(yè)碼，7/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionAfterrunningthecodefragmentshowninListing1.3onourDFToutput,weendupwithanalasasumofsinusoidwaves.Thek-thsinusoidisdescribedbyfrequency[k]，magnitude[k]periodsperseconds),dB(Decibel)and°(Degree).Pleasenotethatafterthepoststhesineandcosinepartsintoasinglesinusoid,wenametheamplitudeofthekitwillnowalwaysbeapositivevalue.Wecouldsaythatanamplitudeof-1.0correspondshaseofeither+or-180°.Intheliterature,thearraymagnitude[]iscalledtheMagnitudeSpectruml,thearrayphase[]iscalledthePhaseSpectrumofthemeasuredsignalatthetimewhereAsareferenceformeasuringthebinmagnitudeindecibels,ourinputwaveisexpectedtoge[-1.0,1.0),whichcorrespondstoamagnitudeof0dBdigitalfullscale(DFS).Asaninterestinglisting1.3can,forexample,beusedtowriteaspectrumanalyzerbasedontheDiscreteFourierConclusionAswehaveseen,theFouriertransformandits'relatives',thediscretesineandcosinetransformdecomposeasignalintoabunchofpartialwaves.Theseareeithersineorcosinewaves,ormbinationofsineandcosinewaves).Theadvantageofusingboththesineandcosinewavertransformisthatwearethusabletointroducetheconceptofphasewhichmakesthetransformecanuseittoefficientlyandclearlyanalyzesinusoidsthatareneitherapuresineorcosinegnalsaswell.TheFouriertransformisindependentofthesignalunderexaminationinthatitrequirestheomatterifthesignalweareanalyzingisonesinglesinusoidorsomethingelsemorecomplicated.theDiscreteFouriertransformiscalledanonparametrictransform,meaningthatitisnotgent'analysisofasignalisneeded(inthecasewhereweareexaminingasignalthatweknoweferjustgettinginformationaboutitsphase,frequencyandmagnitudeinsteadofabunchListing1.3:Gettingsinusoidfrequency,magnitudeandphase什omtheDiscreteFourier#defineM_PI3.14159265358979323846longbin;for(bin=0;bin<=transformLength/2;bin++)(/*frequency*/frequency[bin]=(float)bin*sampleRate/(float)transformLength;/*magnitude*/magnitude[bin]=20.*log10(2.*sqrt(sinPart[bin]*sinPart[bin]+cosPart[bin]*cosPart[bin])//*phase*/phase[bin]=180.*atan2(sinPart[bin],cosPart[bin])/M_PI-90.;}一天征服傅里葉變換[英]頁(yè)碼，8/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversionmepredefinedfrequencies).Wenowalsoknowthatweareevaluatingourinputsignalatafixedfrequencygrid(ourdowiththeactualfrequenciespresentinourinputsignal.Sincewechooseourreferencesineaccordingtotastewithregardtotheirfrequency,thegridweimposeonouranalysisisartificial.mediatelyclearthatonewilleasilyencounterascenariowherethemeasuredsignal'sfrequenciesenthefrequenciesofourtransformbins.Consequently,asinusoidthathasafrequencythatfrequency'bins'willnotbewellrepresentedinourtransform.Adjacentbinsthatsurroundourinputwavewilltryto'correct'thedeviationinfrequencyandthustheenergyoftheinputseveralneighbouringbins.ThisisalsothemainreasonwhytheFouriertransformwillnotrnwithitsfundamentalandharmonics(andthisisalsowhywecallthesineandcosinewavess,orovertones).Simplyspeaking,withoutfurtherpost-processing,theDFTislittlemorethanabankofnarrow,passfilters('channels')withadditionalphaseinformationforeachchannel.Itisusefulforgandapplyingsomeotherneattricks(changingthepitchofasignalwithoutchangingitsinadifferentarticleonDSP),butitrequiresadditionalpostprocessingforbeseenasaspecialcaseofafamilyoftransformsthatusebasisfunctionsotherthantheingtheconceptinthisdirectionisbeyondthescopeofthisarticle.Finally,itisimportanttomentionthatthereisamoreefficientimplementationoftheDFT,eFastFourierTransform(FFT)whichwasoriginallyconceivedbyCooleyandTukeyin1969theworkofGaussandothers).TheFFTisjustanefficientalgorithmthatcalculatestheDFTforwardapproachgivenabove,itisotherwiseidenticalwithregardtoitsresults.However,ementedintheCooley/Tukeyalgorithmitrequiresthatthetransformlengthbeapoweroftableconstraintformostapplications.TheavailableliteratureondifferentFFTimplementationsythattherearemanydifferentFFTimplementations,someofwhichdonothavethepowericalFFT.AnimplementationoftheFFTisgivenbytheroutin§mbFft()inListing1.4below.Listing1.4:TheDiscreteFastFourierTransform(FFT):#defineM_PI3.14159265358979323846voidsmbFft(float*fftBuffer,longfftFrameSize,longsign)/*FFTroutine,(C)1996S.M.Bernsee.Sign=-1isFFT,1isiFFT(inverse)FillsfftBuffer[0...2*fftFrameSize-1]withtheFouriertransformofthetimedomaindatainfftBuffer[0...2*fftFrameSize-1].TheFFTarraytakesandreturnsthecosineandsinepartsinaninterleavedmanner,ie.fftBuffer[0]=cosPart[0],fftBuffer[1]=sinPart[0],asf.fftFrameSizemustbeapowerof2.Itexpectsacomplexinputsignal(seefootnote2),ie.whenworkingwith'common'audiosignalsourinputsignalhastobepassedas{in[0],0.,in一天征服傅里葉變換[英]頁(yè)碼，9/11/Article_Print.asp?ArticleID=6192004-10-18PDFcreatedwithpdfFactorytrialversion[1],0.,in[2],0.,...}asf.Inthatcase,thetransformofthefrequenciesofinterestisinfftBuffer[0...fftFrameSize].*/{floatwr,wi,arg,*p1,*p2,temp;floattr,ti,ur,ui,*p1r,*p1i,*p2r,*p2i;longi,bitm,j,le,le2,k;for(i=2;i<2*f