Bab 5: Discrete Fourier Transform dan FFT

BAB 5 Discrete Fourier Transform dan FFT

Bab 5: Discrete Fourier Transform dan FFT 1 Discrete Fourier Transform (DFT) 1.1

Definisi Tujuan Belajar 1 Peserta dapat mendefinisikan DFT, dan menghitungnya.

Untuk melakukan analisis frekuensi dari sinyal waktu diskrit x(n) maka perlu mendapatkan representasi domain frekuensi dari sinyal yang biasanya dinyatakan dalam domain waktu. DFT digunakan untuk melakukan analisa frekuensi dari sinyal waktu diskrit. N Po int DFT x(n) ←  → X (k )

dimana n = 0, …N-1 dan k = 0, …N-1

DFT dihitung menggunakan persamaan : N −1

X (k ) = ∑ x(n)WNkn dimana WN = e

−j

2π N

n =0

sehingga N −1

X ( k ) = ∑ x ( n) e

k  − j 2π   n N

n=0

Invers DFT (IDFT) menghitung kembali representasi sinyal waktu diskrit x(n) dari sinyal yang dinyatakan dalam domain frekuensi X(ω). 1 x ( n) = N =

N −1

∑ X ( k )e

 k  j 2π   n N

k =0

1 N

N −1

∑ X (k )W k =0

− kn N

dimana WN = e

−j

2π N

→ akar ke N dari unity

Tujuan Belajar 2 Peserta dapat memandang DFT sebagai transformasi linier dan perkalian matriks terhadap vektor. DFT dan IDFT dapat juga dipandang sebagai transformasi linier antara x(n) dan X(k), jadi

V-1


xN ↔ X N dimana xN dan XN masing-masing adalah vektor dengan n buah elemen  x(0)   X (0)   xN =  M  X N =  M   x( N − 1)  X ( N − 1) Jika dinyatakan matriks WN WN = wij = WN( i )( j ) maka, N point DFT dapat dinyatakan dalam bentuk X N = WN xN sedangkan IDFT dapat dihitung jika terdapat invers dari WN.

[

]

xN = WN−1 X N bila WN−1 exist Contoh: Hitung 4 point DFT dari sinyal x(n) = ( 0 1 2 3 )

1 1  1 1 1 W 1 W 2 W 3  4 4 4  W4 =  1 W42 W44 W46   3 6 9 1 W4 W4 W4  k + N2

ingat WN

k+

Ingat WN

= −WNk W44 = 1 W46 = −1

3

= −WNk

1 1  1 1 1 − j − 1 j   = 1 − 1 1 − 1    1 j − 1 − j   6  − 2 + 2 j   → X 4 = W4 x =   −2    − 2 − 2 j 

1.2

N 2

W49 = j

2

0 1 W =e

−j

2π N

Hubungan DFT dengan Spektrum

Tujuan Belajar 3 Peserta dapat menghubungkan DFT dengan deret Fourier untuk sinyal periodik. Misalkan xp(n) adalah sinyal periodik dengan perioda N, maka dapat dinyatakan

V-2


N −1

x p ( n ) = ∑ Ck e

 k  j 2π   n N

k =0

 k 

− j 2π   n 1 N −1 di mana Ck = ∑ x p (n)e  N  N n=0 bila ambil x(n) = xp(n) untuk n = 0, …N-1

maka Ck =

1 N

N −1

∑ x ( n )e

 k  − j 2π   n N

(satu perioda)

yang tidak lain adalah X(k).

n=0

Tujuan Belajar 4 Peserta dapat menghubungkan DFT dengan spektrum dari sinyal aperiodik. Bila x p (n) =

∞

∑ x(n − lN )

→ xp(n) periodik dengan periode N

l = −∞

 k 

∞ − j 2π   n  2π  X k  = ∑ x ( n )e  N   N  n= −∞

= ... +

−1

∑ x ( n )e

k  − j 2π   n N

n=− N

=

∞ lN + N −1

∑∑

x ( n )e

N −1

+ ∑ x ( n )e

 k  − j 2π   n N

+ ...

n =0

 k  − j 2π   n N

l = −∞ n =lN

k 

[

]

N −1  ∞  − j 2π   n = ∑  ∑ x(n − lN )e  N  = FT x p (n) ω =2πk / N n = 0 l = −∞ 

 x ( n) 0 ≤ n ≤ N − 1 bila xˆ (n) =  p otherwise  0 maka FT ( x(n)) ω = 2πk / N = X ( 2Nπ k ) = DFT [xˆ (n)] = X (k ) jadi x(n) → x p (n) → xˆ (n)

hanya bila x(n) finite duration L ≤ N maka x(n) = xˆ (n) sehingga IDFT {X(k)} = x(n)

V-3


1.3

Hubungan DFT Dengan Transformasi z Tujuan Belajar 5 Peserta dapat menghubungkan DFT dengan transformasi z dari sinyal (Langrange interpolator). X (k ) = X ( z )

z =e

j 2π k n N

bila durasi x(n) ≤ N maka N −1

