MATEMATEKA REKAYASAMO 091204

Fungsi-fungsi Khusus: Fourier and FT

mahmud mustain

Fourier andFourier Transform

Why should we learn Fourier Transform?

Sumber: www.csee.wvu.edu/~xinl/courses/ee465/fourier.ppt

Born: 21 March 1768 in Auxerre, Bourgogne, FranceDied: 16 May 1830 in Paris, France

Joseph Fourier

Joseph’s father was a tailor in AuxerreJoseph was the ninth of twelve childrenHis mother died when he was nine andhis father died the following year Fourier demonstrated talent on mathat the age of 14.In 1787 Fourier decided to train for the priesthood - a religious life or a mathematical life?In 1793, Fourier joined the local Revolutionary Committee

Fourier’s “Controversy” Work

• Fourier did his important mathematical work on the theory of heat (highly regarded memoir On the Propagation of Heat in Solid Bodies ) from 1804 to 1807

• This memoir received objection from Fourier’s mentors (Laplace and Lagrange) and not able to be published until 1815

Napoleon awarded him a pension of 6000 francs, payable from 1 July, 1815. Napoleon awarded him a pension of 6000 francs, payable from 1 July, 1815. However Napoleon was defeated on 1 July and Fourier did not receive any moneyHowever Napoleon was defeated on 1 July and Fourier did not receive any money

Expansion of a Function

Example (Taylor Series)

constant

first-orderterm

second-orderterm

…

Fourier Series

Fourier series make use of the orthogonality relationships of the sine and cosine functions

Examples

Fourier Transform

• The Fourier transform is a generalization of the complex Fourier series in the limit

• Fourier analysis = frequency domain analysis – Low frequency: sin(nx),cos(nx) with a small n– High frequency: sin(nx),cos(nx) with a large n

• Note that sine and cosine waves are infinitely long – this is a shortcoming of Fourier analysis, which explains why a more advanced tool, wavelet analysis, is more appropriate for certain signals

Applications of Fourier Transform

• Physics– Solve linear PDEs (heat conduction, Laplace, wave

propagation)• Antenna design

– Seismic arrays, side scan sonar, GPS, SAR• Signal processing

– 1D: speech analysis, enhancement …– 2D: image restoration, enhancement …

Not Just for EE

• Just like Calculus invented by Newton, Fourier analysis is another mathematical tool

• BIOM: fake iris detection• CS: anti-aliasing in computer graphics• CpE: hardware and software systems

FT in Biometrics

natural fake

FT in CS

Anti-aliasing in 3D graphic display

FT in CpE

• Computer Engineering: The creative application of engineering principles and methods to the design and development of hardware and software systems

• If the goal is to build faster computer alone (e.g., Intel), you might not need FT; but as long as applications are involved, there is a place for FT (e.g., Texas Instrument)

14

Frequency-Domain Analysis of Interpolation

• Step-I: Upsampling

• Step-II: Low-pass filtering• Different interpolation schemes correspond to

different low-pass filters

L/nTxL/nxnx ci

15

Frequency Domain Representation of Upsampling

k

Lkje wLXekxwX

16

Frequency Domain Representation of Interpolation

Introduction toFast Fourier Transform (FFT)

Algorithms

Sumber: ecee.colorado.edu/~ecen4002/10_fft_intro.ppt

ECEN4002 Spring 2003 FFT Intro R. C. Maher 18

Discrete Fourier Transform (DFT)

• The DFT provides uniformly spaced samples of the Discrete-Time Fourier Transform (DTFT)

• DFT definition:

• Requires N2 complex multiplies and N(N-1) complex additions

1

0

2

][][N

n

Nnkj

enxkX

1

0

2

][1][N

n

Nnkj

ekXN

nx

ECEN4002 Spring 2003 FFT Intro R. C. Maher 19

Faster DFT computation?• Take advantage of the symmetry and periodicity

of the complex exponential (let WN=e-j2/N)– symmetry: – periodicity:

• Note that two length N/2 DFTs take less computation than one length N DFT: 2(N/2)2<N2

• Algorithms that exploit computational savings are collectively called Fast Fourier Transforms

*][ )( knN

knN

nNkN WWW

nNkN

NnkN

knN WWW ][][

ECEN4002 Spring 2003 FFT Intro R. C. Maher 20

Decimation-in-Time Algorithm

• Consider expressing DFT with even and odd input samples:

1

02/

1

02/

1

0

21

0

2

1

0

22

22

]12[]2[

)](12[)](2[

][][

][][

NN

NN

r

rkN

kN

r

rkN

r

rkN

kN

r

rkN

oddn

nkN

evenn

nkN

N

n

nkN

WrxWWrx

WrxWWrx

WnxWnx

WnxkX

ECEN4002 Spring 2003 FFT Intro R. C. Maher 21

DIT Algorithm (cont.)• Result is the sum of two N/2 length DFTs

• Then repeat decomposition of N/2 to N/4 DFTs, etc.

samples odd ofDFT N/2

sampleseven ofDFT N/2

][][][ kHWkGkX kN

X[0…7]

x[0,2,4,6]

x[1,3,5,7]

N/2

DFT

N/2

DFT7...0

NW

ECEN4002 Spring 2003 FFT Intro R. C. Maher 22

Detail of “Butterfly”

• Cross feed of G[k] and H[k] in flow diagram is called a “butterfly”, due to shape

rNW

)(

)2(

rN

NrN

W

W

rNW -1

or simplify:

ECEN4002 Spring 2003 FFT Intro R. C. Maher 23

8-point DFT Diagram

0NW

0NW

0NW

0NW

0NW

0NW

0NW

2NW

2NW

2NW

1NW

3NW

1

1

1

1

1

1

1

1

1

1

1

1

X[0…7]x[0,4,2,6,1,5,3,7]

ECEN4002 Spring 2003 FFT Intro R. C. Maher 24

Computation on DSP

• Input and Output data– Real data in X memory– Imaginary data in Y memory

• Coefficients (“twiddle” factors)– cos (real) values in X memory– sin (imag) values in Y memory

• Inverse computed with exponent sign change and 1/N scaling

AL-HAMDULILLAH