29/02/2016

www.embedded.com/print/4006427

ADSPalgorithmforfrequencyanalysis
SimonSirinJanuary15,2004
TheChirpZTransform(CZT),alittleknownspectrumanalysisalgorithm,offersengineers
ahighresolutionFFTcombinedwiththeabilitytospecifybandwidth.Here'salookathow
CZTworksandwhatithastooffer.
EngineersworkinginthefieldofdigitalsignalprocessingoftenusethefastFouriertransform
(FFT)algorithmtodetecttones,frequencies,signatures,andotherevents.Inspecificsituations,
however,otheralgorithmsmayactuallyworkbetterthantheFFT.Knowingwhentousewhat
algorithmcanhelpyouimprovethesystemyou'reworkingon.
Forinstance,todetectspecificfrequencieswhenyou'relookingfortonesfromtelephonesorto
detect60Hznoiseonpowerlines,theGoertzelalgorithm("TheGoertzelAlgorithm,"byKevin
Banks,EmbeddedSystemsProgramming,Sept2002,p.34)findsspecificfrequenciesfasterthan
theFFT.
Foranalyzingarangeoffrequencies,suchasrecordingfrequencyresponsemeasurements,
matchingvoicepatterns,ordisplayingspectruminformationonthefaceofanamateurradio,
whatalgorithmworksbest?AlthoughmostengineerswouldusetheFFT,another,lesserknown
algorithmgivesyouadditionalflexibilitytospecifybothspectralanalysisbandwidthandthe
resolutionwithinthatbandwidthandprovidesrealandimaginaryoutputsfromwhichyoucan
computespectralmagnitudeandphase.Inthisarticle,I'llintroduceyoutothatalgorithm,known
astheChirpZtransform(CZT),andwe'llcompareittothebetterknownGoertzelandFFT.

ChirpZtransform

TounderstandtheCZT,firstvisualizetheFFT.AsshowninFigure1A,whencalculatingtheFFT,
thecyclicfrequencyrangeof0Hztothesamplingfrequency(s)isequalto0thru2radians
aroundtheunitcirclewithsamplestakenequaldistancearoundit.TheCZTiscapableof
calculatingthespectrumofasignaloveranarcoftheunitcircleasshowninFigure1Bor,in
otherwords,asignalbetweentwoarbitraryfrequenciesbelowthesamplingfrequencysuchas
255Hzto1,234Hz.

Figure1:Unitcirclerepresentationofspectrum

Figure2:DataflowthroughCZT
TheCZTisnotrestrictedtocalculatingthespectrumontheunitcircleandcancomputethez
transformatpointsalongcirclesorspiralsonthezplane,asshowninFigure1Cand1D.These
calculations,however,arebeyondthescopeofthisarticle.
YoucanunderstandthedetailsoftheCZTastheconvolutionofthesampledinputandtheunit
circlearccoefficientsdefinedwhenselectingtheresolutionoftheCZT,asshowninFigure1B.As
http://www.embedded.com/print/4006427

1/6

29/02/2016

www.embedded.com/print/4006427

seeninFigure2,twoFFTsandoneinverseFFTareusedtocalculatetheCZT.Therefore,to
quicklydeterminetheCZT,thenumberofpointssampledmustbeapoweroftwo.You'renot
restrictedtothisrule,however,becausetheCZTcode,whichispostedonlineat
ftp://ftp.embedded.com/pub/2004/02sirin,willzeropadtheinputsamplestoapoweroftwo.If
you'reusingtheCZTinrealtimespectrumanalysis,knowingthefollowingvalueswillincrease
theCZT'scomputingspeed:
1.Whatisthesamplingfrequencyoftheinput?
2.Howmanyinputsamplesarethere?
3.Whatisthestartfrequencyofthebandwidthofinterest?
4.Whatisthestopfrequencyofthebandwidthofinterest?
5.Whatspectralresolutiondoyouwantinthebandwidthofinterest?
Mostlikelythesamplingfrequencyandnumberofinputsampleswillnotchangeaftereachuse
oftheCZT.Therefore,ifyoudesignateaconstantoutputresolutionandstartandstopbands,
youcanprecomputethearccoefficientsatinitialization,therebyspeedinguptheCZT
computationattheexpenseofflexibility.

