Jenkins, W.K. “Fourier Series, Fourier Transforms, and the DFT”
Digital Signal Processing Handbook
Ed. Vijay K. Madisetti and Douglas B. Williams
Boca Raton: CRC Press LLC, 1999
c

1999byCRCPressLLC
1
Fourier Series, Fourier Transforms,
and the DFT
W. Kenneth Jenkins
University of Illinois,
Urbana-Champaign
1.1Introduction
1.2FourierSeriesRepresentationofContinuousTime
PeriodicSignals
ExponentialFourierSeries
•
TheTrigonometricFourierSeries
•
Convergence of the Fourier Series
1.3TheClassicalFourierTransformforContinuousTime
Signals
PropertiesoftheContinuousTimeFourierTransform
•
Fourier Spectrum of the Continuous Time Sampling Model
•
FourierTransform ofPeriodicContinuousTimeSignals
•
The
Generalized Complex Fourier Transform

the discrete Fourier transform (DFT),are extensions of basic Fourier concepts that apply to discrete
time (DT) signals. A characteristic DT signal, s[n], is defined only for values of n where n is an
integer in the range −∞ <n<∞. The following discussion presents basic concepts and outlines
important properties forboth the CT and DT classes ofFouriermethods, with aparticular emphasis
ontherelationshipsbetweenthese twoclasses. The classofDT Fouriermethodsisparticularly useful
c

1999 by CRC Press LLC
asabasisfordigitalsignal processing(DSP)becauseit extendsthetheory of classical Fourieranalysis
to DT signals and leads to many effective algorithms that can be directly implemented on general
computers or special pur pose DSP devices.
TherelationshipbetweentheCTandtheDTdomainsischaracterizedbytheoperationsofsampling
and reconstruction. If s
a
(t) denotes a signal s(t) that has been uniformly sampled every T seconds,
then the mathematical representation of s
a
(t) is given by
s
a
(t) =
∞

n=−∞
s(t)δ(t − nT ) (1.1)
where δ(t) is a CT impulse function defined to be zero for all t = 0, undefined at t = 0, and has
unit area when integ rated from t =−∞to t =+∞. Because the only places at which the product
s(t)δ(t−nT ) isnotidenticallyequaltozeroareatthesamplinginstances,s(t)in(1.1)canbereplaced
with s(nT ) without changing the overall meaning of the expression. Hence, an alternate expression
for s

(t) ands[n] aredifferent but equivalent
models of the sampling process in the CT and DT domains, respectively. They are both useful for
signal analysis in their corresponding domains. Their equivalenceis established by the fact that they
have equal spectra in the Fourier domain, and that the underlying CT signal from which s
a
(t) and
s[n] are derived can be recovered from either sampling representation, provided a sufficiently large
sampling rate is used in the sampling operation (see below).
1.2 Fourier Series Representation of Continuous Time Periodic
Signals
It is convenient to begin this discussion with the classical Fourier series representation of a p eriodic
timedomainsignal,andthenderive the Fourierintegralfromthisrepresentationbyfinding the limit
of the Fourier coefficient representationas the period goes toinfinity. The conditionsunderwhicha
periodic signal s(t) can be expanded in a Fourier series are known as the Dirichet conditions. They
require that in each period s(t) has a finite number of discontinuities, a finite number of maxima
and minima, and that s(t) satisfies the following absolute convergence criterion [1]:

T/2
−T/2
|s(t)| dt < ∞ (1.4)
Itis assumed in the following discussion that these basic conditions are satisfied byall functions that
will be represented by a Fourier ser ies.
c

1999 by CRC Press LLC
FIGURE1.1:CTmodelofasampledCTsignal.
FIGURE1.2:DTmodelofasampledCTsignal.
1.2.1 ExponentialFourierSeries
IfaCTsignals(t)isperiodicwithaperiodT,thentheclassicalcomplexFourierseriesrepresentation
ofs(t)isgivenby

−
)ands(t
+
),wheres(t
−
)≡lim
→0
s(t−)ands(t
+
)≡
lim
→0
s(t+).
Forexample,theFourierseriesexpansionofthesawtoothwaveformillustratedinFig.1.3ischar-
acterizedbyT=2π,ω
0
=1,a
0
=0,anda
n
=a
−n
=Acos(nπ)/(jnπ)forn=1,2, ,.The
coefficientsoftheexponentialFourierseriesrepresentedby(1.5b)canbeinterpretedasthespec-
tralrepresentationofs(t),becausethea
n
-thcoefficientrepresentsthecontributionofthe(nω
0
)-th
frequencytothetotalsignals(t).Becausethea

