上海交通大学：《数字信号处理 Digital Signal Processing（B）》教学资源_Handouts_ch9 DFT

Digital Signal Processing 主讲：张君 上文大兽

Digital Signal Processing 主讲：张君

Review Digital Signal Processing--DFT/FFT Algorithms The DTFT provides the frequency-domain (w) representation for absolutely summable sequences. The z-transform provides a generalized frequency- domain (z)representation for arbitrary sequences. Two features in common: Defined for infinite-length sequences Functions of continuous variable (w or z) From the numerical computation viewpoint,these two features are troublesome because one has to evaluate infinite sums at uncountably infinite frequencies. In other words,the DTFT and the z-transform are not numerically computable transform. 上游充通大￥

Review Digital Signal Processing—— DFT/FFT Algorithms  The DTFT provides the frequency-domain (w) representation for absolutely summable sequences.  The z-transform provides a generalized frequency￾domain (z) representation for arbitrary sequences.  Two features in common: Defined for infinite-length sequences Functions of continuous variable (w or z) From the numerical computation viewpoint, these two features are troublesome because one has to evaluate infinite sums at uncountably infinite frequencies.  In other words, the DTFT and the z-transform are not numerically computable transform

Introduction Digital Signal Processing--DFT/FFT Algorithms Therefore we turn our attention to a numerically computable transform. It is obtained by samp/ing the DTFT transform in the frequency domain (or the z-transform on the unit circle). We develop this transform by analyzing periodic sequences. 女 From FT analysis we know that a periodic function can always be represented by a linear combination of harmonically related complex exponentials (which is form of sampling). This give us the Discrete Fourier Series representation. We extend the DFS to finite-duration sequences,which leads to a new transform,called the Discrete Fourier Transform. 上海充通大

Introduction Digital Signal Processing—— DFT/FFT Algorithms  Therefore we turn our attention to a numerically computable transform.  It is obtained by sampling the DTFT transform in the frequency domain (or the z-transform on the unit circle).  We develop this transform by analyzing periodic sequences.  From FT analysis we know that a periodic function can always be represented by a linear combination of harmonically related complex exponentials (which is form of sampling).  This give us the Discrete Fourier Series representation.  We extend the DFS to finite-duration sequences, which leads to a new transform, called the Discrete Fourier Transform

Introduction Digital Signal Processing--DFT/FFT Algorithms The DFT avoids the two problems mentioned above and is a numerically computable transform that is suitab/e for computer implementation. The numerical computation of the DFT for long sequences is prohibitively time consuming. Therefore several algorithms have been developed to efficiently compute the DFT. These are collectively called fast Fourier transform (or FFT)algorithms. 上游充通大￥

Introduction Digital Signal Processing—— DFT/FFT Algorithms The DFT avoids the two problems mentioned above and is a numerically computable transform that is suitable for computer implementation. The numerical computation of the DFT for long sequences is prohibitively time consuming. Therefore several algorithms have been developed to efficiently compute the DFT. These are collectively called fast Fourier transform (or FFT) algorithms

Dirichlet Conditions Digital Signal Processing--DFT/FFT Algorithms f must be absolutely integrable over a period f must have a finite number of extrema in any given bounded interval,i.e.there must be a finite number of maxima and minima in the interval. f must have a finite number of discontinuities in any given bounded interval,however the discontinuity cannot be infinite. These three conditions are satisfied if f is a function of bounded variation over a period. 上游充通大

Dirichlet Conditions f must be absolutely integrable over a period f must have a finite number of extrema in any given bounded interval, i.e. there must be a finite number of maxima and minima in the interval. f must have a finite number of discontinuities in any given bounded interval, however the discontinuity cannot be infinite. These three conditions are satisfied if f is a function of bounded variation over a period. Digital Signal Processing—— DFT/FFT Algorithms

FS Digital Signal Processing--DFT/FFT Algorithms x(t)=ao+a cosst+az cos22t+...+b sint+b2 sin2t+.. d+(d cosn+b,sinnt) a. x(t)dt a,= x(t)cosn tdt bn= Clo+T x(t)sinntdt 上游充通大

