幻灯片 1

Digital Signal Processing mailfzh@nwpu.edu.cn /gary/

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

1. FT FT (FS) (FT) ( ) xt () Dirichlet (, ), 1 T () = ( Ω), ( Ω ) = () T T jkωt jkωt xt X k e X k xte dt e jkω t k = Ω, kω, Ω T = π Ω, T x( t) T,

xt () xt () dt< jωt, X( jω ) = x( t) e dt 1 jωt xt () = X( jω) e dω, Ω= π f π xt () t, X( jω) Ω, xt (), FS X( kω ), k FT X( jω), π X( kω ) T Ω T T Ω T T jk t lim TX ( kω ) = lim = lim x( t) e dt = X ( jω)

Parseval ( ),FS 1 T 1 T * 1 T * x = () () () () ( ) T = T T = T T Ω T k = 1 = Ω = Ω Ω = Ω jkωt P x t dt x t x t dt x t X j e dt T * jkω t * X ( j ) x( t) e dt X ( j ) X( k ) X( k ) T k T = k= k= 1 T Px = x() t dt X( k ) T = Ω T,FT k = 1 E = x x() t dt = X( j ) d π Ω Ω

, FT, FT ( ) ( ) j Ω t jkω t X j x t e dt X ( k ) e e j Ω t dt k = Ω = = Ω k = ( ) X( k ) e dt = Ω ± j Ω k Ω t jxy e dx= πδ ( y) X( jω ) = π X( kω ) δ( Ω kω ) k = Ω Drac FT FS FT ( )

xt e X j πδ jωt () = ( Ω ) = ( Ω Ω ) [ ] xt = Ω t= e e j X jω = jπ δ Ω+Ω δ Ω Ω jωt jωt () sin ( ) ( ) ( ) [ ] xt = Ω t= e + e X jω = π δ Ω+Ω + δ Ω Ω jωt jωt () cos ( ) ( ) ( ) xt e X j k jkωt () = ( Ω ) = π δ( Ω Ω ) k= k= π pt () = δ( t nt) P( jω ) = δ( Ω kω) T n= k=

() = δ ( ), pt t nt T pt () = δ ( t nt) = Pk ( Ω ) e jkωt jkωt P k p t e dt δ t e dt n= n= k= 1 T 1 T 1 T T T T T ( Ω ) = () = () = n= 1 jkωt δ( t nt) = e, Ω = π T T k= jkωt e π δ ( Ω kω ) k = k = jkω t π δ( t nt) δ Ω kω T n= k= ( )

k= n= n= e jkω t π δ( Ω kω ) k= π δ( t nt) δ( Ω kω) T k= 1 jkωt δ ( t nt) = e, Ω = π T T k= k= 1 δ( Ω kω ) = e, T = Ω jωnt π Ω n=

(DTFT) xn ( ) DTFT ( ) X e = n= x( n) e n j ( ω ) xn ( ) X e ω T = π j( ω+ π) j( ω+ π) n jπn n ( ) = ( ) = ( ) = ( ) X e xne e xne X e n= n=

(DTFT) X( jω ) = π X( kω ) δ( Ω kω ) k = X( kω ) T = π Ω T Ω x( t)

( ) 1 CFT x a ( t ) X a ( f ) x a t 1 j πft ( t) = X a ( f ) e df jωt π X a( jω ) = xa( t) e dt DTFT x a ( nt ) x ( n ) 1 π n xn ( ) = X( e ) e dω π π T t n X ( e ) = X ( e n= ) x( n) e π / T π n Ω ω = Ω = f π f Z Ω T

( ) 3 (FS) x p ( t ) T 1 xp t = X kω e () ( ) jk Ω t k = 4 (DFS) t X ( k Ω 1 ) 1 T X ( kf 1 ) f Ω 1 jkωt X( kω ) = x ( ) T1 p t e dt 1 T k = ~ x ( n 1 xn ( ) = X( ke ) ) π j nk ~ X ( k t f n X( k) = x( n) e n= ) π j nk

DTFT xn ( ) = ax( n) + bx( n), 1 X( e ) = ax ( e ) + bx ( e ) j ω j ω j ω 1 y( n) = x( n) h( n) Y( e ) = X( e ) H( e ) yn xn n Ye e Xe n ( ) = ( ) ( ) = ( ) Parseval( ) y( n) = x( n) h( n) Y( e ) = X( e ) H( e ) * ( ) ( ) ( ) ( j j ym xnhn m Ye ω ) X ( e ω j = + = ) He ( ω n= n= 1 π xn ( ) = X( e ) dω π π )