seriesintoatrigonometricformthatcontainssin(ω
0
t)andcos(ω
0
t)termswithcorrespondingreal-
c

1999byCRCPressLLC
valued coefficients [1]. The trigonometric form of the Fourier series for a real-valued signal s(t) is
given by
s(t) =
∞

n=0
b
n
cos(nω
0
t) +
∞

n=1
c
n
sin(nω
0
t) (1.6a)
where ω
0
= 2π/T .Theb

t)dt, n = 1, 2, ,
An arbitrary real-valued signal s(t) can be expressed as a sum of even and odd components, s(t) =
s
even
(t) + s
odd
(t),wheres
even
(t) = s
even
(−t) and s
odd
(t) =−s
odd
(−t), and where s
even
(t) =
[s(t) + s(−t)]/2 and s
odd
(t) =[s(t) − s(−t)]/2. For the trigonometric Fourier series, it can be
shownthats
even
(t)isrepresentedbythe(e ven)cosinetermsintheinfiniteseries,s
odd
(t)isrepresented
by the (odd) sine terms, and b
0
is the DC level of the signal. Therefore, if it can be determined by
inspectionthata signalhasDClevel,orifit isevenorodd,thenthecorrectformof thetrigonometric
c

n
=(b
n
−jc
n
)/2forn=1,2, ,a
0
=b
0
,anda
−n
=a
∗
n
.
ThetrigonometricFourierseriesiscommoninthesignalprocessingliteraturebecauseitreplaces
complexcoefficientswithrealonesandoftenresultsinasimplerandmoreintuitiveinterpretation
oftheresults.
1.2.3 ConvergenceoftheFourierSeries
TheFourierseriesrepresentationofaperiodicsignalisanapproximationthatexhibitsmeansquared
convergencetothetruesignal.Ifs(t)isaperiodicsignalofperiodT,ands

(t)denotestheFourier
seriesapproximationofs(t),thens(t)ands

(t)areequalinthemeansquaresenseif
MSE=

T/2
−T/2

thedefinitionofcontinuity.)BecausetheDirichetconditionsrequirethats(t)haveatmostafinite
numberofpointsofdiscontinuityinoneperiod,thesetS
t
,definedasallvaluesoftwithinone
periodwheres(t)=s

(t),containsafinitenumberofpoints,andS
t
isasetofmeasurezerointhe
formalmathematicalsense.Therefore,s(t)anditsFourierseriesexpansions

(t)areequalalmost
everywhere,ands(t)canbeconsideredidenticaltos

(t)fortheanalysisofmostpracticalengineering
problems.
Convergencealmosteverywhereissatisfiedonlyinthelimitasaninfinitenumberoftermsare
includedintheFourierseriesexpansion.IftheinfiniteseriesexpansionoftheFourierseriesis
truncatedtoafinitenumberofterms,asitmustbeinpracticalapplications,thentheapproximation
willexhibitanoscillatorybehavioraroundthediscontinuity,knownastheGibbsphenomenon[1].
Lets

N
(t)denoteatruncatedFourierseriesapproximationofs(t),whereonlythetermsin(1.5a)
fromn=−Nton=NareincludedifthecomplexFourierseriesrepresentationisused,orwhere
onlythetermsin(1.6a)fromn=0ton=NareincludedifthetrigonometricformoftheFourier
seriesisused.Itiswellknownthatinthevicinityofadiscontinuityatt
0
theGibbsphenomenon
causess


N
(t)|
2
dt (1.8)
c

1999byCRCPressLLC
AnimportantpropertyoftheFourierseriesisthattheexponentialbasisfunctionse
jnω
0
t
(orsin(nω
0
t)
andcos(nω
0
t)forthetrigonometricform )forn=0,±1,±2, (orn=0,1,2, forthe
trigonometricform)constituteanorthonormalset,i.e.,t
nk
=1forn=k,andt
nk
=0forn=k,
where
t
nk
=(1/T)

T/2
−T/2

becomes
infinitesimallysmall,aconditionthatisdenotedbyreplacingω
0
withω.Thefactor(1/T)in(1.5a)
becomes(ω/2π).Withthesealgebraicmanipulationsandchangesinnotation(1.5a)and(1.5b)
takeonthefollowingformpriortotakingthelimit:
s(t)= (1/2π)
∞

