第4章快速傅立叶变换(FFT) 4.1引言 4.2基2FFT算法 4.3进一步减少运算量的措施 4.4其他快速算法简介 Back
第4章 快速傅立叶变换（FFT） 4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 其他快速算法简介
第4章快速傅立叶变换(FFT) 4.1引言 DFT是数字信号分析与处理中的一种重要变换， 应用广泛。但由于直接计算DFT的计算量与变换区间 长度N的平方成正比，当N较大时，计算量太大，所 以在快速傅里叶变换FFT(Fast Fourier Transform) 出现以前，直接用DFT算法进行谱分析和信号的实时 处理是不切实际的。直到1965年库利与图基以及桑 德等提出DFT的一种快速算法FFT(基2的)以后， 情况才发生了根本的变化。 1984年杜哈梅尔和赫尔曼又提出分裂基的FFT Back
4.1 引 言 DFT是数字信号分析与处理中的一种重要变换， 应用广泛。但由于直接计算DFT的计算量与变换区间 长度N的平方成正比，当N较大时，计算量太大，所 以在快速傅里叶变换FFT(Fast Fourier Transform) 出现以前，直接用DFT算法进行谱分析和信号的实时 处理是不切实际的。直到1965年库利与图基以及桑 德等提出DFT的一种快速算法FFT（基2的）以后， 情况才发生了根本的变化。 1984年杜哈梅尔和赫尔曼又提出分裂基的FFT 。 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 4.2基2FFT算法 4.2.1直接计算DFT的特点及减少运算量的基本途径 1.直接计算DFT的运算量 N-1 X(k)=∑(n)W, k=0,1,.,N-1 n=0 m 1 N- Cx(k)ws"k, n=0,1,.,N-1 k=0 两者的差别仅在指数的符号和因子1/N
4.2 基2FFT算法 4.2.1 直接计算DFT的特点及减少运算量的基本途径 ( ) ( ) , 0,1, , 1 1 0 = = − − = X k x n W k N N n nk N − = − = = − 1 0 ( ) , 0,1, , 1 1 ( ) N k nk X k WN n N N x n 两者的差别仅在指数的符号和因子1/N. 1. 直接计算DFT的运算量 第4章 快速傅立叶变换（FFT）
第4章快速傅立叶变换(FFT) 个X(k)的值的工作量，如X(1) X(四=x(0)WW+x()W队+x(2)WR++x(N-1)W- 计算一个X(k)的值：N次复数乘法运算 N-1次复数加法运算.， N点DFT运算量： 复数乘法：N2 复数加法：N(N-1) 若N=1024,则N2=1048576
计算一个X(k)的值： N次复数乘法运算 N-1 次复数加法运算. 一个X(k)的值的工作量,如X(1) 0 1 2 1 (1) (0) (1) (2) ( 1) − = + + + + − N N N N N WN X x W x W x W x N点DFT运算量： 复数乘法： N2 复数加法： N(N-1) 若N=1024,则N2=1048576 第4章 快速傅立叶变换（FFT）
改进的途径 1)、把N点DFT分解成几个较短DFT可减少计算量 (N/2)2+(N/2)2=N2/2小于N2,同时有以下性质也 可减少计算量。 2)、X“的对称性、周期性、可约性 对称性：(W*)”=W nk 可约性：W=Ww*=W加 /m 周期性：Ww-)=W-=W(~W4=W=e2成=) W2=-l,:W=e=-1) Ww)=-W
2 改进的途径 1)、把N点DFT分解成几个较短DFT可减少计算量 (N/2)2+ (N/2)2 = N2/2小于N2 ，同时有以下性质也 可减少计算量。 2）、 WN nk 的对称性、周期性、可约性 k N k N N j N N N W W W W e N = − = − = = − + − ( / 2) / 2 1,( 1) 2 nk N nk WN W − = * 对称性: ( ) m n k m N nmk mN n k 可约性: WN = W = W 周期性 WN nk =WN (n+N )k =WN n(k+N ) : ( 1) ( ) ( ) 2 ( ) = = = = = − − − Nn − k n N Nk N n k N N n k N n N k N W W W W W e