Digital Signal Processing 主讲：张君 上文大兽
Digital Signal Processing 主讲：张君
FFT-Introduce Digital Signal Processing--DFT/FFT Algorithms DFT plays an important role in the analysis,design,and implementation of discrete-time signal-processing algorithms and systems.Because direct computing DFT needs N2 complex multiplication,when N is larger, computation cost is larger.Before FFT comes,it is not practical that using DFT spectrum analysis and real-time processing of signal.Until in 1965 fast computation algorithm turn up,situation didn't change (J.W.Cooley,J. W.Tukey,G.Sande). 上浒充通大
Digital Signal Processing—— DFT/FFT Algorithms FFT- Introduce DFT plays an important role in the analysis, design, and implementation of discrete-time signal-processing algorithms and systems. Because direct computing DFT needs N2 complex multiplication ， when N is larger， computation cost is larger. Before FFT comes，it is not practical that using DFT spectrum analysis and real-time processing of signal 。 Until in 1965 fast computation algorithm turn up，situation didn’t change (J. W. Coo1ey, J. W. Tukey, G. Sande)
FFT Digital Signal Processing--DFT/FFT Algorithms The discrete Fourier transform plays an important role in many applications of digital signal processing,including linear filtering,correlation analysis,and spectrum analysis.The major reason is the existence of efficient algorithms for computing the DFT. A divide-and-conquer approach in which a DFT of size N,where N is a composite number,is reduced to the computation of smaller DFTs from which the larger DFT is computed.Particularly for N=2B. A linear filtering operation on the data,this approach has two algorithms:the Goertzeland the chirp-z transform algorithms. 上游充通大
Digital Signal Processing—— DFT/FFT Algorithms FFT The discrete Fourier transform plays an important role in many applications of digital signal processing, including linear filtering, correlation analysis, and spectrum analysis. The major reason is the existence of efficient algorithms for computing the DFT. A divide-and-conquer approach in which a DFT of size N, where N is a composite number, is reduced to the computation of smaller DFTs from which the larger DFT is computed. Particularly for N=2B. A linear filtering operation on the data, this approach has two algorithms: the Goertzeland the chirp-z transform algorithms
DFT (Direct Compute) Digital Signal Processing--DFT/FFT Algorithms Complex Complex Real Real Multiplication Addition Multiplication Addition Y- X()∑xn)wN N-1 4N 2N+2(W-1) N X(k) N2 W(W-1) 4W2 2W(2W-1) 上游充通大
Digital Signal Processing—— DFT/FFT Algorithms DFT (Direct Compute) X k( ) 1 0 ( ) N nk N n x n W N N 1 4N 2 2( 1) N N N X k( ) 2 N N N( 1) 2 4N 2 (2 1) N N Complex Multiplication Complex Addition Real Multiplication Real Addition
Improve of DFT Digital Signal Processing--DFT/FFT Algorithms Symmetry (Wt)=W Periodicity Wik-WNim)k -WaNk) WWINW W W=1 W2=-1 WW+N/2）=-W DIT:Decimation-In-Time DIF:Decimation-In-Frequency 上游充通大￥
Digital Signal Processing—— DFT/FFT Algorithms Improve of DFT * nk nk W W N N nk N n k n N k ( ) ( ) W W W N N N nk mnk W W N mN / / nk nk m W W N N m 0 1 WN / 2 1 N WN ( /2) k N k W W N N Periodicity Symmetry DIT: Decimation-In-Time DIF: Decimation-In-Frequency