DTFT xn ( ) = x xn ( ) xi ( n) = R( n) + xi( n) X( e ) = X X( e ) ω R( e ) + XI( e ) DTFT X( e ) ω X( e ) ω XR( e ) = [ xr( n)cos( ωn) + xi( n)sin( ωn) ] n= X( e ) ω X ( ) xn ( ) I e = [ xr( n)sin( ωn) xi( n)cos( ωn) ] n= xn ( ) 1 π xr( n) = XR( e )cos( ωn) XI( e )sin( ωn) dω π π 1 π xi( n) = XR( e )sin( ωn) + XI ( e )cos( ωn) dω π π

DTFT xn ( ) = x xn ( ) xi ( n) = R( n) + xi( n) X( e ) = X X( e ) ω R( e ) + XI( e ) DTFT X( e ) ω X( e ) ω XR( e ) = [ xr( n)cos( ωn) + xi( n)sin( ωn) ] n= X( e ) ω X ( ) xn ( ) I e = [ xr( n)sin( ωn) xi( n)cos( ωn) ] n= xn ( ) 1 π xr( n) = XR( e )cos( ωn) XI( e )sin( ωn) dω π π 1 π xi( n) = XR( e )sin( ωn) + XI ( e )cos( ωn) dω DCT π π

Wiener-Khinchin( ) x(n) xn ( ) 1 xn ( ) n Px ( e ) = lim X ( e ), X ( e ) = F ( x( n) ), x( n) = + 1 n > xn ( ) r ( m) m 1 rx ( m) e = lim x( n) x( n+ m) e 1 + 1 ω = lim xne ( ) xn ( + me ) + 1 m= m= n= x n= m= m j n ( n+ m) * n ( n+ m) 1 = lim xne ( ) xn ( me ) 1 + + n= m= 1 * = lim X 1 ( e ) X ( e ) + 1 = lim X 1 ( e ) = Px ( e ) +

DTFT DTFT xn ( ) = e jωt e ( Ω Ω ), X( e ) = π δ( ω ω + πk), k Z k = n Ω δ DTFT ω δ π πδ DTFT

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

. (1) ( ) ( Ω ) ( ) ( Ω ) () xt ( ) xnt ( ) X j X e (3) X j X e (4) xnt ( ) xt ( ) s s ( )

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

3. x ( nt ) x () t x () t T, T = T, Ω = π T = π T. x ( t) s jkωt xt () xt () = X( kω ) e, X( kω ) s k = π x ( nts) = x ( t) t= nt = X( k )exp( jk nt ) ( )exp( ) s Ω Ω s = X kω j kn k= k= X ( kω) Ω = π T = π T = Ω Ω X ( kω ) s k = s X( k) π X( k)exp( j kn) n [, ] [, ] x ( nts ) x( n), n [, ] s

3. Ts Ωs T ( ) Ω T/Ts== Ωs/ Ω π xn ( ) = X( k)exp( j nk) k =

3. 1 π xn ( ) = X ( k)exp( j nk) n= ~ + k = DFS X π ( k) = x ( n)exp( j nk) k = ~ + k = 1 π xn ( ) = X( k)exp( j nk) n= ~ k = DFT π X( k) = x( n)exp( j nk) k = ~ k =

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

4. DFT FT FS DTFT DFS π DFS ± j n k exp( nk)

4. DFT π X( k) = x( n)exp( j nk) k = ~ k = 1 π xn ( ) = X( k)exp( j nk) n= ~ k = π W = exp( j ), nk X( k) = x( n) W k = ~ k = 1 nk xn ( ) = X( kw ) n= ~ k =

4. DFT x(n) DFT x(n) DFS x(n)dft x(n) DTFT DFT DFT

4. DFT DTFT Z xn ( ), Z DTFT DFT n n X( z) = x( n) z = x( n)( re ) n= n= n X( e ) = x( n) e = X( z) n= z= e π X( k) = x( n) W = x( n)exp( j nk) = X( e ) nk π k n n ω= = = z Im z r =1 π k =1 Re z k= z z X( z) X( e ) X( k) π

4.DFT [ ] DFT ax ( n) + bx ( n) = ax ( k) + bx ( k) 1 1 ( ) W X x 1 W W W W nk 4 ( ) = W = W W W W W W W W W W W W ( ) ( )( ) [ X() X(1) X( 1) ] T [ x() x(1) x( 1) ] = = DFT T X = W x