n=−∞
a

n
e
jnωt
ω (1.10a)
a

n
=

T/2
−T/2
s(t)e
−jnωt
dt (1.10b)
ThefinalstepinobtainingtheCTFouriertransformistotakethelimitofboth(1.10a)and(1.10b)
asT→∞.Inthelimittheinfinitesummationin(1.10a)becomesanintegral,ωbecomesdω,
nωbecomesω,anda


−1
{2πδ(ω−
ω
0
)}=e
jω
0
t
,sothatδ(t−t
0
)↔e
−jωt
0
ande
jω
0
t
↔2πδ(ω−ω
0
)arevalidFouriertransform
c

1999byCRCPressLLC
pairs. UsingtheserelationshipsitiseasytoestablishtheFouriertransformsofcos(ω
0
t)andsin(ω
0
t),
as well as many other useful waveforms that are encountered in common signal analysis problems.
A number of such transforms are shown in Table 1.1.

(t) =

∞
−∞
f
1
(t − τ)f
2
(τ ) dτ
1. Linearity (superposition): F {af
1
(t) + bf
2
(t)}=aF {f
1
(t)}+bF{f
2
(t)}
(a and b, complex constants)
2. Time shifting: F{f(t − t
0
)}=e
−jωt
0
F {f(t)}
3. Frequency shifting: e
jω
0
t
f(t)= F

properties 1, 6, and7 areuseful for solving differential or integralequations. Property 4 provides the
basis for many signal processing algorithms because many systems can be specified directly by their
impulseorfrequencyresponse. Property3isparticularlyusefulinanalyzingcommunicationsystems
inwhichdifferentmodulationfor matsarecommonlyusedtoshiftspectralenergytofrequencybands
that are appropriate for the application.
1.3.2 Fourier Spectrum of the Continuous Time Sampling Model
Because the CT sampling model s
a
(t), given in (1.1), is in its ownright a CT signal, it is appropriate
to apply the CTFT to obtain an expression for the spectrum of the sampled signal:
F {s
a
(t)}=F

∞

n=−∞
s(t)δ(t − nT )

=
∞

