第四章快速傅立叶变换 Fast Fourier transform
第四章 快速傅立叶变换 Fast Fourier Transform
第一节直接计算DFT的问题及改进途径 1、问题的提出 设有限长序列x(n),非零值长度为N,若 对x(n)进行一次DFT运算,共需多大的运算 工作量? 计算成本? 计算速度?
第一节 直接计算DFT的问题及改进途径 1、问题的提出 设有限长序列x(n)，非零值长度为N，若 对x(n)进行一次DFT运算，共需多大的运算 工作量？ 计算成本? 计算速度?
2.DFT的运算量 回忆DFT和DFT的变换式: X(k)=DFx(m)=∑x(m)WN0≤k≤N 0 x(n)=DFTX(k)=∑X(k)W0≤n≤N-1 =0 注意: k 1)x()为复数,W咻=eN也为复数 2)DFT与DFT的计算量相当
2. DFT的运算量 回忆DFT和IDFT的变换式： ( ) 0 1 1 ( ) [ ( )] 1 0 = = − − = − X k W n N N x n IDFT X k N k nk ( ) [ ( )] ( ) 0 1 1 0 = = − − = X k DFT x n x n W k N N n nk N 1）x(n)为复数， 也为复数。 2）DFT与IDFT的计算量相当。 nk N j nk N W e 2 − = 注意：
以DFT为例: X(k)=DFx(m)=∑x(m)W0≤k≤N-1 H=0 计算机运算时(编程实现): k=0X(0)=x(0W0+x(1)WN0+…+x(N-1-10 k=1X(1)=x(0X+x(1W+…+x(N-1)WX) (N-1)2 N个点 k=2X￥(2)=x(02+x(1)W2+…+x(N-1)WN k=N-1X(N-1)=x0+x()w+…+x(N-1)Wy-1 N次复乘,N-1次复加
计算机运算时（编程实现）： k = 0 0 0 1 0 ( 1) 0 (0) (0) (1) ( 1) − = + + + − N N N N WN X x W x W x k =1 01 11 ( 1) 1 (1) (0) (1) ( 1) N X x W x W x N W N N N − = + + + − k = 2 0 2 1 2 ( 1) 2 (2) (0) (1) ( 1) N X x W x W x N W N N N − = + + + − k = N −1 0 1 1 1 ( 1) 1 ( 1) (0) (1) ( 1) N N N N X N x W x W x N W N N N − − − − − = + + + − N次复乘，N-1次复加 N个点 ( ) [ ( )] ( ) 0 1 1 0 = = − − = X k DFT x n x n W k N N n nk N 以DFT为例：
运算量 复数乘法复数加法 个X(K) N N-1 N个X(k) N r(n N(N-1) 刀=0 (N点DFT) (atjb(c+(ac-bd)+j(bctad) 实数乘法实数加法 一次复乘4 次复加 22 个X(1) AN 2N+2(N-1)=2(2N-1) N个X(k) 4N2 2N(2N-1) (N点DFT)
复数乘法 复数加法 一个X(k) N N – 1 N个X(k) (N点DFT) N 2 N (N – 1) 实数乘法 实数加法 一次复乘 4 2 一次复加 2 一个X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N个X (k) (N点DFT) 4N 2 2N (2N – 1) 1 0 ( ) N nk N n x n W − = 运算量 (a+jb)(c+jd)=(ac-bd)+j(bc+ad)