[PDF] Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm

View - Download Fourier Transforms and the Fast Fourier Transform (FFT) Algorithm

Previous PDF

Next PDF

Notes 3, Computer Graphics 2, 15-463

Fourier Transforms and the

Fast Fourier Transform (FFT) Algorithm

Paul Heckbert

Feb. 1995

Revised 27 Jan. 1998

We start in the continuous world; then we get discrete.

De®nition of the Fourier Transform

The Fourier transform (FT) of the functionf.x/is the functionF.!/, where:

F.!/DZ

1 -1 f.x/e -i!x dx and the inverse Fourier transform is f.x/D1 2Z 1 -1 F.!/e i!x d!

Recall thatiDp

1ande i

DcosCisin.

Think of it as a transformation into a different set of basis functions. The Fourier trans- form uses complex exponentials (sinusoids) of various frequencies as its basis functions. (Other transforms, such as Z, Laplace, Cosine, Wavelet, and Hartley, use different basis functions). A Fourier transform pair is often writtenf.x/$F.!/,or

F.f.x//DF.!/whereF

is the Fourier transform operator. Iff.x/isthoughtofasasignal(i.e. inputdata)thenwecallF.!/thesignal'sspectrum. Iffisthoughtofas theimpulseresponseofa®lter(whichoperates on inputdatatoproduce output data) then we callFthe ®lter'sfrequency response. (Occasionally the line between what's signal and what's ®lter becomes blurry). 1

Example of a Fourier Transform

Suppose we want to create a ®lter that eliminates high frequencies but retains low frequen- cies (this is very useful in antialiasing). In signal processing terminology, this is called an ideal low pass ®lter. So we'll specify a box-shaped frequency response with cutoff fre- quency! c

F.!/D1j!j!

c

0j!j>!

c

What is its impulse response?

We know that the impulse response is the inverse Fourier transform of the frequency response, so taking off our signal processing hat and puttingon our mathematics hat, all we need to do is evaluate: f.x/D1 2Z 1 -1 F.!/e i!x d! for this particularF.!/: f.x/D1 2Z c c e i!x d! D 1 2e i!x ix c !D-! c D1 xe i! c x -e -i! c x 2i D sin! c x xsince sinDe i -e -i 2i D! c sinc.! c x/ where sinc.x/Dsin.x/=.x/. For antialiasing with unit-spaced samples, you want the cutoff frequency to equal the Nyquist frequency, so! c D.

Fourier Transform Properties

Rather than write ªthe Fourier transform of anXfunction is aYfunctionº, we write the shorthand:X$Y.Ifzis a complex number andzDxCiywherexandyare its real and imaginary parts, then the complex conjugate ofzisz

Dx-iy. A functionf.u/isevenif

f.u/Df.-u/,itisoddiff.u/D-f.-u/, it is conjugate symmetric iff.u/Df .-u/, and it is conjugate antisymmetric iff.u/D-f .-u/. 2 discrete$periodic periodic$discrete discrete, periodic$discrete, periodic real$conjugate symmetric imaginary$conjugate antisymmetric box$sinc sinc$box

Gaussian$Gaussian

impulse$constant impulse train$impulse train (can you prove the above?) When a signal is scaled up spatially, its spectrum is scaled down in frequency, and vice versa:f.ax/$F.!=a/for any real, nonzeroa.

Convolution Theorem

The Fourier transform of a convolution of two signals is the product of their Fourier trans- forms:fg$FG. The convolution of two continuous signalsfandgis .fg/.x/DZ C1 -1 f.t/g.x-t/dt So R C1 -1 f.t/g.x-t/dt$F.!/G.!/. The Fourier transform of a product of two signals is the convolution of their Fourier transforms:fg$FG=2.

Delta Functions

The (Dirac) delta function.x/is de®ned such that.x/D0 for allx6D0,R C1 -1 .t/dtD1, and for anyf.x/: .f/.x/DZ C1 -1 f.t/.x-t/dtDf.x/ The latter is called thesifting propertyof delta functions. Because convolution with a delta is linear shift-invariant ®ltering, translating the delta byawill translate the output bya: f.x/.x-a/ .x/Df.x-a/ 3