n=−∞
s(nT )e
−jωTn
(1.12)
Becausetheexpressionontheright-hand sideof(1.12)isafunctionofe
jωT
itiscustomarytodenote
the transform as F(e

k
e
jω
0
t
2πδ(ω+ω
0
)
a
1
=1
a
k
=0, otherwise
cosω
0
tπ[δ(ω−ω
0
)+δ(ω+ω
0
)]
a
1
=a
−1
=
1
2
a
k

T
0
>0

Periodicsquarewave
x(t)=



1, |t|<T
1
0,T
1
<|t|≤
T
0
2
+∞

k=−∞
2sinkω
0
T
1
k
δ(ω
k
ω
0
)


k=−∞δ

ω−
2πk
T

a
k
=
1
T
forallk
x(t)=

1, |t|<T
1
0, |t|>T
1
2T
1
sinc

ωT
1
π

=
2sinωT
1

−at
u(t),Re{a}>0
1
a+jω
—
te
−at
u(t),Re{a}>0
1
(a+jω)
2
—
t
n−1
(n−1)!
e
−at
u(t),
Re{a}>0
1
(a+jω)
n
—
c

1999byCRCPressLLC
TABLE1.2 PropertiesoftheCTFT
Name IfFf(t)=F(jω),then
Definition f(jω)=


(b)f(t)isodd F(jω)=2j

∞
0
f(t)sinωtdt
Negativet Ff(−t)=F
∗
(jω)
Scaling:
(a)Time F
f(at)=
1
|a|
F

jω
a

(b)Magnitude Faf(t)=aF(jω)
Differentiation F

d
n
dt
n
f(t)

=(jω)
n
F(jω)

)]}
{
Ff(t)sinω
0
t=
1
2
j[F[j(ω−ω
0
)]−F[j(ω+ω
0
)]}
Timeconvolution F
−1
[F
1
(jω)F
2
(jω)]=

∞
−∞
f
1
(τ)f
2
(τ)f
2
(t
τ

n
e
jnω
0
t

=2π
∞

n=−∞
a
n
δ(ω−nω
0
) (1.13)
ThespectrumisshownpictoriallyinFig.1.7.Notethesimilaritybetweenthespectralrepresentation
ofFig.1.7andtheplotoftheFouriercoefficientsinFig.1.4,whichwasheuristicallyinterpreted
asa“linespectrum”.Figures1.4and1.7aredifferentbutequivalentrepresentationsoftheFourier
c

1999byCRCPressLLC
spectrum.NotethatFig.1.4isaDTrepresentationofthespectrum,whileFig.1.7isaCTmodelof
thesamespectrum.
FIGURE1.7:SpectrumoftheFourierseriesrepresentationofs(t).
1.3.4 TheGeneralizedComplexFourierTransform
TheCTFTcharacterizedby(1.11a)and(1.11b)canbegeneralizedbyconsideringthevariablejω
tobethespecialcaseofu=σ+jωwithσ=0,writing(1.11a)intermsofu,andinterpretingu
asacomplexfrequencyvariable.TheresultingcomplexFouriertransformpairisgivenby(1.14a)
and(1.14b)
s(t)= (1/2πj)


1999byCRCPressLLC
anormalizedfrequencyω

=ωT,theDTFTpairisdefinedin(1.15a).Notethatinordertosimplify
notationitisnotcustomarytodistinguishbetweenωandω

,butrathertorelyonthecontextofthe
discussiontodeterminewhetherωreferstothenormalized(T=1)ortheunnormalized(T=1)
frequencyvariable.
S(e
jω

) =
∞

n=−∞
s[n]e
−jω

n
(1.15a)
s[n]=(1/2π)

π
−π
S(e
jω

)e

transformisidenticaltothespectrumofs[n]ascalculatedbytheDTFT.Therefore,althoughs
a
(t)
ands[n]arequitedifferentsamplingmodels,theyareequivalentinthesensethattheyhavethesame
Fourierdomainrepresentation.
AlistofcommonDTFTpairsispresentedinTable1.3.JustastheCTFouriertransformisuseful
inCTsignalsystemanalysisanddesign,theDTFTisequallyusefulinthesamecapacityforDT
systems.ItisindeedfortuitousthatFouriertransformtheorycanbeextendedinthiswaytoapply
toDTsystems.
InthesamewaythattheCTFouriertransformwasfoundtobeaspecialcaseofthecomplexFourier
transform(orbilateralLaplacetransform),theDTFTisaspecialcaseofthebilateralz-transform
withz=e
jω

t
.Themoregeneralbilateralz-transformisgivenb y
S(z)=
∞

n=−∞
s[n]z
−n
(1.17a)
s[n]=(1/2πj)

C
S(z)z
n−1
dz (1.17b)
whereCisacounterclockwisecontourofintegrationwhichisaclosedpathcompletelycontained

n
u[n] (|a|<1)
1
1−ae
−jω
5.u[n]
1
1−e
−jω
+
∞

k=−∞
πδ(ω+2πk)
6.(n+1)a
n
u[n] (|a|<1)
1
(1−ae
−jω
)
2
7.
r
2
sinω
p
(n+1)
sinω
p

sin(ω/2)
e
−jωM/2
10.e
jω
0
n
∞

k=−∞
2πδ(ω−ω
0
+2πk)
11.cos(ω
0
n+φ) π
∞

k=−∞
[e
jφ
δ(ω−ω
0
+2πk)+e
−jφ
δ(ω+ω
0
+2πk)]
1.4.1 PropertiesoftheDiscreteTimeFourierTransform
BecausetheDTFTisacloserelativeoftheclassicalCTFouriertransformitshouldcomeasnosurprise

{F(e
j(ω−ω
0
)
)}
4.Timedomainconvolution:DTFT{f
1
[n]∗f
2
[n]}=DTFT{f
1
[n]}DTFT{f
2
[n]}
5.Frequencydomainconvolution:DTFT{f
1
[n]f
2
[n]}=(1/2π)DTFT{f
1
[n]}∗DTFT{f
2
[n]}
6.Frequencydifferentiation:nf[n]=DTFT
−1
{dF(e
jω
)/dω}
Notethatthetime-differentiationandtime-integrationpropertiesoftheCTFTdonothaveanalogous
counterpartsintheDTFTbecausetimedomaindifferentiationandintegrationarenotdefinedforDT

x[n] X(e
j(ω−ω
0
)
)
4.x[−n] X(e
−jω
) ifx[n]isreal
X
∗
(e
jω
)
5.nx[n] j
dX(e
jω
)
dω
6.x[n]∗y[n] X(e
jω
)Y(e
jω
)
7.x[n]y[n]
1
2π

x
−x
X(e

2π
π
inf
−π
X(e
jω
)Y
∗
(e
jω
)dω
signals.WhenworkingwithDTsystemspractitionersmustoftenmanipulatedifferenceequations
inthefrequencydomain.Forthispurposeproperty1andproperty2areveryimportant.Aswith
theCTFT,property4isveryimportantforDTsystemsbecauseitallowsengineerstoworkwith
thefrequencyresponseofthesystem,inordertoachievepropershapingoftheinputspectrumor
toachievefrequencyselectivefilteringfornoisereductionorsignaldetection.Also,property3is
usefulfortheanalysisofmodulationandfilteringoperationscommoninbothanaloganddigital
communicationsystems.
TheDTFTisdefinedsothatthetimedomainisdiscreteandthefrequencydomainiscontinuous.
ThisisincontrasttotheCTFTthatisdefinedtohavecontinuoustimeandcontinuousfrequency
domains.ThemathematicaldualoftheDTFTalsoexists,whichisatransformpairthathasa
continuoustimedomainandadiscretefrequencydomain.Infact,thedualconceptisreallythe
sameastheFourierseriesforperiodicCTsignalspresentedearlierinthechapter,asrepresented
by(1.5a)and(1.5b).However,theclassicalFourierseriesarisesfromtheassumptionthattheCT
signalisinherentlyperiodic,asopposedtothetimedomainbecomingperiodicbyvirtueofsampling
thespectrumofacontinuousfrequency(aperiodictime)function[8].ThedualoftheDTFT,the
discretefrequencyFouriertransform(DFFT),hasbeenformulatedanditspropertiestabulatedas
aninterestingandusefultransforminitsownright[5].AlthoughtheDFFTissimilarinconcept
totheclassicalCTFourierseries,theformalpropertiesoftheDFFT[5]servetoclarifytheeffects
offrequencydomainsamplingandtimedomainaliasing.Theseeffectsareobscuredintheclassical


,sotheexplicitprimednotation
isusedinthefollowingdiscussionwhereneededforclarification.Becausethesamplingfunction
(summationofshiftedimpulses)ontheright-handsideoftheaboveequationisperiodicwithperiod
TitcanbereplacedwithaCTFourierseriesexpansionasfollows:
S(e
jωT
)=F{s
a
(t)}=(1/2π)S(jω)∗F

∞

n=−∞
(1/T)e
j(2π/T)nt

ApplyingthefrequencydomainconvolutionpropertyoftheCTFTyields
S(e
jωT
)=(1/2π)
∞

n=−∞
S(jω)∗(2π/T)δ(ω−(2π/T)n)
Theresultis
S(e
jωT
)=(1/T)
∞


)consistsofaninfinitenumberofreplicasoftheCTspectrumS(jω),positionedatintervals
of(2π/T)ontheωaxis(oratintervalsof2πontheω

axis),asillustratedinFig.1.8.Notethatif
S(jω)isbandlimitedwithabandwidthω
c
,andifTischosensufficientlysmallsothatω
s
>2ω
c
,
thentheDTspectrumisacopyofS(jω)(scaledby1/T)inthebaseband.Thelimitingcaseof
ω
s
=2ω
c
iscalledtheNyquistsamplingfrequency.WheneveraCTsignalissampledatorabove
theNyquistrate,noaliasingdistortionoccurs(i.e.,thebasebandspectrumdoesnotoverlapwiththe
higher-orderreplicas)andtheCTsignalcanbeexactlyrecoveredfromitssamplesbyextractingthe
basebandspectrumofS(e
jω

)withanideallow-passfilterthatrecoverstheoriginalCTspectrumby
removingallspectralreplicasoutsidethebasebandandscalingthebasebandbyafactorofT.
1.5 TheDiscreteFourierTransform
ToobtainthediscreteFouriertransform(DFT)thecontinuousfrequencydomainoftheDTFT
issampledatNpointsuniformlyspacedaroundtheunitcircleinthez-plane,i.e.,atthepoints
c


N
[n]=1forn=0, ,N−1,andR
N
[n]=0
forn<0andn≥N.Thetransformrelationshipgivenby(1.20a)and(1.20b)isalsovalidwhen
s[n]andS[k]areperiodicsequences,eachofperiodN.Inthiscasenandkarepermittedtorange
overthecompletesetofrealintegers,andS[k]isreferredtoasthediscreteFourierseries(DFS).The
DFSisdevelopedbysomeauthorsasadistincttransformpairinitsownright[6].Whetherthe
DFTandtheDFSareconsideredidenticalordistinctisnotveryimportantinthisdiscussion.The
importantpointtobeemphasizedhereisthattheDFTtreatss[n]asthoughitwereasingleperiod
ofaperiodicsequence,andallsignalprocessingdonewiththeDFTwillinherittheconsequencesof
thisassumedperiodicity.
1.5.1 PropertiesoftheDiscreteFourierSeries
MostofthepropertieslistedinTable1.5fortheDFTaresimilartothoseofthez-transformandthe
DTFT,althoughsomeimportantdifferencesexist.Forexample,property5(time-shiftingproperty),
holdsforcircularshiftsofthefinitelengthsequences[n],whichisconsistentwiththenotionthatthe
DFTtreatss[n]asoneperiodofaperiodicsequence.Also,themultiplicationoftwoDFTsresultsin
thecircularconvolutionofthecorrespondingDTsequences,asspecifiedbyproperty7.Thislatter
propertyisquitedifferentfromthelinearconvolutionpropertyoftheDTFT.Circularconvolution
istheresultoftheassumedperiodicitydiscussedinthepreviousparagraph.Circularconvolution
issimplyalinearconvolutionoftheperiodicextensionsofthefinitesequencesbeingconvolved,in
whicheachofthefinitesequencesoflengthNdefinesthestructureofoneperiodoftheperiodic
extensions.
Forexample,supposeonewishestoimplementadigitalfilterwithfiniteimpulseresponse(FIR)
c

1999byCRCPressLLC
TABLE1.5 PropertiesoftheDFT
Finite-LengthSequence(LengthN) N-PointDFT(LengthN)
1.x[n] X[k]

−ln
N
x[n] X[((k−l))
N
]
7.
N−1

m=0
x
1
(m)x
2
[((n
m
))
N
] X
1
[k]X
2
[k]
8.x
1
[n]x
2
[n]
1
N
N−1

]+K
∗
[((−k))
N
]}
12.jIm{x[n]} X
op
[k]=
1
2
{X[((k))
N
]−X
∗
[((−k))
N
]}
13.x
ep
[n]=
1
2
{x[n]+x
∗
[((−n))
N
]} Re{X[k]}
14.x
op
[n]=