Samplingfrequency,inputsamples

Thesamplingfrequencyusuallydependsontheapplication.Forexample:
8kHztelephonystandard
16kHzG.722audiocompressionstandardforvideoteleconferencing
32kHzusedindigitalradio
44.1kHzCDqualityaudio
TheCZTusesthesamplingfrequencyasareferencetodeterminewherethestartandstop
bandsarelocatedontheunitcircle.Theresolution,alsoknownasbinsize,isdeterminedby
dividingthesamplingfrequencybandwidthbythenumberofinputsamples.Forinstance,ifthe
samplefrequencybandwidthis44.1kHzand1,024sampleswererecordedin23ms,thenthe
resolutionwouldbe44,100/1,024=43Hz.
Increasingthenumberofsamplesto2,048recordedover46mswouldofferaresolutionof
44,100/2,048=21.5Hz.

Startandstopfrequency,frequencyresolution

Engineersareofteninterestedinasmallrangeoffrequenciesandoversampleananalogsignal
tosatisfytheNyquistcriterion.Havingoversampled,thebinsbelowandabovethebandwidthof
interestdon'taidincreatingaclearpictureofthedesiredfrequencies,asshowninFigure3.

Figure3:ResolutionusingFFT

http://www.embedded.com/print/4006427

2/6

29/02/2016

www.embedded.com/print/4006427

Figure4:SamplespectrumusingFFT
WiththeCZT,theusercandefinenotonlythestartandstopfrequenciesbutalsothenumberof
binscontainedbythatbandwidth.
Youcanseethesignificanceofresolutioniftwofrequenciesappearbetweenthesetbinsizes.
Suppose128samplesat8kHzaretakenofanaudiosignal.Theresolutionis8,000/128=
62.5Hz,andthreeofthebinsarecalculatedtobe437.5Hz,500Hz,and562.5Hzrespectively.
62.5*N=437.5,500,562.5Hz(whereN=7,8,9)
Iftwotoneswereacquiredat470Hzand530Hzbetweentheestablishedbins,thespectrum
outputwouldappearsimilartotheyellowshadedareainFigure4.Analysisofthisspectrum
wouldindicateatoneat500Hzhasbeendetected,alsoshowninFigure4.
UsingtheCZTwithastartandstopfrequenciesof100Hzand1,000Hzrespectively,128output
sampleswouldgivearesolutionof7Hz,similartotheenhancedresolutionshowninFigure5.

Figure5:CZTresolutionsuperimposedoverFFT

Figure6:SamplespectrumusingCZT
Withahigherresolutionof7Hzperbin,thetwotonesat470Hzand530Hzcanclearlybe
resolved,asseeninFigure6.Thisconfigurationallowsresolutionofanytwotonesthatare
separatedbyatleast7Hz.
Tosummarize,theCZTrequiresthesamplingfrequencyandnumberofinputsamplesbecoupled
withthestartandstopfrequenciestodeterminethearcalongtheunitcirclewithwhichthe
sampledinputswillbeconvolved.TheCZTalsorequiresthenumberofoutputsamplesto
establishtheresolutionbetweenthestartandstopfrequencies.

CZTvs.FFT

HavingexpendedsomucheffortonincreasingthespeedandaccuracyoftheFFT,whywould
therebeaneedforanythingelse?TheanswerliesinthesacrificesmadetotheFFTtoachieve
speed.Onesuchlimitationisthepoweroftworule,requiringthenumberofinputsamplestobe
anintegerpoweroftwo(inotherwords,128,256,512).Whileinitselfthismaynotseem
important,coupledwiththefactthatsamplingfrequenciesareoftendictatedbythesampling
http://www.embedded.com/print/4006427

3/6

29/02/2016

www.embedded.com/print/4006427

hardwaretocommonsamplingfrequencies,suchas44.1kHz,22.050kHz,16kHz,11.025kHz,and
8kHzresolution,choicesstartbecomingseverelylimitedasshowninTable1.
Table1:Possiblebinssizeswithcommonsamplingfrequenciesandpoweroftwonumber
ofsamples
44,100/ 1,024= 43Hz 22,050/ 1,024=21Hz 16,000/ 1,024= 16Hz 11,025/ 1,024= 11Hz 8,000/ 1,024= 8Hz
44,100/

