3 Discrete Fourie Transform: DFT DFT 3.1 3.1.1 x(n) X(e jω ) X(e jω )= x(n)e jωnt (3.1) n= X(e jω ) N X(k) ωt f 2π f s N X(k) =X(e j2πk/n )= x(n)e j2πnk/n, k N 1 (3.2) n= X(k) δ X(e jω )= X(k)δ(ωT 2πk N ) (3.3) k= X(e jω ) X(e jω ) x(n)
x(n) = 1 2π 2π = 1 2π 2π 3.1 59 X(e jω )e jωnt dωt (3.4) [ ] 2πk X(k)δ(ωT N ) e jωnt dωt k= (3.5) ωt 2π k k = N 1 x(n) = 1 [ 2π ] X(k)δ(ωT 2πk 2π N ) e jωnt dωt = 1 2π k= = 1 2π k= k= 2π X(k) δ(ωt 2πk N )ejωnt dωt X(k)e j 2πnk N (3.6) 1 2π 1 N 1/2π 1/N x(n) = 1 N k= X(k)e j 2πnk N (3.7) X(e jω ) x(n) X(k),k = N 1 x(n) X(k) X(k) = n= x(n)e j2πnk/n (3.8) (3.7) X(k) x(n) x(n) = 1 N = 1 N k= k= X(k)e j 2πnk N [ m= x(m)e j2πmk/n ] e j 2πnk N
6 3. [ = m= x(m) 1 N k= e j2π(n m)k/n) ] = x(n) (3.9) [] m = n 1 m n m = n x(n) 3.1.2 X(k) = x(n) = 1 N n= x(n)e j2πnk/n, k N 1 (3.1) k= X(k)e j 2πnk N, n N 1 (3.11) 3.1.3 X(e jω ) x(n) (3.11) X(k) x(n) (3.11) X(k) (3.2) [ x(n) = 1 ] x(m)e j2πkm/n e j2πkn/n (3.12) N = k= k= m= m= x(m) 1 N k= 1 e j2πk(m n)/n = N x(n) = e j2πk(m n)/n (3.13) 1, m n = rn, r, m n rn (3.14) r= x(n + rn) (3.15)
3.1 61 x(n) x(n) N x(n) N T L = NT fhz N = f s / f T L = NT = N f s = 1 f (3.16) x(n) ( ) f 1/ f x(n) x(n) 3.1 x(n) T (= MT) M M<N M>N x(n + rn) x(n) ~ x ( n ) T = MT M M > N n T L = NT M N N + M M < N n 3.1 3.1 3.1.4
62 3. 3.1 (DFT) = T =1/ f =1/T (= f s )Hz = fhz (3.15) x(n + rn) 3.1 N x(n) T L = NT x(n) n M T = MT T = MT < T L = NT (3.17) T L =1/ f f < 1 T (3.18) M<N (3.19) 3.1.5 x(t) t T X(jω) f f c f s f s > 2f c (3.2) T =1/f s T T = 1 < 1 (3.21) f s 2f c t T x(t)
3.1 63 x(),x(t ) M +1 T = MT M M = T T > 2T f c (3.22) f f < 1 T (3.23) 1 N N>M (3.24) (3.21) (3.23) 3.2 3.2 (DFT) T<1/2f c = T =2f c Hz f <1/T Hz T =.1 f c =3kHz f s > 2f c =6kHz T <1/2f c =.166msec f <1/T =1Hz M >2T f c = 6 N >M
64 3. 3.1.6 3.2 (a) x(t) X(jω) Fourier Transform: FT (b) x(n) X(e jω ) Fourier Transform: FT (c) x(t) X(k) Fourier Series: FS (d) x(n) X(k) Discrete Fourier Series: DFS (e) x(n) X(k) (d) Discrete Fourier Transform: DFT
3.1 65 3.2
66 3. 3.2 x(n) X(k) n N 1 k N 1 x(n) X(k) X(k) = n= x(n) = 1 N x(n)e j2πnk/n, k N 1 (3.25) k= X(k)e j 2πnk N, n N 1 (3.26) 3.2.1 1 x 3 (n) = ax 1 (n)+bx 2 (n) (3.27) X 3 (k) =ax 1 (k)+bx 2 (k) (3.28) 2 x(n) n N 1 N y(n) =x((n k)) N, n N 1 (3.29) ((n)) N N N =5,k =3y(n) =x((n 3)) 5 y() = x(( 3)) 5 = x(2) y(1) = x((1 3)) 5 = x(3) y(2) = x((2 3)) 5 = x(4) y(3) = x((3 3)) 5 = x() y(4) = x((4 3)) 5 = x(1)
3.2 67 3.3?? 3.3 y(n) =x((n 3)) 5 3 N 3.4??? 3.4 4 x(n) DFT X(k) x(n m) DFT e j2πkm/n X(k) X(k + l) DFT e j2πln/n x(n)
68 3. 3.2.2 DFT y 3 (n) = m= x 1 ((m)) N x 2 ((n m)) N, n N 1 (3.3) Y 3 (k) =X 1 (k)x 2 (k), k N 1 (3.31) y 3 (n) =x 1 (n)x 2 (n), n N 1 (3.32) Y 3 (k) = l= X 1 ((l)) N X 2 ((k l)) N, k N 1 (3.33) 1.2 N =4 y() x 2 () x 2 (3) x 2 (2) x 2 (1) x 1 () y(1) x = 2 (1) x 2 () x 2 (3) x 2 (2) x 1 (1) y(2) x 2 (2) x 2 (1) x 2 () x 2 (3) x 1 (2) y(3) x 2 (3) x 2 (2) x 2 (1) x 2 () x 1 (3) (3.34) 3.3 3.3.1 y(n) = m= h(m)x(n m) (3.35) 3.5 N =3
y() y(1) y(2) y(3) y(4). = 3.3 69 h() x() h(1) h() x(1) h(2) h(1) h() x(2) (3.36) h(2) h(1) h() x(3) h(2) h(1) h() x(4)..... 3.5 FIR DFT DFT DFT 3.6 DFT N 3.6 DFT
7 3. DFT (3.36) (3.34) 3.3.2 x(n) n N 1 h(n) n M 1 y(n) n N + M 2 N + M 1 DFT x(n) =,N n N + M 2 (3.37) h(n) =,M n N + M 2 (3.38) 3.7 DFT 3.7 DFT X(k) = H(k) = N+M 2 n= N+M 2 n= x(n)e j2pikn N +M 1, k N + M 2 (3.39) h(n)e j2pikn N +M 1, k N + M 2 (3.4) Y (k) = H(k)X(k), k N + M 2 (3.41) y(n) = N+M 2 1 Y (k)e j2pikn N +M 1, n N + M 2(3.42) N + M 1 k=
3.3 71 N + M 1 3.3.3 DFT h(n) M 1 Overlap-add method x(n) N M 1 N + M 1 k x k (n) y k (n) x k (n) h(n) y k (n) x(n), kn n (k +1)N 1 x k (n) = (3.43), (k +1)N n (k +1)N + M 1 x(n) = x k (n) (3.44) y(n) = = = k= M 1 m= k= h(m) [ M 1 m= x k (n m) k= h(m)x k (n m) ] y k (n) (3.45) k= y k (n) y k+1 (n) (k +1)N n (k +1)N + M 1 3.8 2 Overlap-save method x(n) N + M 1 M 1 N +2(M 1) DFT
72 3. 3.8 DFT x(n), kn n (k +1)N + M 1 x k (n) =, (3.46) y k (kn + l) = M 1 m= x k (kn + l m)h(m), l N +2(M 1)(3.47) y k (kn + l) l M 1 N + M n N +2(M 1) y k (n),kn + M n (k +1)N + M 1 3.9 DFT N + M 1 N +2(M 1) 3.4 1. x(t) x(n) x(t) T x(n) f s = Hz x(t) x(n) X(jω) X(e jω ) X(e jω ) X(jω) Hz
3.4 73 3.9 DFT X(e jω ) Hz X(jω) f c Hz f c Hz X(jω) f s X(e jω ) fhz X(k) x(n) x(n) N = x(n) x(n) x(t) t = T x(),x(t ) f (1)T (2)1/T (3)f s (4)1/f s (5)2f c <f s (6)2f c >f s (7) + r= x(n + rn) (8) f (9)1/ f (1) f >1/T (11) f < 1/T (12) (13) (14) (15)f s / f (16) f/f s (17)NT (18)T/N
74 3. 2. DFT) x(t) T x(n) =x(nt ) x(n) X(e jω ) Hz f s T x(t) X(e jω ) fhz x(n) x(t) t = T x(),x(t ) f 1 f s N = M +1 M N (1)T (2)1/T (3)f s (4)f s /2 (5)2f s (6)f s / f (7) f/f s (8)T /T +1 (9)M <N (1)M >N (11) f (12)1/ f (13)T < 1/ f (14)T > 1/ f (15)T /T (16)T/T 3. DFT) x(t) t 1 x(),x(1 ) X(jω) 4kHz 4kHz X(jω) = x(t) f s x(n) X(e jω ) (a) (b) (c) f s f s =8kHz M +1 f 1 N f
3.4 75 (d) (e) (f) (g) x(n) X(e jω ) X(k) x(n) N f N 2 N x(n) x(n) x(n) x(n) x(n) 4. h(n),n = 3 x(n),n = 3 DFT H(k),k = 3 X(k),k = 3 Y (k) = H(k)X(k),k = 3 IDFT y(n),n= 3 y(n),n= 3 h(n),n= 3 x(n),n = 3 (3.34) 5. h(n),n = 2 x(n),n = 3 y(n) y(n) h(n) x(n) DFT H(k) X(k) Y (k) =H(k)X(k) Y (k) IDFT y(n) h(n) x(n) DFT 6. h(n),n= M 1 x(n),n= y(n) y(n) h(n) x(n) DFT H(k) X(k) Y (k) =H(k)X(k) Y (k) IDFT y(n) x(n) N DFT
76 3. 3.5 3.5.1 3.1 T x(t) x(t) 3.1 T x(t) =x(t + nt ), T >,n (3.48) T x(t) = a k e jkωt, ω = 2π (3.49) T k= kω a k a k = 1 T x(t)e jkωt dt (3.5) T (3.49) x(t) a k 1 T = T m= a m 1 T m= T a m e jmωt e jkωt dt (3.51) e j(m k)ωt dt
3.5 77 = a k 1 T e j(m k)ωt 1, m = k dt = T, m k (1) (3.52) (3.53) T x N (t) = x(t) 2 dt < (3.54) N k= N a k e jkωt (3.55) N E N = T x(t) x N (t) 2 dt (3.56) lim E N = (3.57) N (2) T x(t) dt < (3.58) t 3.11 [ T 1,T 1 ] x(t) [, ] x(t) x(t) (3.49) (3.5) x(t) = a k e jkωt (3.59) k= a k = 2 sin kω T 1 kω T (3.6)
78 3. 3.11 ω = 2π T T T 1 a k 3.12 T a k T /T 1 T x(t) x(t) 3.12 (a)t /T 1 =4 (b)t /T 1 =8 (c)t /T 1 =16 lim x(t) =x(t) (3.61) T
3.5 79 a k x(t) a k = 1 T T/2 T /2 = 1 T/2 x(t)e jkωt dt T T /2 x(t)e jkωt dt (3.62) = 1 x(t)e jkωt dt (3.63) T X(jω)= (3.63) x(t)e jωt dt (3.64) a k = 1 T X(jkω ) (3.65) (3.59) x(t) = 1 T k= X(jkω )e jkωt (3.66) ω =2π/T x(t) = 1 X(jkω )e jkωt ω (3.67) 2π k= 3.13 X(jω )e jωt ω T ω x(t) x(t) 3.13
8 3. x(t) = 1 X(jω)e jωt dω (3.68) 2π (3.64) (3.68) X(jω)= x(t) = 1 2π x(t)e jωt dt (3.69) X(jω)e jωt dω (3.7) 3.5.2 X a (s) = x(t)e st dt, s = σ + jω (3.71) σ+j x(t) = 1 X(s)e st ds (3.72) 2πj σ j x(t) x d (t) x d (t) (3.71) x d (t) = x(kt)δ(t kt) (3.73) X d (s) = = = k= k= k= δ(t) δ(t) =,t (3.74) x d (t)e st dt x(kt) δ(t kt)e st dt x(kt)e skt (3.74) δ(t)dt =1 (3.75) z = e st (3.76)
3.5 81 X d (s) = k= x(kt)z k (3.77) x(kt) T x(kt) = 1 2πj C z s (3.76) X(z)z k 1 dz (3.78) dz = Te st = Tz (3.79) ds z 1 dz = Tds (3.8) x(kt) = 1 2πj a(kt) = 1 2πj σ+jπ/t σ jπ/t σ+jπ/t σ jπ/t X(e st )e skt Tds (3.81) X(e st )e skt ds (3.82) X(e st )= Ta k (kt)e skt (3.83) k= Ta k (kt)e skt 3.14 lim T X(esT )= a(t)e st dt (3.84) X(e st )=X d (s) (3.85) X a (s) X d (s) 3.15
82 3. 3.14 3.15 X a(s) X d (s) lim T X(esT )=X a (s) (3.86) (3.84) (3.86) X a (s) = a(t)e st dt (3.87) (3.82), 1 σ+π/t lim a(kt) =a(t) = lim X(e st )s st dt (3.88) T T 2πj = 1 2πj (3.72) σ+ σ σ π/t X a (s)s st dt (3.89)
3.5 83 x(t) =a(t) (3.9) (3.87) (3.89) X a (s) = x(t) = 1 2πj x(t)e st dt (3.91) σ+ σ j X a (s)e st ds (3.92) X(jω) = x(t) = 1 2π x(t)e jωt dt (3.93) X(e jωt )= x(n) = 1 2π n= π π X(jω)e jωt dω (3.94) x(n)e jωnt (3.95) X(e jωt )e jωnt dωt (3.96) T X(s) = x(t) = 1 2πj X(z) = x(t)e st dt (3.97) σ+ n= x(n) = 1 2πj σ j X(s)e st ds (3.98) x(n)z n (3.99) C X(z)z n 1 dz (3.1)
84 3. T 3.5.3 x(t) X(s) dx(t) sx(s) (3.11) dt t x(τ)dτ 1 X(s)+x() (3.12) s ae s kt a s s k (3.13)