Discrete Fourier Transform (DFT)

When a signal is discrete and periodic, we don't need the continuous Fourier transform. Instead we use the discrete Fourier transform, or DFT. Suppose our signal isa n fornD

0:::N-1, anda

n Da nCjN for allnandj. The discrete Fourier transform ofa, also known as the spectrum ofa,is: A k D N-1 X nD0 e -i 2 N kn a n

This is more commonly written:

A k D N-1 X nD0 W knN a n (1) where W N De -i 2 N andW kN forkD0:::N-1arecalledtheNth roots of unity. They're called this because, in complex arithmetic,.W kN N D1 for allk. They're vertices of a regular polygon inscribed in the unit circle of the complex plane, with one vertex at.1;0/. Below are roots of unity forND2,ND4, andND8, graphed in the complex plane. W 42
ReIm N=2W 20 W 21
N=4W 40
W 43
W 41

1-1 -1

1i -i W 84
N=8W 80
W 86
W 82
-1 1i -i W 87
W 85
W83 W 81
Powers of roots of unity are periodic with periodN, since the Nth roots of unity are N isequiv- alent to rotation clockwise by this angle. Multiplication byW NN is rotation by 2radians, that is, no rotation at all. In general,W kN DW kCjN N for all integerj. Thus, when raisingW N to a power, the exponent can be taken moduloN.

ThesequenceA

k n . Eachisasequence ofNcomplex numbers.

The sequencea

n is the inverse discrete Fourier transform of the sequenceA k .Thefor- mula for the inverse DFT is a n D1 N N-1 X kD0 W -knN A k 4 The formula is identical except thataandAhave exchanged roles, as havekandn.Also, the exponent ofWis negated, and there is a 1=Nnormalization in front.

Two-point DFT (N=2)

W 2 De -i

D-1, and

A k D 1 X nD0 .-1/ kn a n D.-1/ k0 a 0 C.-1/ k1 a 1 Da 0 C.-1/ k a 1 soA 0 Da 0 Ca 1 A 1 Da 0 -a 1

Four-point DFT (N=4)

W 4 De -i=2

D-i,and

A k D 3 X nD0 .-i/ kn a n Da 0 C.-i/ k a 1 C.-i/ 2k a 2 C.-i/ 3k a 3 Da 0 C.-i/ k a 1 C.-1/ k a 2 Ci k a 3 soA 0 Da 0 Ca 1 Ca 2 Ca 3 A 1 Da 0 -ia 1 -a 2 Cia 3 A 2 Da 0 -a 1 Ca 2 -a 3 A 3 Da 0 Cia 1 -a 2 -ia 3 This can also be written as a matrix multiply:8>>>>>>>>>>>>>>>>:A 0 A 1 A 2 A 3

9>>>>>>>>>>>>>>>>;D8

>>>>>>>>>:1111

1-i-1i

1-11-1

1i-1-i9

>>>>>>>>>;8 >>>>>>>>>>Tj?T*?(>>>>>>:a 0 a 1 a 2 a 3

9>>>>>>>>>>>>>>>Tj?0 -0.29 TD?(>;

More on this later.

To computeAquickly, we can pre-compute common subexpressions: A 0 D.a 0 Ca 2 /C.a 1 Ca 3 A 1 D.a 0 -a 2 /-i.a 1 -a 3 A 2 D.a 0 Ca 2 /-.a 1 Ca 3 Aquotesdbs_dbs5.pdfusesText_9

[PDF] fast fourier transform simple code

[PDF] fast fourier transform simple explanation

[PDF] fast fourier transform theory pdf

[PDF] fast fourier transform tutorial pdf

[PDF] fast fourier transform vs fourier transform

[PDF] fastest lmp1 car

[PDF] fatal big cat attacks

[PDF] fatca details in nps tin number

[PDF] fatca form

[PDF] fatca full form

[PDF] fatca meaning

[PDF] fatca tin number search

[PDF] fatf methodology

[PDF] fatf recommendation 12

[PDF] fatf recommendation 16 for wire transfers