X ( z ) = ∑ x ( n) z − n n=0

=

1− z −N N

N −1

X (k )

∑ 1− e k =0

j 2π

k N

z −1

X (k ) 1 − e − jωN N −1 → X (ω ) = X ( z ) z =e jω = ∑ − j (ω − 2πk / N ) N k =0 1 − e → Lagrange Interpolation

2 Sifat DFT Tujuan Belajar 6 Peserta mengerti dan dapat memanfaatkan sifat linier, periodik dan simetri sirkular. Sifat linier : Jika x1(n) ß N-DFT à X1(k) dan x2(n) ß N-DFT à X2(k) maka untuk sebarang konstanta a1 dan a2 real atau kompleks a1.x1(n) + a2.x2(n) ß N-DFT à a1.X1(k) + a2.X2(k) Sifat periodik : Jika x(n) ß N-DFT à X(k) maka x(n + N) = x(n) untuk semua n X(k + N) = X(k) untuk semua k Sifat simetri sirkular

V-4


3 Filter Menggunakan DFT Tujuan Belajar 7 Peserta dapat melakukan filtering membandingkannya dengan konvolusi.

linier

dengan

x(n) ↔ X(ω) h(n) ↔ H(ω) y(n) ↔ Y(ω) X(ω) à H(ω) àY(ω)=H(ω)X(ω) Assumsikan FIR dan Finite duration Let : x(n) = 0, n < 0 dan n ≥ L → durasi L h(n) = 0, n < 0 dan n ≥ M → durasi M Y(ω) = H(ω) X(ω)

durasi : L + M- 1

Bila Y(ω) disample maka sampling harus N ≥ L + M -1  2πk  IDFT agar y  ←→ y (n)  N  maka Y (k ) = Y (ω ) ω = 2πk

k = 0, …, N-1

N

→ Y (k ) = X (k )H (k ), ↓ ↓ zero padding IDFT → Y (k ) ← → y (n)

k = 0,..., N − 1 N ≥ L + M +1

Contoh : FIR : h(n) = {1, 2, 3} X(n) = {1, 2, 2, 1} Cari output dengan menggunakan DFT dan IDFT L = 4, M =3 → N = 6 Pilih N = 8 (agar sesuai dengan FFT) 7

H ( k ) = ∑ k ( n )e

− j 2π ( k8 )n

n=0

V-5

DFT,

dan


H (k ) = 1 + 2e

X (k ) =

− j 2π

k 8

7

+ 3e

∑ h ( n)e

− j 2π

k 4

+ 2e

− j 2π

3k 8

, k = 0,...,7

k − j 2π   n 8

n=0

= 1 + 2e

− jπ

k 8

+ 2e

− jπ

k 4

+ 2e

− jπ

3k 8

, k = 0,...,7

4+3 2  2+ 2  + j   2  2   4−3 2  2− 2  X (3) = + j   2  2   4−3 2  2− 2  X (5) = + j   2  2  4+3 2  2+ 2  X (7 ) = + j   2  2  H (1) = 1 + 2 − j 3 + 2

X ( 0) = 6

X (1) =

X ( 2) = − 1 − j X ( 4) = 0 X ( 6) = − 1 + j

H ( 6) = − 2 + j 2

( H (3) = (1 − H (5) = (1 − H (7) = (1 +

Y(k) = H(k) X(k) Y(0) = 36 Y(2) = j4 Y(4) = 0 Y(6) = -j4

Y(1) = -14.07 - j17.48 Y(3) = 0.07 + j0.515 Y(5) = 0.07 - j0.515 Y(7) = -14.07 + j17.48

H ( 0) = 6 H (2) = −2 − j 2 H ( 4) = 2

) ( 2 ) + j (3 − 2 ) − j (3 − 2 ) + j (3 +

) 2) 2) 2)

→ IDFT 7

y ( n) = ∑ Y ( k )e

k j 2π   n 8

n = 0, 1, …,7

k =0

→ y(n) = {1, 4, 9, 11, 8, 3, 0, 0} ↓↓ zeropad akibat 8 point → seakan lebih sukar dari konvolusi tetapi akan menguntungkan bila M > 40-43 → aliasing terjadi bila N < M + L -1 Tujuan Belajar 8

V-6


Peserta dapat melakukan filtering linier dengan DFT, untuk sinyal yang panjang, melalui metoda overlap-save dan overlap-add. Untuk melakukan filtering sinyal panjang dapat dilakukan dengan cara Block-by-Block - Overlap-save method - Overlap-odd method Asumsi FIR → durasi M Blok → durasi L Asumsi L >> M • Metoda overlap-save N = L + M -1 → N point DFT dan IDFT M-1 x(n)

Old

L New Data

← → X (k ) N − DFT

New x(n)

Untuk blok -m

YˆM (k ) = H (k )M X M (k )

IDFT → h(n)

k = 0, 1,L-1 …, N-1

→ H (k ) yˆ m (n) = { yˆ m (0), yˆ m (1),..., yˆ m ( M − 1), yˆ m ( M ),..., ← yˆ m ( N− 1)} N − DFT