N
]|
<){X[k]} = −<){X[((−k))
N
]}
16.x
ep
[n]=
1
2
{x[n]+x[((−n))
N
]} Re{X[k]}
17.x
op
[n]=
1
2
{x[n]−x[((−n))
N
]} jIm{X[k]}
h[n].Theoutputy(n)inresponsetoinputs[n]isgivenby
y[n]=
N−1

k=0
h[k]s[n−k] (1.21)
wherey(n)isobtainedbytransformingh[n]ands[n]intoH[k]andS[k]usingtheDFT,multiplying
thetransformspoint-wisetoobtainY[k]=H[k]S[k],andthenusingtheinverseDFTtoobtain
y[n]=DFT

−N+1)],n=0, ,N
DFT
−1.Thefilterimpulse
c

1999byCRCPressLLC
response is augmented with N
DFT
− N zeroes to produce
h
pad
[n]=

h[n],n= 0, ,N − 1
0,n= N, ,N
DFT
− 1

(1.22)
TheDFTisthenusedtoobtainY
pad
[n]=DFT{h
pad
[n]}·DFT{s
k
[n]},andy
pad
[n]=IDFT{Y
pad
[n]}.

s[n + kL],n= 0, ,L− 1
0,n= L, ,N
DFT
− 1

(1.24)
where L = N
DFT
− N + 1. The filter function h
pad
[n] is augmented with zeroes, as before, to
createh
pad
[n], and the DFTprocessingisexecuted as before. In each block y
pad
[n] that is obtained
attheoutputthefirstN − 1 pointsareerroneous,thelastN − 1 pointsareerroneous,andthemiddle
N
DFT
− 2(N − 1) points correctly correspond to the linear convolution. However, if the last N − 1
points from block k are overlappedwith the first N − 1 points from block k + 1 and added pairwise,
correct results corresponding to linear convolution are also obtained from these positions. Hence,
after this addition the number of correct points produced per block is N
DFT
− N + 1, which is the
same as that for the overlap-save algorithm. The overlap-add algorithm requires approximately the
sameamountofcomputationastheoverlap-savealgorithm,althoughtheadditionoftheoverlapping
portionsofblocksisextra. Thisfeature,togetherwiththeaddeddelayofwaitingforthe nextblockto
be finished before the previous one is complete, has resulted in more popularity for the overlap-save
algorithm in practical applications.