4.DFT (cont.) ( ) W X 1 W W W W nk 4 ( ) = W = W W W W T [ X() X(1) X( 1) ], x [ x() x(1) x( 1) ] W W W W W W W W ( ) ( )( ) = = DFT X = W x * mk nk ( n m) k m= n R = WW R( m, n) = W W = W = k= k= m n * 1 * * R = WW = I W = W, W W 1 * DFT x = W X = WX, T

4.DFT [ ] km [ ] km DFT x( n + m) = W X ( k), DFT x( n m) = W X ( k) DTFT Parseval π π W = exp( j ) ω k, ω k 1 x( n) = X( k) n= n=

4.DFT xn ( ) hn ( ) DFT X( k) Hk ( ) xn ( ) hn ( ) yn ( ) y( nmod ) = x( n) h( n) = x( imod ) h( n imod ) ( nmod ) n i= yn ( ) = xn ( ) hn ( ), Yk ( ) = XkHk ( ) ( )

= 3 y() h() h( ) h( ) x() y(1) h(1) h() h( 1) x(1) =, h( n) 3 y() h() h(1) h() x() y() h() h() h(1) x() y(1) = h(1) h() h() x(1) y() h() h(1) h() x() y() h() h( ) h(1) x() y(1) h(1) h() h() x(1) y = = y ( ) h ( ) h ( ) h() x ( ) = Hx

yn ( ) = xn ( ) hn ( ), xn ( ) M hn ( ) yn ( ) M + h() y() h(1) h() y(1) x() hm ( ) h() ym ( 1) x(1) = y ( ) h ( ) h ( M) xm ( ) yl ( ) h ( ) y = Hx

( n) R4 ( n) x( n) h( n) (L=4) 1 x = ( n) R3 ( n) 1 3 x(m) m h = x( n) h( n) 1 1 3 x(m) m 1 1 h( m) m h( 1 m) m 1 1 h (( m)) m h (( 1 m)) m x( n) h( n) 33 1 1 1 3 4 5 n 3 33 3 1 3 x( n) h( n) n

DFT yn ( ) = xn ( ) hn ( ), xn ( ) M hn ( ) L yn ( ) M + L DFT xn ( ) hn ( ) M + L xn ( ) n=,1,,, M x ( n) = n= M, M + 1,, M + L hn ( ) n=,1,,, L h ( n) = n= L, L+ 1,, M + L xn ( ) hn ( ) [ ] 3 DFT yn ( ) = y ( n) = IDFT X ( kh ) ( k)

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

5. x(n) exp(j ) DFT π π x( n) DTFT X( e ) X ( e ) = X( e ) δω ( k) IDTFT 1 π 1 π n π n x ( n) = X ( e ) e dω X( e ) δ( ω k) e dω π = π π π 1 π 1 = X( e ) e e dω X( e ) e π = π π π π π = xn ( + m) π m= π m n ( n+ m) m= k = m= k = DFT dω

5. M x(n) exp(j ) ( ) x(n) M xn ( ) = xnr ( ) ( n), X( e ) = X ( e ) R ( e ) 1 e sin( ω ) R e R n e e e 1 sin( ω ) n n ( ) ( ) = ( ) = = = n= n= e

5. M x(n) exp(j ) ( ) x(n) M xn ( ) = xnr ( ) ( n), X( e ) = X ( e ) R ( e ) 1 e sin( ω ) R e R n e e e 1 sin( ω ) n n ( ) ( ) = ( ) = = = n= n= e sinc

5. M x(n) exp(j ) ( ) x(n) M X( e ) = X ( e ) R ( e ) π X ( e ) = X( k) sin( ω ) sin( ω ) ( ) X( e ) X( k) e

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

6. DFT \ DFT \ f \ T f T ( ) TW FW TW ifw (uncertainty principle) 14π TW = n x n x n n= ( ) ( ) fs ( ) ( ) f s f s n= TF = f X f df X f df f s

6. DFT ( sinc ) ( sinc )

1. FT FT. 3. 4. DFT 5. 6. DFT 7.

7. nk X( k) = x( n) W k =,1,, 1, W = e n= 1 nk xn ( ) = X( kw ) n=,1,,, k = ( ) ( 1) π j X k nk kn, W W = W = W k = nk ( n+ ) k n( k + ) ( ) nk nk ( n) k n( k ) = = = W W W W W nk n= r, r = n = rm W = W = W ; W = 1, W = 1, W = j r 1 1 4 r M

