2、运算量 当N=2L时，共有L级蝶形，每级N/2个蝶形，每 个蝶形有1次复数乘法2次复数加法。 复数乘法：%-L-og,水 2 2 复数加法：ap=NL=Nlog2N 1024 直接计算 比较DFT DFT mp(DFT) N2 2N 512 mg(FFT) Nlog,N log,N 256 FFT算法 2 1器 64128256512 1024 V(抽样点数)
2、运算量 当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每 个蝶形有1次复数乘法2次复数加法。 2 log 2 2 F N N 复数乘法： m L N 2 log F 复数加法： a NL N N 2 2 2 ( ) 2 ( ) log log 2 F F m DFT N N m FFT N N N 比较DFT
3、算法特点 1)原位计算 x(k)=X(k)+(j)WN X()=Xm(k)-Xm(j)WN m表示第m级迭代，飞，表示数据所在的行数 Xm-1(k) Xm(k)=Xm-1(k)+Xm-1()W Xm-i(j) W -1 一Xm)=Xm-1(k)一Xm-1)K 图47按时间抽选蝶形运算结构
3、算法特点 1）原位计算 1 1 1 1 ( ) ( ) ( ) ( ) ( ) ( ) r m m m N r m m m N X k X k X j W X j X k X j W m表示第m级迭代，k，j表示数据所在的行数
2)倒位序 x(n)n=(nnno)2 倒位序 自然序 no n n2 0 0 n=(nonn2)2 n=(nnno)2 1 000 0 000 1 100 001 1 010 2 010 0 0 110 011 1 001 100 1 101 101 1 011 6 110 111 7 7 111
2）倒位序 倒位序 自然序 000 0 0 000 100 4 1 001 010 2 2 010 110 6 3 011 001 1 4 100 101 5 5 101 011 3 6 110 111 7 7 111 n 0 n 1 n 2 0 0 01 1 01 1 0 01 1 01 2 1 0 2 x n n n n n ( ) ( ) 2 1 0 2 n n n n ( ) 0 1 2 2 n n n n ( )
存储单元 A(0) A(1) A(2) 4(3) A(4) A(5) 4(6) A(7刀 自然顺序输入 x(0) x(1)x(2) x(3) x(4) x(5) x(6) x(7) 变址 倒位序 x(0) x(4) (2) 1) x(5) x(3) x7) 图4-9 倒位序的变址处理
3)蝶形运算 对N=2L点FFT,输入倒位序，输出自然序， 第m级运算每个蝶形的两节点距离为2m-1 第m级运算： X(k)=X(k)+X(k+2"WN X(k+2")=X(k)-Xm(k+2")WN Xm-1(k) Xm(k)=Xm-1(k)+Xm-1()W Xm-⑦ 】之Xm0)=Xm-1(-Xm-0W1
3）蝶形运算 对N = 2L点FFT，输入倒位序，输出自然序， 第m级运算每个蝶形的两节点距离为 2 m–1 第m级运算： 1 1 1 1 1 1 1 ( ) ( ) ( 2 ) ( 2 ) ( ) ( 2 ) m r m m m N m m r m m m N X k X k X k W X k X k X k W