2
4+k
1
2+k
0
andn=n
2
4+n
1
2+n
0
,
wherek
i
andn
i
arebitsthattakeonthevaluesofeither0or1.Iftheseexpressionsaresubstituted
into(1.20a),alltermsintheexponentthatcontainthefactorN=8canbedeletedbecause
e
−j2πl
=1foranyintegerl.Upondeletingsuchtermsandregroupingtheremainingterms,the
productnkcanbeexpressedineitheroftwoways:
nk = (4k
0
)n
2
+(4k
1
+2k
0

Substituting(1.25a)into(1.20a)leadstotheD-I-TFFT,whereassubstituting(1.25b)leadstothe
D-I-FFFT.OnlytheD-I-TFFTisdiscussedfurtherhere.TheD-I-Fandvariousrelatedformsare
treatedindetailin[6].
TheD-I-TFFTdecomposesintolog
2
Nstagesofcomputation,plusastageofbitreversal,
x
1
[k
0
,n
1
,n
0
]=
1

n
2
=0
s[n
2
,n
1
,n
0
]W
4k
0
n

8
(stage2) (1.26b)
x
3
[k
0
,k
1
,k
2
]=
1

n
0
=0
x[k
0
,k
1
,n
0
]W
(4k
2
+2k
1
+k
0
)n

isreplacedbyk
2
intheresult.Thelastoperation,called
bitreversal,isnecessarytocorrectlylocatethefrequencysamplesX[k]inthememory.Itiseasyto
showthatifthesamplesarepairedcorrectly,anin-placecomputationcanbedonebyasequenceof
butterflyoperations.Theterm“in-place”meansthateachtimeabutterflyistobecomputed,apair
ofdatasamplesisreadfrommemory,andthenewdatapairproducedbythebutterflycalculation
iswrittenbackintothememorylocationswheretheoriginalpairwasstored,therebyoverwriting
theoriginaldata.Anin-placealgorithmisdesignedsothateachdatapairisneededforonlyone
butterfly,andthusthenewresultscanbeimmediatelystoredontopoftheoldinordertominimize
memoryrequirements.
Forexample,instage3thek=6andk=7samplesshouldbepaired,yieldinga“butterfly”
computationthatrequiresonecomplexmultiply,onecomplexadd,andonesubtract:
c

1999byCRCPressLLC
x
3
(1, 1, 0) = x
2
(1, 1, 0) + W
3
8
x
2
(1, 1, 1) (1.27a)
x
3
(1, 1, 1) = x
2

Figure 1.9 shows the signal flow graph of the D-I-T FFT for N = 8. This algorithm is referred to
FIGURE 1.9: D-I-T FFT algorithm with normally ordered inputs and bit-reversed outputs.
as an in-place FFT with normally ordered input samples and bit-reversed outputs. Minor variations
that include both bit-reversed inputs and normally ordered outputs and non-in-place algorithms
with normally ordered inputs and outputs are possible. Also, when N is not a power of 2, a mixed-
radix algorithm can be used to reduce computation. The mixed-radix FFT is most efficient when
N is highly composite, i.e., N = p
r
1
1
p
r
2
2
···p
r
L
L
, where the p
i
are small prime numbers and the r
i
are positive integers. It can be shown that the order of complexity of the mixed radix FFT is order
{N(r
1
(p
1
−1)+r
2
(p

1.7 Selected Applications of Fourier Methods
1.7.1 Fast Fourier Transform in Spectral Analysis
An FFT program is often used to perform spectral analysis on signals that are sampled and recorded
aspart of laboratoryexperiments,or in certain typesofdataacquisitionsystems. Several issues must
be addressed when spectral analysis is performed on (sampled) analog waveforms that are observed
over a finite interval of time.
Windowing
The FFT treats the block of data as though it were one period of a periodic sequence. If the
underlying waveform is not per iodic, then harmonic distortion may occur because the periodic
waveform created by the FFT may have sharp discontinuities at the boundaries of the blocks. This
effectisminimizedbyremovingthemeanofthedata (it can alwaysbereinserted)andbywindowing
the data so the ends of the block are smoothly tapered to zero. A good rule of thumb is to taper
10% of the data on each end of the block using either a cosine taper or one of the other common
windows shown in Table1.7. An alternateinterpretationofthisphenomenonisthatthefinitelength
observation has already windowed the true waveform with a rectangular window that has large
spectral sidelobes (see Table 1.7). Hence, applying an additional window results in a more desirable
window that minimizes frequency domain distortion.
Zero Padding
An improve d spectral analysis is achieved if the block length of the FFT is increased. This
can be done by taking more samples within the observation interval, increasing the length of the
observation inter val, or augmenting the original data set with zeroes. First, it must be understood
that the finite observation interval results in a fundamental limit on the spectral resolution, even
before the signals are sampled. The CT rectangular window has a (sin x)/x spectrum, which is
convolvedwiththetrue spectrumof the analog signal. Therefore,thefrequencyresolutionislimited
bythewidth of the mainlobe in the (sin x)/x spectrum, which is inversely proportional to the length
c

1999 by CRC Press LLC
TABLE 1.6 An In-Place D-I-T FFT Program in C Language
/*****************************************************

}
}
n1=0;n2=1; /*FFT*/
for(i=0;i<m;i++) /*state loop */
{
n1 = n2; n2 = n2 + n2;
e = -6.283185307179586/n2;
a = 0.0;
for (j=0; j < n1; j++) /*flight loop */
{
c = cos(a); s=sin (a);
a=a+e;
for (k=j;k<n;k=k+n2) /*butterfly loop */
{
t1 = c*x[k+n1] - s*y[k+n1];
t2 = s*x[k+n1] + c*y[k+n1];
x[k+n1] = x[k] - t1;
y[k+n1] = y[k] - t2;
x[k] = x[k] + t1;
y[k] = y[k] + t2;
}
}
}
return;
}
c

1999 by CRC Press LLC
FIGURE 1.10: Relationships among CT Fourier concepts.
of the observation interval. Sampling causes a certain degree of aliasing, although this effect can

Bartlett ω(n) =

2/N, 0 ≤ n ≤ (N − 1)/2
22n/N, (N − 1)/2 ≤ n ≤ N − 1
−25 8π/N −25
Hanning ω(n) = (1/2)[1 − cos(2πn/N)]−31 8π/N −44
0 ≤ n ≤ N − 1 −43 8π/N −53
Hamming ω(n) = 0.54 − 0.46cos(2πn/N), −43 8π/N −53
0 ≤ n ≤ N − 1
Backman ω(n) = 0.42 − 0.5cos(2πn/N) −57 12π/N −74
+ 0.08 cos(4π n/N )
,
0 ≤ n ≤ N − 1
thespect rum. TheeffectisillustratedinFig.1.12forasinusoidthatisobservedthrougharectangular
window and then sampledatN points. The picketfenceeffectmeans that not all frequenciescan be
seen bythe FFT. Harmonic components areseen accurately, but other components “slipthrough the
picketfence” while their energyis“leaked” into the harmonics. Theseeffectsproduceartifacts in the
spectral domain that must be carefully monitored to assure that an accurate spectrum is obtained
from FFT processing.
1.7.2 Finite Impulse Response Digital Filter Design
AcommonmethodfordesigningFIRdigitalfiltersisbyuseofwindowingandFFTanalysis. Ingeneral,
windowdesignscanbecarriedoutwiththeaidofahandcalculatorandatableofwell-knownwindow
functions. Let h[n] be the impulse response that corresponds to some desired frequency response,
H(e
jω
).IfH(e
jω
) has sharp discontinuities, such as the low-pass example shown in Fig. 1.13, then
h[n] willrepresent an infinite impulse response (IIR) function. Theobjective is to time limit h[n] in
such a way as to not distort H(e

jω
) shouldbesimilartoanimpulse sothatH

(e
jω
)
is approximately equal to H(e
jω
).
Special Case. Let h[n]=cos nω
0
, for all n. Then h[n]=w[n] cosnω
0
, and
H

(e
jω
) = (1/2)W (e
j(ω+ω
0
)
) + (1/2)W(e
j(ω−ω
0
)
) (1.28)
as illustrated in Fig. 1.14. For this simple class, the center frequency of the bandpass is controlled
by ω
0

jω
), the design is finished. If not, choose
anewH(e
jω
) oraneww[n] and repeat. Throughout the designprocedure it is important to choose
N

= kN, withk aninteger that is typicallyintherange of 4 to 10. Because this designtechnique is a
c

1999 by CRC Press LLC