512= 86Hz 22,050/

44,100/

256= 172Hz

22,050/256= 84Hz

512=42Hz 16,000/

512= 32Hz 11,025/

512= 22Hz 8,000/

512= 16Hz

16,000/256=64Hz 11,025/256=44Hz 8,000/256=32Hz

AddtothisscenariotheNyquistcriterion,requiringthesamplingfrequencytobetwicethehighest
frequencybeingsampled.Then,choosingtolowersamplingfrequenciesforbetterresolutionisno
longeraviableoption.Acleverengineerwouldsimplyincreasethenumberofsamplesbeingtaken.
However,thissolutionquicklygetsoutofhand.
Everyincreaseinsamplescollectedmustbetwicethatpreviouslysampledinordertosatisfythe
poweroftworuleshowninTable2.Thesamplingfrequencyandnumberofsamplesacquireddefine
thesamplingtimeinterval.Forexample,tocapture1,024sampleswithasamplingrateof8kHz
requires(1/8,000)*1,024=0.128seconds.Steppinguptothenextpoweroftwo,thesamplingtime
requiredis(1/8,000)*2,048=0.256seconds.Here'sthepattern:toattaintwicetheresolution,twice
thenumberofsamplesisrequired,whichtakestwicethetimetoacquire.
Table2:Validpoweroftwosamples
210 =
211 =

1,024

212 =
213 =

4,056

2,048
8,192

214 = 16,384
215 = 32,768
216 = 65,536

ComparedtotheFFT,theCZTismuchmoreflexible.Giventhesamplingrateandthenumberof
samplestaken,youcantailortheresolutiontoyourapplicationbyadjustingthestartandstop
frequenciesandthenumberofoutputsamples(binsize).It'sironic,however,thattomakespectrum
analysismoreflexible,theCZTusestheFFTitself.ThefastertheFFTbecomes,themoreefficient
theCZTbecomes.Inspiteofthis,theCZTwillneverbefasterthantheFFT.
CZTvs.Goertzel
TheGoertzelalgorithmisafastermethodofpitchdetectionthantheFFTforsinglefrequencies.The
Goertzel'samazingspeedcomesfromfocusingondetectingtheamplitudeandphaseofasingle
frequency.AlthoughtheGoertzelisn'tlimitedbythepoweroftworule,thesamesamplingandbin
sizeconsiderationsoftheFFTapply.Notboundbythepoweroftworule,theGoertzelismore
flexibleatadjustingbinsizes.Assumingthatsamplingratesaredictatedbyhardware(inotherwords,
44.1kHz,8kHz),youonlyneedtochangethenumbersamplestoachievethedesiredbinsize.

TodeterminethenumberofsamplestoobtainintheGoertzelalgorithm,findthesmallestinteger
valueofkthatprovidesanintegervaluenumberofsamples(inotherwords,205,301).Ifyoucan't
findanintegervalueofkandyouuseanapproximateresolution,beawarethatyoumightnotgetan
http://www.embedded.com/print/4006427

4/6

29/02/2016

www.embedded.com/print/4006427