Digital Signal Processing—— DFT/FFT Algorithms FS 0 1 1 2 1 1 1 2 1 x t a a t a t b t b t ( ) cos cos 2 ... sin sin 2 ...            0 1 1 1 ( cos sin ) n n n a a n t b n t         0 0 0 1 ( ) t T t a x t dt T    0 0 1 2 ( )cos t T n t a x t n tdt T     0 0 1 2 ( )sin t T n t b x t n tdt T    

FS RS Digital Signal Processing--DFT/FFT Algorithms x(t)=d+(a cosnt+bsin n2t) n= b=sinm2 n= =d+c(cosp cosnt-sinp sinn!) n= =C+∑ccos(n2t+p,) n- ao Co cn=va,"+b2 -b an =Cn cos pr =-arctan b cos br =-Cn sin pn 上游充通大粤

Digital Signal Processing—— DFT/FFT Algorithms FS 0 1 1 1 ( ) ( cos sin ) n n n x t a a n t b n t         2 2 0 1 1 2 2 2 2 1 ( cos sin ) n n n n n n n n n a b a a b n t n t a b a b             0 1 1 1 (cos cos sin sin ) n n n n a c n t n t           0 1 1 cos( ) n n n c c n t         0 0 a c  2 2 n n n c a b   arctan n n n b a    2 2 sin n n n n b a b     2 2 cos n n n n a a b    cos n n n a c   sin n n n b c   

FS Digital Signal Processing--DFT/FFT Algorithms ∑c,cos2f+n,)=∑c.(eao+eao) n=1 c em) n=l 00 n=12 00 n=1 n= 00 00 =∑X(n2)e+∑X(-n2)ear n=l =∑X(n2)emar+∑Xn2,)ear n=l X(n2)=K(n2em=号c,em 1X2=X(-n2=c, X(-n2 )=X(-n)e=c,e 上游充通大￥

FS Digital Signal Processing—— DFT/FFT Algorithms 1 1 ()() 1 1 1 1 cos( ) ( ) 2 n n j n t j n t n n n n n c n t c e e                   1 1 1 1 1 1 ( ) ( ) jn t jn t n n X n e X n e               1 1 1 1 ( ) 2 n n jn t jn t j j n n c e e e e            1 1 1 1 1 1 2 2 n n j j jn t jn t n n n n c e e c e e               1 1 1 1 1 1 ( ) ( ) jn t jn t n n X n e X n e             1 1 1 ( ) ( ) 2 n n j j X n X n e c en       1 1 1 ( ) ( ) 2 n n j j X n X n e c en           1 1 1 ( ) ( ) 2 X n X n c      n

FT Digital Signal Processing--DFT/FFT Algorithms x(t)=∑Xen=∑Xn22mr 1=-00 X,=2)=%0mh •T/2 imX。=m(e T→00 X TX= X.=2n 天 21 X(j)="x(t)edi 上游充通大

Digital Signal Processing—— DFT/FFT Algorithms FT 1 1 1 ( ) ( ) jn t jn t T n n n x t X e X n e            1 / 2 1 / 2 1 ( ) ( ) T jn t n T T X X n x t e dt T        1 / 2 / 2 lim lim ( ) T jn t n T T T T TX x t e dt        1 1 2 n n n X X TX f     ( ) ( ) j t X j x t e dt       

FT Digital Signal Processing--DFT/FFT Algorithms x0=立0emdk T/2 T- 21 0-立2@e x(t)→x(t)n21→2， 21>d2 e)-小2元 )=2元 上游充〔大学

Digital Signal Processing—— DFT/FFT Algorithms FT 1 1 / 2 / 2 1 ( ) [ ( ) ] T jn t jn t T T T n x t x t e dt e T          1 2 T    1 1 / 2 1 / 2 ( ) [ ( ) ] 2 T jn t jn t T T T n x t x t e dt e            ( ) ( ) T x t x t  1 n   1 ， ， ，   d 1 ( ) [ ( ) ] 2 j t j t x t x t e dt e d             1 ( ) ( ) 2 j t x t X j e d        