Zero Padding

↓ M-1 point datang dari old data → buang

↓ L hasil konvolusi

Untuk blok m+1 - ambil M-1 point terakhir di blok m untuk digunakan sebagai old data pada bagian berikut - ulangi x1(n) = {0, 0, …0, x(0), x(1), …x(L-1)} •

Overlap-add Method

4 Fast Fourier Transform (FFT) Tujuan Belajar 9 Peserta mengerti konsep FFT dan butterfly. Kebutuhan kalkulasi DFT N −1

X (k ) = ∑ x(n)W n=0

kn N

WN = e

−j

2π N

V-7

= cos

2π 2π − j sin N N


karena x(n) = xr(n) + jxI(n) bisa bernilai kompleks, maka X(k) = XR(k) + jXI(k) N −1

k k   1. X R (k ) = ∑  xr (n) cos 2π n + xI (n) sin 2π n  N N  n =0  N −1 k k   2. X I (k ) = −∑  xR (n) sin 2π n − xI (n) cos 2π n  N N  n =0 

→ perlu → 2N2 evaluasi trigonometric function + → 4N2 real multiplications + → 4N(N-1) real addition + → sejumlah indexing + addressing operators → Sering disebut O(N2) k+ N

→ Gunakan fakta : WN 2 = −WNk (simetri) untuk menekan komputasi

k + N2

WN

= WNk

⇒ Fast algorithms tersedia untuk N = r1, r2, …rv di mana {rj} = prime

Tujuan Belajar 10 Peserta dapat menjelaskan FFT Radix-2 desimasi dalam waktu. •

Radix-2 FFT] - Kasus khusus N = r x r x r x … xr = rv - R =2 → radix-2 FFT ⇒ N = 2v Decimation in Time FFT x(n) ← → X (k ) 1.

N −1 x ( n) 2 f 2 (n) = x(2n + 1) bagi 2 sequences f1 , f 2 f1 (n) = x(2n)

n = 0,1,...,

⇒ f1 dan f2 diperoleh melalui desimasi x(n)

x(n F1(n) F2(n)

V-8


N −1

X (k ) = ∑ x(n)WNkn

2.

k = 0, 1, …, N-1

n=0

=

∑ x(n)W

n − even

kn N

m =0

kn N

n − odd

N −1 2

N −1 2

= ∑ x(2m)W

∑ x(n)W

+

2 mk N

+ ∑ x(2m + 1)WNk ( 2 m+1) m =0

namun WN2 = WN / 2 , maka N −1 2

X (k ) = ∑ f1 (m)WN 2 + W km

m =0

N 2

k N

−1

∑f

m=0

2

(m)WNk2( 2 m+1)

X (k ) = F1 (k ) + W F2 (k ) k = 0,1,...N − 1 di mana F1(k) : N/2 point DFT dari f1(m) F2(k) : N/2 point DFT dari f2(m) k N

Karena F1(k) dan F2(k) periodik, dengan perioda N/2, F1(k+N/2) = F1(k) dan F2(k+N/2) = F2(k) k + N2

Juga WN

= −WNk , maka X (k ) = F1 (k )+ WNk F2 (k ) k = 0, …(N/2)-1 N X (k + ) = F1 (k )− WNk F2 (k ) k= 0, …(N/2)-1 2

G1 (k ) = F1 (k ) G2 (k ) = WNk F2 (k )

Bila

X (k ) = G1 (k )+ G2 (k )   2 − po int DFT N X (k + ) = G1 (k ) − G2 (k ) 2  Lanjutkan

f1

V11 (n) = f1 (2n) V12 (n) = f1 (2n + 1)

N po int s 4 N po int s 4

N po int s 4 f2 N V22 (n) = f 2 (2n + 1) po int s 4 N F1 (k ) = V11 (k ) + W NkV12 (k ) k ⇒ po int s 2 4 V21 (n) = f 2 (2n)

V-9


F1 (k + N4 ) = V11 (k ) − W NkV12 (k ) k ⇒ 2

N po int s 4

N po int s 2 4 N F2 (k + N4 ) = V21 (k ) − W NkV22 (k ) k ⇒ po int s 2 4

F2 (k ) = V21 (k ) + W NkV22 (k ) k ⇒

di mana

•

vij ← → Vij (k )

N/4 DFT point → O(nlogn)

Ilustrasi untuk 8 samples V11(n) = f1(2n)= x(4n) = {x(0), x(4)} V12(n) = f1(2n+1) = x(2(2n+1)) = x(4n+2) ={x(2), x(4)} V21(n) = f2(2n) = x(2(2n+1)) = x(4n+2) = {x(1), x(5)} V22(n) = f2(2n+1) = x(2(2n+1)+1) = x(4n+3) = {x(3), x(7)}

Tujuan Belajar 11 Peserta dapat menjelaskan FFT Radix-2 desimasi dalam frekuensi.

V-10

Bab 5: Discrete Fourier Transform dan FFT

Recommend Documents