accuratemagnitudemeasurement.IftheGoertzelalgorithmisusedfortonedetection,thisproblem
maynotbeanissue.Beawarethatalargernumberofsamplestakeslongertosample.Therefore,for
realtimeapplicationsyoumayneedtominimizethesamplingduration.
AlthoughtheGoertzelalgorithmisbettersuitedtotonedetection,youcanuseitforspectrumanalysis
bylookingatmultipletonestocreateaspectrum.Todothis,youshouldchangethetargetfrequency
andsweepitacrossthespectrumofinterest.Thismethodisacceptableforverysmallbandwidthsbut
becomesmuchslowerasthenumberoffrequenciesbeingsweptacrossgrows.TheFFTandCZT,on
theotherhand,aremuchmoretimeefficientatcalculatingthespectrumoflargerbandwidths.
ComparedtotheFFT,theGoertzelalgorithmismoreflexible.Giventhesamplingrateandthetarget
frequency,thenumberofsamplesacquiredcaneasilybeadjustedtoobtainthedesiredbinsize.The
advantagesofspeedandflexibilityarespoiledbytheGoertzel'ssingularfocusonasolitary
frequency.TheCZT,incontrast,offersmorechoicesthantheGoertzelforselectingresolutions,but
doessoatthepriceofspeed.Inaddition,theCZToutputresolutioncanbetailormadebyadjusting
thestartandstopfrequencies,andthenumberofoutputsamples(binsize)overarangeof
frequencies.
Anothertool
TheCZTiscapableofanalyzingarangeoffrequenciestorecordfrequencyresponsemeasurements,
matchvoicepatterns,ordisplayspectruminformation.Itgivestheengineertheflexibilitytospecify
bandwidthandresolution,andoutputsrealandimaginaryfrequencycomponentsfromwhichthe
magnitudeandphasecanbecomputed.
WithabetterunderstandingoftheCZTalgorithm,thewidespreadandenduringuseoftheFFTbegs
thequestion,"Istheneedformoreresolutionandflexibilityworththecomputationalloadandtime
delay?"TheCZTisanothertoolintheengineer'sarsenalwhenengineersarechallengedtodetect
tones,frequencies,signatures,orsometelltalesignofaconditionofinterest.Similarly,theGoertzel
algorithmisapowerfultool,whichfindsspecificfrequenciesfasterthantheFFT.Thepertinent
designquestiontoaskyourselfis"IsthesinglefrequencydetectionoftheGoertzelalgorithmtoo
narrowandtheFFTtoowideformyapplication?"
SimonSirinisanengineerattheRemoteSensingLaboratory,operatedfortheU.S.Departmentof
EnergybyBechtelNevada,whereheworksonembeddedandrealtimesoftwareandhardware
applications.HeholdsaBSinelectricalengineeringfromtheUniversityofNevada,LasVegas.You
[email protected].
Acknowledgments
ThisworkwassupportedbytheU.S.DepartmentofEnergy,NationalNuclearSecurity
AdministrationNevadaSiteOffice,underContractNo.DEAC0896NV11718.DOE/NV/11718
833.
References
Banks,Kevin."TheGoertzelAlgorithm,"EmbeddedSystemsProgramming,September2002,pp.
32"42.
Taft,Jeffrey."TheJavaChirpZTransformSourceCodePage,"September2003,
www.nauticom.net/www/jdtaft/JavaCZT.htm
Taft,Jeffrey."TheChirpZTransformPage,"September2003,
www.nauticom.net/www/jdtaft/czt.htm
Oliver,William."ChirpzTransform,"June2003,
http://feynman.stanford.edu/people/Oliver_www/singhtml/node44.html
Bluestein'sFFTAlgorithm.Wikipedia,July2003,
http://en.wikipedia.org/wiki/Bluestein%27s_FFT_algorithm

http://www.embedded.com/print/4006427

5/6

29/02/2016

www.embedded.com/print/4006427

Readerresponse
Thefiguresinthearticlearemisleading.Thedistancebetweenbincenters("binsize"inthefigures)is
alteredfromtheFFTtotheCZT.Thebinshape(theyellowhumpinthefigures)orfrequency
resolutionisdeterminedbytheinputsampleset:1/(#ofsamplestimesSampleFrequency).This
doesnotchangebetweentheFFTandtheCZT.Theresolutiondoesnotchange.Youcanreadthisin
thewikipediareference.
DaleB.Dalrymple
SystemsEngineer
ISLInc.
ThatkmustbeanintegerintheGoertzelalgorithmisacommonmisconception.Choosingitso
somewhatsimplifiestheanalysisandgreatlysimplifiestheexplanation,butitisbynomeansrequired
bythemathematics.Forafixedsqmplerateandfrequenciestobedetected(suchasDTMFandFSK),
nonintegerkcansignificantlyimprovetheaccuracyofdiscrimination.
Refertorecentthreadsongroup:comp.dsp(GoertzeldetectortoGoertzelfilter?),(AnotherGoertzel
question,andGoertzel'sAlgorithmforRFSpectralMonitoring),orsimplytryitandsee.
JerryAvins
RetiredE.E.

http://www.embedded.com/print/4006427

6/6