数字信号课件：DSP第四章5.ppt

1、直接DFT方法 / CZT方法：当要求准确的N点DFT，且N是素数时五、N为复合数的FFT算法混合基算法基-2FFT算法：2LN 2LN 当时补零使满足2LN 混合基FFT算法：N是复合数1、 整数的多基多进制表示形式 122102LLnnnn n n自然序 0122122LLnn n nnn倒位序 12212210102222LLLLnnnnnn 12012110222LLLLnnnnn 2LN（1）二进制： 0,1in 其中 0,1iL（2）r进制： LNr 12211221010LLLLnnrnrn rn rn 12012110LLLLnn rn rnrn12210LLrnnnn n n

2、0,1inr其中 0,1iL 01221LLrrnn n nnn（3）多基多进制（混合基）： 1 2LNrrr1 21210LLLrrrnnnn n 12 323 41010LLLLLnnr rrnrrrn rn1101,1Lnr其中 ， ，220,1,1Lnr00,1,1Lnr0,1,1iL inr即 0,1iL 01 2111 222 1110LLLLnnrrrn rrrnrn 2 12 10121LLLLrr rrr rnn nnn例： 1 244Nrr 104 454 1 111 4 410105114 1 15 104 464 1212 104 41142323 4 41010621

3、4219 4 41010113243214p 1 2010104nn rnnn 0 1101104nn rnnn00,1,2,3n 10,1,2,3n 2 2 31 30210103 22nn r rn rnnnn 0 1 21 1201010434nn rrn rnnnn00,1n 20,1,2,3n 10,1,2n 1 2 343 2Nrr r 例：104 3 2233 2 3221321 2 3 410102312343 142323 104 3 233 202 1 1011 2 3 41010311043 14 1018 104 3 2143 222 10210 2 3 4101014

4、01243 04 126 2、 的快速算法 1 2Nrr1 2Nrr1 20nn rn112020,1,1 0,1,1nrnrnr为 进制1210101,10,1,1krkrkr，为 进制2 1Nr r1 10kk rk1 2Nrr2 1Nr r行 列1r2r1n行序号0n列序号1r2r行 列0k行变量1k列变量 11 10100,NnkNnX kX rkkX k kx n W212 101 1001112 1000rrr nnrkkNnnx r nn W212 1 01 0 10 01 2 1 101111000,rrr n krn kn krr n kNNNNnnx n n WWWW211

5、 00 00 11201111000,rrn kn kn krNrnnx n n WWW20 00 12011000,rn kn kNrnXk n WW20 12011002010,rn krnXk n WXk k 的DFT 算法 1 2Nrr(1) 改写 成 x n10,x n n 2 1010,x nx r nnx n n11020,1,10,1,1nrnr(2)做 个 点DFT ，得 为参量，输入变量 ，输出变量 的 点 DFT2r1r100,Xk n0n1n0k1r(3) N个 （旋转因子） 0 0100,n kNXk nW100,Xk n(4)做 个 点DFT，得 为参量，输入变量

6、，输出变量 的 点DFT1r2r201,Xk k0k1k0n2r(5) 整序 10,X k kX k1 10krkk1 2428Nrr例 102nnn100,1,2,30,1nn104kkk100,10,1,2,3kk11 01 0111131001010400,rn kn krnnXk nx n n Wx n n W0 00 01001001008,n kn kNXk nXk n WXk n W20 10 120011201100100200,rn kn krnnXk kXk n WXk n W 10,X k kX k当N为高组合素数时： 1 2LNrrr个 点DFT，乘以旋转因子2 31L

7、Lr rrr1r 个 点DFTLr1 221LLrrrr X k整序个 点DFT，乘以旋转因子1 31LLrrrr2r个 点DFT，乘以旋转因子1 22LLrrrr1LrL级r点DFTLNr称基 算法，r 基 算法 2r 2混合基算法（基 算法） 1 2LNrrr1 2Lrrr4r 4基 算法混合基算法的运算量1 2Nrr不计译序、整序工作量（2）乘N个旋转因子 复乘 N总计： 222 11 2121Fmr rNrrN rr2 111 2212112Far r rrr rN rr（1） 个 点DFT 2r1r复乘22 1r r2 111r r r 复加 （3） 个 点DFT 2r1r21 2rr1 221rr r 复乘复加 2(1)FFmNaN N直接计算：，混合基节省的运算量 2121211NNRN rrrr1212NrrR1 2LNrrr11LFiimNrL1L 次乘N个旋转因子个 点DFT2 31LLr rrr1r个 点DFT1 31LLrrrr2r 个 点DFTLr1 221LLrrrr