7. DFT 4 4=16 X() W4 W4 W4 W 4 x() 1 1 1 1 x() 1 3 1 1 X(1) x(1) W 1 4 W4 W4 W W 4 4 W 4 x(1) = = 4 6 X() W x() 1 1 1 1 x() 4 W4 W4 W 4 3 6 9 1 1 X(3) W x(3) 1 W 4 W4 W4 W4 4 W4 x(3) () (3) [ ] [ ] 1 [ ] [ ] 4 [ ] [ ] 1 [ x ) x() ] [ x(1) x(3) ] W X() 1 1 1 1 x() X() = x() + x() + x(1) + x(3) 1 1 X(1) 1 W4 W 4 x() X (1) = x() x() + x(1) x(3) W = X() 1 1 x(1) X() = x() + x() x(1) + x(3) 1 1 X(3) 1 W4 W4 x(3) X(3) = ( 4

7. Cooley Tukey FFT( Fast Fourier Transform) DFT log 4 Winograd

7. FFT (DIT) FFT = X() W () 1 1 () W x x 1 X(1) = W x(1) = 1 1 x(1) W =^M xn ( ) rk (r+ 1) k rk k rk r= r= r= r= X( K) = x( r) W + x(r+ 1) W = x( r) W + W x(r+ 1) W A( k) = x ( r) W DFT( k=,1,, -1) x ( r) = x( r), r= r= rk 1 1 Bk ( ) = x( rw ) DFT( k=,1,, -1) x( r) = x(r+ 1) rk k k=,1,, -1 X( k) = A( k) + W B( k) k X( k+ ) = A( k) W B( k)

7. FFT (DIT) FFT = X() W () 1 1 () W x x 1 X(1) = W x(1) = 1 1 x(1) W =^M xn ( ) rk (r+ 1) k rk k rk r= r= r= r= X( K) = x( r) W + x(r+ 1) W = x( r) W + W x(r+ 1) W A( k) = x ( r) W DFT( k=,1,, -1) x ( r) = x( r), r= r= rk 1 1 Bk ( ) = x( rw ) DFT( k=,1,, -1) x( r) = x(r+ 1) rk k k=,1,, -1 X( k) = A( k) + W B( k) k X( k+ ) = A( k) W B( k) A(k) x(n) DFT B(k) x(n) DFT

7. FFT (DIT) FFT = X() W () 1 1 () W x x 1 X(1) = W x(1) = 1 1 x(1) W =^M xn ( ) rk (r+ 1) k rk k rk r= r= r= r= X( K) = x( r) W + x(r+ 1) W = x( r) W + W x(r+ 1) W A( k) = x ( r) W DFT( k=,1,, -1) x ( r) = x( r), r= r= rk 1 1 Bk ( ) = x( rw ) DFT( k=,1,, -1) x( r) = x(r+ 1) rk k k=,1,, -1 X( k) = A( k) + W B( k) k X( k+ ) = A( k) W B( k) ^M DFT =

7. FFT (DIT) FFT k X( k) = A( k) + W B( k), k=,1,, -1 k X( k+ ) = A( k) W B( k), k=,1,, -1 X( k) A( k) B( k) A( k) X( k) x( n) DFT B( k) X( k) xn ( ) DFT X ( k) X ( k) X ( k) X ( k) x( n) (1) () (3) log / /4

DIT ( Decimation In Time ) x(n) x() x(4) x() x(6) x(1) x(5) x(3) x(7) C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) A() A(3) B() B(1) B() B(3) 1 3 X() X(1) X() X(3) X(4) X(5) X(6) X(7) x(n)

x(n) x() x(4) x() x(6) x(1) x(5) x(3) x(7) C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) x(n) A() A(3) x(n) B() B(1) B() B(3) 1 x(n) 3 X() X(1) X() X(3) X(4) X(5) X(6) X(7)

x() x(4) x() x(6) x(1) x(5) x(3) x(7) m= 1 m=1 m= C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) A() A(3) B() B(1) B() B(3) 1 3 M = log X() X(1) X() X(3) X(4) X(5) X(6) X(7)

x() x(4) x() x(6) x(1) x(5) x(3) x(7) C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) A() A(3) B() B(1) B() B(3) 1 3 X() X(1) X() X(3) X(4) X(5) X(6) X(7) m x ( ) m p x () m q r W x x m+ m+ ( ) 1 p () 1 q

