LeeTwe 5
DFT CFHT) popertes and F¥T conolution
As explained earlier, the pFT can be inte coreted
oo frequency olomain Sam pling othe DTET
X(n) e 2Ttnt
X(P) = OTFT
=-O
Samplig in Heq. domain
(N poi ntsver ea'ch period f > mfs
N
N-
(n) e mn/N
Xm)= OFT
I n DTFT X (P) o peNodic coith period F= Es
oue to Sampling in t i e doman
DFDFTo. obtained by sampling inthe freqrency
d omai
the eqvilant time omain signalafterIDFT)
peio dic in the tirne domain,
ocln) DTET
O
t 2s
eiod fs =ts
n) after IpF,
NN e>
prioodic), periocl=Sampl
DF T
IDFT
ahulhn
tperiod = t
his poriodicty can be Ventiedtoom the
IDFT equahion
N j2mn/N
clM) Xm) e
N mo
J27mn+N)N
N-
Compuing c(mt N) L X(m)
N M
N- 27Tm
2Tmn/N
Xm) e' e
Nmo
oclm)
o(m) o periolic with peried = N Samples
Numbe eSormpleo pe peiool la
he requen cy oomai
Hssuming more gensrol scenarioS in dhich the
time domain Sianal has L samples and an N-P
DT Cemputed, e . haue 3 sanaria3:
L= N ln) peiodic sth periaoN
cm) juo vepeats itselP
LN -1li.
L
N
olm) hoo a period N
ho si ono iled Oith zebs pelueen Land N
LN
In thisCase ime do main aiasing oillour
thi's should lbe avoidad, [Link] o hy the FFT
size i
udually L
CN)
An interecring conclusion om caye(2) uwhen N>L
ee-o siana length L Go
N 128
Jo pertorm this, pad the Sional uibh 68 reos
and take FFT. In thi cone bh2 numbac o
req uenc domaina points 198 cohich means the
O¥T sTarts to loo dosec to. D1FT t e
w e t u wnen evaluat ng the e a ne ny ponge
ate from its impwse fesponse.
Ch. 4 Steven Smith's book, rig 9.7
A the extfeme Careb hen N>- -L ha
Spectrum looko more and mare Continou, nih,
a the|imst uhdn N-b ou qef the TFT
D)FT
apenadic
anod th time olomain Siqna becoms Gpenadc.
Hnother important con secuence is the yeie shif
ropey the DFT:
T cn), X(m) are a DtTpair
GCm) 21TKm/N x m ) , K an integer
e
then n)
Cirealan shifE by Samgle
unlike i DTFT
xn), N= 4 X(m)
OFT
TDFT
o
23 45 6
.21m/N
X,(m) = e Xm
lllil 23
LDFT
re, k=d
this io shat you See over a
eriod e N=4
Conicn is c(n-
Cyclic, shit die to the pen'odic
nore Cm)
This also impacs the onvoluhi On pfoperty i
OFT Tk X3(m)N- = X,(m) Xalm) salled
Circwa
oNoldo
2 () C k ) c2n-k
cicctar shift
Also in this example XG(m) is petodic coth
a penod equal to the FFT size. N
1 oC, (m) ha L Sample
2m) ho PS amples
Then the FFT size N shodd be at east
eonalto
L+P-1toavaidaliasing
(time domain) gCon)
LRg 9:4, Chq s Shs book
Cconvolubion
Hn 1mportant applicotion T ohen Convolving
Goith an impulse fesponse (hn)) shich is long
h (m)
Lsamples Psamples)
2 paddim Peopadd
to LP- LtP-
take FFT take EET
Xn) H(m)
Note N= L+P-1
T Con. u
footer, eo pQcially /TEAT
when hn) o Ytm SR
IFFT
long, ie, P6otor fo what you
yln) (identical
xamp) 9n)qe from feguar Cr
TConvoluion Can also be very Powerul in
image procon9
You have to do zero padding in c829 directions
Ex: 00 x 0Oo image to be convolved oi th
29 29PsF
ooth should be zapadde to be 12&xl28.
hen Take 20FT,.muhiely, 2D-IEFT to
usn D FFT'Ss using iD-IFFTS
obtain the reo wlt.
To be come much faoter bhan feqular anv
hen PSF arge.
FT Convoluhon also simpli bies the pfoa o
eNersing a particdor ilter effech throuá
deconvoluti on, which is simply division in the
freauenc olomaincan be uaese-g, Ko inmage
enhancement and Ceotorahion from Cectain
effects
althouah more Sophisticoted staisticol algorith-
ale uual y oed , ea, iener iters, ete. avoid
noige enhancement- oWside Sape obhis
CorS.)
Sechon 7:3 Oppenhem
loek FT convoluhon | Sechion 131o [Link]'s
text book
n many case you may ant to :lker, eg a
spee ch oaveform caith very longleng th ompare
to the im pulse feoponse. You can still take FET
o4he entite signal and perkotm FET convblutian,
T
butit coilll beco me imprachical ao the signol gets
onge and lonae Hnother proslem o lodenCy
ohe yo need to w a i t o the entite signol
before producin ony otpt
Souhion och Cenvo
cCanvolutian.
hete are 22 metho do. foc block ¥¥T convoon
Metho d Overlap -
Add method
Sime
Simplybased on. tha.. pinciple. Superposition
LTI Sstems
Divide ctn). into blocks non-overlappi
Sement, than Con vo we eacn Seament
Seporatrely csith hn)
m = pm) + c4m} Kaln) +
1m)= Co(n) h (n)
, Cn) = (m) h(m)
(n) 2n) * h ( )
m) = xn) h(n)
= Cn) + S, (m) +.(n)
As Oppenkeam
illuotrateol ia tia. 2 P.69
22 dnd 23
he above poCeslure Can be dpne' o ingha
feauar r e domon: Convolto, bu in Olde ho
use thT;
Each block romcn) th length LSamples
should bepadola d winP) 2eos hare
Pio the length oionpulat feopon Se hlm)
Then tare FFT oeackbleth
& T hn) padded L-) Feros
ol mulbply tham, then.
an
TFFT o qat
n) In) . etc.
The outputs TFET are adlded
Tocethar (the
overlap by -1) Samplo
Mehool
2 Overlap-
Save mathod
In this methed, each block o
input L Sanple
i circwtany con
voed coith Psompls ohln)
eg, wn FFT). Tnthio caoe the 4 P-
Semples feulh9 bm the Convo ution are
cofona, ond
and ane thm oliscalde d om the
De to m-doman qlias ing
o n vol 0a OuupulT.
The Corect porti ons ohe croular convoution
owputs are then patcked toqetha
toe
Jo pertofmm thb operahjon, eachTblock oL
Samelo Oyec laps by P-1) Sample ith th
precacing block, i e, you Sae tha laot P-
SampleD rom prewioo blocls o be weel in the
besanning h ne»t block, hence the name
Ove ap- Save method.
Jh pro@ o illuotrated In ia 24
Loppenheim, P. Foo
