DSP_FOEHU - MATLAB 04 - The Discrete Fourier Transform (DFT)

DSP_FOEHU - MATLAB 04 - The Discrete Fourier Transform (DFT)

1. MATLAB(04)
The Discrete Fourier Transform
(DFT)
Assist. Prof. Amr E. Mohamed

2. Introduction
Thediscrete-timeFouriertransform(DTFT)providedthefrequency-
domain(ω)representationforabsolutelysummablesequences.
Thez-transformprovidedageneralizedfrequency-domain(z)
representationforarbitrarysequences.
Thesetransformshavetwofeaturesincommon.
First,thetransformsaredefinedforinfinite-lengthsequences.
Second,andthemostimportant,theyarefunctionsofcontinuousvariables
(ωorz).
Inotherwords,thediscrete-timeFouriertransformandthez-transform
arenotnumericallycomputabletransforms.
TheDiscreteFourierTransform(DFT)avoidsthetwoproblems
mentionedandisanumericallycomputabletransformthatissuitable
forcomputerimplementation.
2

3. Periodic Sequences
Let ??????(??????)isaperiodicsequencewithperiodN-Samples(thefundamental
periodofthesequence).
Notation:asequencewithperiodNissatisfyingthecondition
whererisanyinteger.
3 ),...1(),...,1(),0(),1(),...,1(),0(...,)(
~
 NxxxNxxxnx
x(n) x(n))(
~
)(
~
rNnxnx 

4. Periodic Sequences
FromFourieranalysisweknowthattheperiodicfunctionscanbesynthesized
asalinearcombinationofcomplexexponentialswhosefrequenciesare
multiples(orharmonics)ofthefundamentalfrequency(whichinourcaseis
2π/N).
ThediscreteversionoftheFourierSeriescanbewrittenas
where{ ??????(??????),??????=0,±1,...,∞}arecalledthediscreteFourierseries
coefficients.
NoteThat,forintegervaluesofm,wehave
(itiscalledTwiddleFactor)
4


k
kn
N
k
N
kn
j
k
kn
N
j
k
WkX
N
ekX
N
eXnx )(
~1
)(
~1
)(
~
2
2

 nmNk
N
N
nmNk
j
N
kn
j
kn
N WeeW
)(
)(
22






5. Synthesis and Analysis (DFS-Pairs)
5
Notation)/2(Nj
NeW


Synthesis




1
0
)(
~1
)(
~
N
k
kn
NWkX
N
nx
Analysis)(
~
)(
~
kXnx 
DFS
Both have
Period N



1
0
)(
~
)(
~
N
k
kn
NWnxKX

6. Matlab Implementation
AnefficientimplementationinMATLABwouldbetouseamatrix-vector
multiplication.
Let Xand Xdenotecolumnvectorscorrespondingtotheprimaryperiodsof
sequences ??????(??????)and ??????(??????),respectively.
wherethematrix�
??????isgivenby
6

7. Matlab Implementation (Cont.)
ThefollowingMATLABfunctiondfsimplementsthisprocedure.
7

8. Matlab Implementation (Cont.)
Example:TheDFSof ????????????={...,0,1,2,3,0,1,2,3,0,1,2,3,...}canbe
computedusingMATLABas
8

9. Matlab Implementation (Cont.)
Thefollowingidfsfunctionimplementsthesynthesisequation.
9

10. EXAMPLE
10

11. Solution
AplotofthissequenceforL=5andN=20isshownintheFigure
11

12. Solution (Cont.)
a.ByapplyingtheDFSanalysisequation
Thelastexpressioncanbesimplifiedto
12

13. Solution (Cont.)
orthemagnitudeof �(??????)isgivenby
b.TheMATLABscriptforL=5andN=20:
13

14. Solution (Cont.)
TheplotsforthisandallothercasesareshownintheFigure.
Notethatsince �(??????)isperiodic,theplotsareshownfrom−N/2toN/2.
14

15. Solution (Cont.)
C.Severalinterestingobservationscanbemadefromplotsintheabove
Figure.TheenvelopesoftheDFScoefficientsofsquarewaveslooklike
“sinc”functions.Theamplitudeatk=0isequaltoL,whilethezeros
ofthefunctionsareatmultiplesofN/L,whichisthereciprocalofthe
dutycycle.
15

16. Discrete Fourier Transform(DFT)
16

17. The DFT Pair
17N
j
N
N
k
kn
N
N
k
N
kn
j
N
n
kn
N
N
n
N
kn
j
eWwhere
NnWkX
N
x
ekX
N
xSynthesis
NkWnxX
enxXAnalysis



2
1
0
1
0
2
1
0
1
0
2
1,...,1,0)(
1
n)(
)(
1
n)(
1,...,1,0)(k)(
)(k)(





















18. Matlab Implementation
TheMATLABhas
thedftfunctiontocalculateDiscreteFourierTransform,and
theidftfunctiontocalculatetheinverseDiscreteFourierTransform.
Or,wecanusethefollowingcode
18

19. Example
19

20. Solution
a.Thediscrete-timeFouriertransformisgivenby
20

21. Solution (Cont.)
Theplotsofmagnitudeandphaseare
21

22. Solution (Cont.)
b.Letusdenotethe4-pointDFTbyX4(k).Then
WecanalsouseMATLABtocomputethisDFT.
Notethatwhenthemagnitudesampleiszero,thecorrespondingangle
isnotzero.ThisisduetoaparticularalgorithmusedbyMATLABto
computetheanglepart.Generallytheseanglesshouldbeignored.
22

23. Solution (Cont.)
23

24. Zero-Padding Operation
InpreviousExample,HowcanweobtainothersamplesoftheDTFT
??????(�
????????????
)?
Solution:Thiswecanachievebytreatingx(n)asan8-pointsequenceby
appending4zeros.
MATLABscript:
24

25. Zero-Padding Operation (Cont.)
Hence
25

26. Zero-Padding Operation (Cont.)
1.Zero-paddingisanoperationinwhichmorezerosareappendedtothe
originalsequence.TheresultinglongerDFTprovidescloselyspaced
samplesofthediscrete-timeFouriertransformoftheoriginal
sequence.
2.Thezero-paddinggivesusahigh-densityspectrumandprovidesa
betterdisplayedversionforplotting.Butitdoesnotgiveusahigh-
resolutionspectrumbecausenonewinformationisaddedtothesignal;
onlyadditionalzerosareaddedinthedata.
3.Togetahigh-resolutionspectrum,onehastoobtainmoredatafrom.
26

27. Example
27

28. Solution
a.Wecanfirstdeterminethe10-pointDFTofx(n)toobtainanestimate
ofitsdiscrete-timeFouriertransform.MATLABScript:
28

29. Solution (Cont.)
TheplotsinFigureshow
therearen’tenoughsamples
todrawanyconclusions.
Thereforewewillpad90
zerostoobtainadense
spectrum.
29

30. Solution (Cont.)
MATLABScript:
30

31. Solution (Cont.)
NowtheplotinFigureshows
thatthesequencehasa
dominant frequency at
ω=0.5π.
Thisfactisnotsupportedby
theoriginalsequence,which
hastwofrequencies.
Thezero-paddingprovideda
smootherversionofthe
spectrum.
31

32. Solution (Cont.)
b.Togetbetterspectralinformation,wewilltakethefirst100samplesof
x(n)anddetermineitsdiscrete-timeFouriertransform.
MATLABScript:
32

33. Solution (Cont.)
Nowthediscrete-timeFourier
transformplotinFigure
clearlyshowstwofrequencies,
whichareveryclosetoeach
other.
Thisisthehigh-resolution
spectrumofx(n).
Notethatpaddingmorezeros
tothe100-pointsequencewill
resultinasmootherrendition
ofthespectrum.
33

34. Circular Convolution
34

35. Circular Convolution
Aconvolutionoperationthatcontainsacircularshiftiscalledthe
circularconvolutionandisgivenby
NotethatthecircularconvolutionisalsoanN-pointsequence.
Ithasastructuresimilartothatofalinearconvolution.Thedifferences
areinthesummationlimitsandintheN-pointcircularshift.Henceit
dependsonNandisalsocalledanN-pointcircularconvolution.
Thereforetheuseofthenotation??????isappropriate.TheDFTproperty
forthecircularconvolutionis
35

36. MATLAB
Implementation
Thefollowingcirconvt
functionisaMATLAB
function that
calculatesthecircular
convolution.
36

37. MATLAB Implementation (Cont.)
Performthecircularconvolutionforthefollowingtwosequences
MATLABscript:
Hence
37

38. Linear Convolution Using The DFT
Infact,FIRfiltersaregenerallyimplementedinpracticeusingthis
linearconvolution.Ontheotherhand,theDFTisapracticalapproach
forimplementinglinearsystemoperationsinthefrequencydomain.
TheDFTisalsoanefficientoperationintermsofcomputations.
However,thereisoneproblem.TheDFToperationsresultinacircular
convolution(somethingthatwedonotdesire),notinalinear
convolutionthatwewant.
Howtomakeacircularconvolutionidenticaltothelinear
convolution???
Let??????
1(??????)and??????
2(??????)atwosequenceswithlength??????
1????????????�??????
2,thenthe
circularconvolutionisidenticaltothelinearconvolution.Ifwepadboth
sequencetohavealengthequalto??????=(??????
1+??????
2−1)point.
38

39. Example
Solution:
39

40. THE FAST FOURIER TRANSFORM
40

41. MATLAB IMPLEMENTATION
MATLABprovidesafunctioncalledffttocomputetheDFTofavectorx.
ItisinvokedbyX=fft(x,N),whichcomputestheN-pointDFT.
IfthelengthofxislessthanN,thenxispaddedwithzeros.Ifthe
argumentNisomitted,thenthelengthoftheDFTisthelengthofx.
Ifxisamatrix,thenfft(x,N)computestheN-pointDFTofeachcolumn
ofx.
ThisfftfunctioniswritteninmachinelanguageandnotusingMATLAB
commands(i.e.,itisnotavailableasa.mfile).Thereforeitexecutes
veryfast.Itiswrittenasamixed-radixalgorithm.
TheinverseDFTiscomputedusingtheifftfunction,whichhasthesame
characteristicsasfft.
41

42. 42