Convolution, Correlation, Fourier Transforms

1 Convolution, Correlation,& Fourier TransformsJames R. Graham11/25/2009 Introduction A large class of signal processingtechniques fall under the category ofFourier transform methods These methods fall into two broad categories Efficient method for accomplishing common datamanipulations Problems related to the Fourier transform or thepower spectrumTime & Frequency Domains A physical process can be described in two ways In the time domain, by h as a function of time t, that ish(t), - < t < In the frequency domain, by H that gives its amplitudeand phase as a function of frequency f, that is H(f), with- < f < In general h and H are complex numbers It is useful to think of h(t) and H(f) as twodifferent representations of the same function One goes back and forth between these tworepresentations by Fourier transformsFourier Transforms If t is measured in seconds, then f is in cycles persecond or Hz Other units , if h=h(x) and x is in meters, then H is a function ofspatial frequency measured in cycles per meter H(f)=h(t)

2 E 2 iftdt h(t)=H(f)e2 iftdf Fourier Transforms The Fourier transform is a linear operator The transform of the sum of two functions isthe sum of the Transforms h12=h1+h2H12(f)=h12e 2 iftdt =h1+h2()e 2 iftdt =h1e 2 iftdt +h2e 2 iftdt =H1+H2 Fourier Transforms h(t) may have some special properties Real, imaginary Even: h(t) = h(-t) Odd: h(t) = -h(-t) In the frequency domain these symmetrieslead to relations between H(f) and H(-f)FT SymmetriesH(f) real & oddh(t) imaginary & oddH(f) imaginary & evenh(t) imaginary & evenH(f) imaginary & oddh(t) real & oddH(f) real & evenh(t) real & evenH(-f) = - H(f) (odd)h(t) oddH(-f) = H(f) (even)h(t) evenH(-f) = -[ H(f) ]*h(t) imaginaryH(-f) = [ H(f) ]*h(t) Properties of FT h(t) H(f) Fourier Pairh(at) 1aH(f/a) Time scalingh(t t0) H(f)e 2 ift0 Time shiftingConvolution With two functions h(t) and g(t), and theircorresponding Fourier Transforms H(f) andG(f), we can form two special combinations The convolution, denoted f = g * h, defined by ft()=g h g( )h(t )d Convolution g*h is a function of time, andg*h = h*g The convolution is one member of a transform pair The Fourier transform of the convolution is theproduct of the two Fourier Transforms !

3 This is the Convolution Theorem g h G(f)H(f)Correlation The correlation of g and h The correlation is a function of t, which isknown as the lag The correlation lies in the time domainCorr(g,h) g( +t)h( )d Correlation The correlation is one member of the transformpair More generally, the RHS of the pair is G(f)H(-f) Usually g & h are real, so H(-f) = H*(f) Multiplying the FT of one function by thecomplex conjugate of the FT of the other gives theFT of their correlation This is the Correlation Theorem Corr(g,h) G(f)H*(f)Autocorrelation The correlation of a function with itself iscalled its autocorrelation. In this case the correlation theorem becomesthe transform pair This is the Wiener-Khinchin Theorem Corr(g,g) G(f)G*(f)=G(f)2 Convolution Mathematically the convolution of r(t) ands(t), denoted r*s=s*r In most applications r and s have quitedifferent meanings s(t) is typically a signal or data stream, whichgoes on indefinitely in time r(t) is a response function, typically a peakedand that falls to zero in both directions from itsmaximumThe Response Function The effect of convolution is to smear thesignal s(t) in time according to the recipeprovided by the response function r(t) A spike or delta-function of unit area in swhich occurs at some time t0 is Smeared into the shape of the response function Translated from time 0 to time t0 as r(t - t0)Convolution The signal s(t) is convolved with a response function r(t) Since the response function is broader than some features in theoriginal signal, these are smoothed out in the convolutions(t)r(t)

4 S*rFourier Transforms & FFT Fourier methods have revolutionized many fieldsof science & engineering Radio astronomy, medical imaging, & seismology The wide application of Fourier methods is due tothe existence of the fast Fourier transform (FFT) The FFT permits rapid computation of the discreteFourier transform Among the most direct applications of the FFT areto the convolution, correlation & autocorrelationof dataThe FFT & Convolution The convolution of two functions is defined forthe continuous case The convolution theorem says that the Fouriertransform of the convolution of two functions is equalto the product of their individual Fourier Transforms We want to deal with the discrete case How does this work in the context of convolution? g h G(f)H(f)Discrete Convolution In the discrete case s(t) is represented by itssampled values at equal time intervals sj The response function is also a discrete set rk r0 tells what multiple of the input signal in channel j iscopied into the output channel j r1 tells what multiple of input signal j is copied into theoutput channel j+1 r-1 tells the multiple of input signal j is copied into theoutput channel j-1 Repeat for all values of kDiscrete Convolution Symbolically the discrete convolution iswith a response function of finite duration,N, is s r()j=skrj kk= N/2+1N/2 s r()j SlRlDiscrete Convolution Convolution of discretely sampled functions Note the response function for negative times wrapsaround and is stored at the end of the array rksj rk (s*r)j Examples Java applet demonstrations Continuous convolution ~signals/convolve/ Discrete convolution ~signals/discreteconv/Suppose that f and g are functions of timef(t)=F( )e2 i t- d and g(t)=G( )

5 E2 i t- d The convolution f*g says f g=g(t')f(t t')- dt'=g(t')F( )e2 i (t t')- d - dt'Swap the order of integration=F( )g(t')e 2 i t'dt'- - e2 i td =FTF( )G( )[]Voila!