m x ( ) m p x () m q r W x x m+ m+ ( ) 1 p () 1 q / log log = M log = M

x() x(4) x() x(6) x(1) x(5) x(3) x(7) C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) A() A(3) B() B(1) B() B(3) 1 3 X() X(1) X() X(3) X(4) X(5) X(6) X(7)

x() x(4) x() x(6) x(1) x(5) x(3) x(7) C() C(1) D() D(1) E() E(1) F() F(1) A() A(1) A() A(3) B() B(1) B() B(3) k X( k) = A( k) + W B( k), k=,1,, -1 k X( k+ ) = A( k) W B( k), k=,1,, -1 1 3 X() X(1) X() X(3) X(4) X(5) X(6) X(7) L W W, k=,1,, -1 k L

x() x(4) x() x(6) x(1) x(5) x(3) x(7) X() X(1) X() X(3) X(4) X(5) X(6) X(7) 4 1 4 6 6 3 1 1 4 5 3 5 3 5 6 7 7 7 1 1 1 1 11 11 1 1 11 11 11 11 111 111

7. FFT (DIF) FFT X(k) k X ( k) = x( n) W n= nk nr nr nr n= n= n= X( r) = x( n) W = x( n) W + x( n) W nr nr r / xnw ( ) xn ( ) W W n= n= = + + n= n= nr r / jπ r ( xn ( ) xn ( ) ) W, ( W e 1) = + + = = = gnw ( ) nr

7. FFT (DIF) FFT X(k) k X ( k) = x( n) W n= nk X( r) = g( n) W, g( n) = x( n) + x( n+ ); n= nr n(r+ 1) nr n nr n n= n= n= X(r+ 1) = x( n) W = x( n) W W + x( n) W W nr n nr r / n xnw ( ) W xn ( ) W W WW n= n= = + + n nr r/ jπ r ( xn ( ) xn ( ) ) WW, ( W e 1, W = ) = + = = n= = hnw ( ) n= nr

7. FFT (DIF) FFT X(k) k X ( k) = x( n) W n= nk X( r) = g( n) W, g( n) = x( n) + x( n+ ); n= n= nr nr ( ) n X(r+ 1) = h( n) W, h( n) = x( n) x( n+ ) W ;

7. FFT (DIF) FFT nr X( r) = g( n) W, g( n) = x( n) + x( n+ ); n= nr n X(r+ 1) = h( n) W, h( n) = ( x( n) x( n+ ) ) W; n= g( n) h( n) xn ( ) x ( n) x ( n) x ( n) x ( n) X( k) (1) () (3) log / /4

X(K) x() x(1) x() x(3) x(4) x(5) x(6) x(7) 1 3 g() g(1) g() g(3) h() h(1) h() h(4) p() p(1) q() q(1) r() r(1) s() s(1) X() X(4) X() X(6) X(1) X(5) X(3) X(7) X(k)

x() x(1) x() x(3) x(4) x(5) x(6) x(7) 1 3 g() g(1) g() g(3) h() h(1) h() h(4) p() p(1) q() q(1) r() r(1) s() s(1) X() X(4) X() X(6) X(1) X(5) X(3) X(7) m x ( ) m p x m+ ( ) 1 p x () m q r W x m+ () 1 q

DIT DIF DIT DIF x ( ) m p x m+ ( ) 1 p x ( ) m p x m+ ( ) 1 p x () m q r W x m+ () 1 q x () m q r W x m+ () 1 q x() X() x() X() x(4) X(1) x(1) X(4) x() x(6) X() X(3) x() x(3) X() X(6) x(1) X(4) x(4) X(1) x(5) X(5) x(5) X(5) x(3) X(6) x(6) X(3) x(7) X(7) x(7) X(7)

7. FFT IFFT DFT IDFT π j nk X( k) = x( n) W k =,1,, 1, W = e n= 1 nk xn ( ) = X( kw ) n=,1,,, k = r FFT W W, x( n) X( K) ( ) 1 IFFT 1 nk 1 nk 1 k= k= x( n) = X ( k) W = X ( k) W = FFT ( X ( k)) X( K) FFT 1 1 nk 1 ( n) k 1 k= k= xn ( ) = X( kw ) = X( kw ) = x'( n)

7. FFT FFT L + M x( n ) M DFT X( k ) L y( n ) : DFT IDFT Y( k ) L